  We introduce into the classical perceptron algorithm with margin a mechanism
that shrinks the current weight vector as a first step of the update. If the
shrinking factor is constant the resulting algorithm may be regarded as a
margin-error-driven version of NORMA with constant learning rate. In this case
we show that the allowed strength of shrinking depends on the value of the
maximum margin. We also consider variable shrinking factors for which there is
no such dependence. In both cases we obtain new generalizations of the
perceptron with margin able to provably attain in a finite number of steps any
desirable approximation of the maximal margin hyperplane. The new approximate
maximum margin classifiers appear experimentally to be very competitive in
2-norm soft margin tasks involving linear kernels.
