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) / (α2 γ2 ) )
corrections to separate the data with
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.
[abs]
[pdf]
[ps.gz]
[ps]
