MaxMinOver: a simple incremental learning procedure for support vector classification

The well-known MinOver algorithm is a simple modification of the perceptron algorithm and provides the maximum margin classifier in a linearly separable two class classification problem. In its dual formulation selected training patterns which determine the separating hyperplane have to be stored. A drawback of MinOver is that this set of patterns does not consist only of support vectors. With MaxMinOver an extension of MinOver by a simple forgetting procedure is introduced. It is shown that this forgetting not only reduces the number of patterns which have to be stored, but also improves convergence bounds. After a finite number of training steps, the set of stored training patterns will consist only of support vectors. It is shown how this simple and iterative procedure can also be extended to classification with soft margins. The SoftMaxMinOver algorithm exhibits close connections to the v/support-vector-machine.