Maximal Margin Perceptron

Overview of sequential update algorithms for the Maximal Margin Perceptron. In particular, a new update method is derived which is based on the observation that the normal vector of the separating hyperplane can be found as the difference between between two points lying in the convex hull of positive and negative examples respectively. This new method has the advantage that at each iteration only one Lagrange multiplier has to be updated, leading to a potentially faster training algorithm. Bounds on the speed of convergence are stated and an experimental comparison with other training algorithms shows the good performance of this method.