12:15, Wed 11 Sep 1996, WeH 7220
^^^^^
Polynomial-time guarantees for the Perceptron Algorithm
Avrim Blum
Abstract:
The Perceptron Algorithm is a simple, well-studied algorithm for
learning linear threshold functions. Given a set of linearly-
separable positive and negative examples, it converges in a finite
number of steps to a correct solution. Unfortunately, it can take
exponential time to converge, depending on the amount of "wiggle room"
available for a solution. In this work we describe a modified version
of the perceptron algorithm which we prove has the following modest
guarantee: it still may take exponential time to converge fully, BUT,
after a polynomial number of steps, it is guaranteed to have made at
least a noticeable amount of progress in the sense that by that time
it has correctly classified at least a 1/2 + epsilon fraction of the
data ("weak learning").
One might ask what the point of this is since given linearly separable
data one can find a solution in polynomial time using linear
programming. However, the Perceptron Algorithm has the advantage of
noise-tolerance (both empirically and theoretically demonstrated). A
specific theoretical result of this work is the first "polynomial time
algorithm for learning linear threshold functions in the presence of
random classification noise".
Does the new algorithm have ideas useful for practice? I don't know.
I'd like to try some experiments and would be interested in your
suggestions.
This is joint work with Alan Frieze, Ravi Kannan, and Santosh Vempala.