A New Approximate Maximal Margin Classification Algorithm

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 ALMAp (Approximate Large Mar-gin algorithm w.r.t. norm p), takes 0 ((P~21;;2) corrections to sepa-rate the data with p-norm margin larger than (1- 0:),,(, where,, ( is the p-norm margin of the data and X is a bound on the p-norm of the in-stances. ALMAp avoids quadratic (or higher-order) programming meth-ods. It is very easy to implement and is as fast as on-line algorithms, such as Rosenblatt's perceptron. We report on some experiments comparing ALMAp to two incremental algorithms: Perceptron and Li and Long's ROMMA. Our algorithm seems to perform quite better than both. The accuracy levels achieved by ALMAp are slightly inferior to those obtained by Support vector Machines (SVMs). On the other hand, ALMAp is quite faster and easier to implement than standard SVMs training algorithms. 1