A New Approximate Maximal Margin Classification Algorithm
A new incremental learning algorithm is described which
approximates the maximal margin hyperplane w.r.t. norm p ≥ 2
a set of linearly separable data.
Our algorithm, called ALMA_p
(Approximate Large Margin algorithm w.r.t. norm p
takes O( (p-1) / (α2 γ2 ) )
corrections to separate the data with p
-norm margin larger than (1-α)γ
is the (normalized) p
-norm margin of the data.
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
outperforms Perceptron-like algorithms, such as ALMA_2.