The Perceptron with Dynamic Margin
  The classical perceptron rule provides a varying upper bound on the maximum
margin, namely the length of the current weight vector divided by the total
number of updates up to that time. Requiring that the perceptron updates its
internal state whenever the normalized margin of a pattern is found not to
exceed a certain fraction of this dynamic upper bound we construct a new
approximate maximum margin classifier called the perceptron with dynamic margin
(PDM). We demonstrate that PDM converges in a finite number of steps and derive
an upper bound on them. We also compare experimentally PDM with other
perceptron-like algorithms and support vector machines on hard margin tasks
involving linear kernels which are equivalent to 2-norm soft margin.
