|
NeuroCOLT
Technical Report NC-TR-95-029
The
Curse of Dimensionality and the Perceptron Algorithm
Jyrki
Kivinen
University of Helsinki
Manfred
K. Warmuth
University of California
Santa Cruz
Abstract
We give an adversary strategy that forces the Perceptron algorithm
to make $(N-k+1)/2$ mistakes when learning $k$-literal
disjunctions over $N$ variables. Experimentally we see that even for
simple random data, the number of mistakes made by the Perceptron
algorithm grows almost linearly with $N$, even if the number $k$ of
relevant variable remains a small constant. Thus, the Perceptron algorithm
suffers from the curse of dimensionality even when the target is extremely
simple and almost all of the dimensions are irrelevant. In contrast,
Littlestone's algorithm Winnow makes at most %$O(k(1+\log(N/k))$ mistakes
for the same problem. $O(k\log N)$ mistakes for the same problem.
Both algorithms use linear threshold functions as their hypotheses.
However, Winnow does multiplicative updates to its weight vector instead
of the additive updates of the Perceptron algorithm.
Download Compressed
Postscript
|