|
About
NeuroCOLT
Papers
Archive
Books
info@neurocolt.org
|
NeuroCOLT
Technical Report NC-TR-01-096
2001-096
A new approximate maximal margin classification algorithm
Claudio Gentile
ABSTRACT
A new incremental learning algorithm is described which
approximates the maximal margin hyperplane w.r.t. norm $p \geq 2$
for a set of linearly separable data. Our algorithm, called Alma$_p$
(Approximate Large Margin algorithm w.r.t. norm $p$), takes $O\left(\frac{(p1)\,X^2}{\alpha^2\,\gamma^2}\right)$
corrections to separate the data with $p$-norm margin larger than
$(1-\alpha)\,\gamma$, where $\gamma$ is the $p$-norm margin of the
data and $X$ is a bound on the $p$-norm of the instances. 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$.
Download PDF
|