## A New Approximate Maximal Margin Classification Algorithm

** Claudio Gentile**;
2(Dec):213-242, 2001.

### Abstract

A new incremental learning algorithm is described which approximates the maximal margin hyperplane w.r.t. norm*p ≥ 2*for a set of linearly separable data. Our algorithm, called ALMA_

*p*(Approximate Large Margin algorithm w.r.t. norm

*p*), takes

*O( (p-1) / (α*corrections to separate the data with

^{2}γ^{2}) )*p*-norm margin larger than

*(1-α)γ*, where

*g*is the (normalized)

*p*-norm margin of the data. ALMA_

*p*avoids quadratic (or higher-order) programming methods. It is very easy to implement and is as fast as on-line algorithms, such as Rosenblatt's Perceptron algorithm. We performed extensive experiments on both real-world and artificial datasets. We compared ALMA_2 (i.e., ALMA_

*p*with

*p = 2*) to standard Support vector Machines (SVM) and to two incremental algorithms: the Perceptron algorithm and Li and Long's ROMMA. The accuracy levels achieved by ALMA_2 are superior to those achieved by the Perceptron algorithm and ROMMA, but slightly inferior to SVM's. On the other hand, ALMA_2 is quite faster and easier to implement than standard SVM training algorithms. When learning sparse target vectors, ALMA_

*p*with

*p > 2*largely outperforms Perceptron-like algorithms, such as ALMA_2.