|
About
NeuroCOLT
Papers
Archive
Books
info@neurocolt.org
|
NeuroCOLT
Technical Report NC-TR-02-118
2002-118
The Perceptron Algorithm with Uneven Margins
Yaoyong Li
Hugo Zaragoza
Ralf Herbrich
John Shawe-Taylor
Jaz Kandola
ABSTRACT
The perceptron algorithm with margins is a simple, fast and effective learning algorithm for linear classifiers; it produces
decision hyperplanes within some constant ratio of the maximal margin.
In this paper we study this algorithm and a new variant: the perceptron
algorithm with uneven margins, tailored for document categorisation
problems (i.e.~problems where classes are highly unbalanced and performance
depends on the ranking of patterns). We discuss the interest of these
algorithms from a theoretical point of view, provide a generalisation
of Novikoff's theorem for uneven margins, give a geometrically description
of these algorithms and show experimentally that both algorithms yield
equal or better performances than support vector machines, while reducing
training time and sparsity, in classification (USPS) and document
categorisation (Reuters) problems.
Download
Postscript
|