|
NeuroCOLT
Technical Report NC-TR-97-023
The
Perceptron algorithm vs. Winnow:
linear vs. logarithmic mistake bounds
when few input variables are relevant
Jyrki
Kivinen
University of Helsinki, Finland
Manfred
Warmuth
University of California, Santa Cruz, USA
Peter
Auer
Technische Universitaet Graz, Austria
Abstract
We give an adversary strategy that forces the Perceptron algorithm
to make $\Omega(k N)$ mistakes in learning monotone disjunctions over
$N$ variables with at most $k$ literals. In contrast, Littlestone's
algorithm Winnow makes at most $O(k\log N)$ mistakes for the same
problem. Both algorithms use thresholded linear functions as their
hypotheses. However, Winnow does multiplicative updates to its weight
vector instead of the additive updates of the Perceptron algorithm.
The Perceptron algorithm is an example of {\em additive\/} algorithms,
which have the property that their weight vector is always a sum of
a fixed initial weight vector and some linear combination of already
seen instances. We show that an adversary can force any additive algorithm
to make $(N+k-1)/2$ mistakes in learning a monotone disjunction of
at most $k$ literals. Simple experiments show that for $k\ll N$, Winnow
clearly outperforms the Perceptron algorithm also on nonadversarial
random data.
Download Compressed Postscript
|