APPROXIMATE MAXIMAL MARGIN CLASSIFICATION WITH RESPECT TO AN ARBITRARY NORM
Dr Claudio Gentile, Department of Information Science, University of Milan, Italy

Abstract: A new incremental learning algorithm is described which is shown to approximate the maximal margin hyperplane w.r.t. norm $p \geq 2$ for a set of linearly separable data. Our algorithm, called ALMAp (Approximate Large Margin algorithm w.r.t. norm p), takes $O\left(\frac{(p-1)\,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. ALMAp 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. We report on some experiments about handwritten digit recognition comparing a variant of ALMAp to two incremental algorithms: Perceptron and Li and Long's ROMMA. These experiments show that our algorithm performs quite better than both.

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 7 September 2000

back