The perceptron algorithm versus winnow: linear versus logarithmic mistake bounds when few input variables are relevant

作者:

摘要

We give an adversary strategy that forces the Perceptron algorithm to make Ω(kN) 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. In general, we call an algorithm additive if its weight vector is always a sum of a fixed initial weight vector and some linear combination of already seen instances. Thus, the Perceptron algorithm is an example of an additive algorithm. 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 ⪡ N, Winnow clearly outperforms the Perceptron algorithm also on nonadversarial random data.

论文关键词:Linear threshold functions,Perceptron algorithm,Relevant variables,Multiplicative updates,Mistake bounds

论文评审过程:Available online 19 May 1998.

论文官网地址:https://doi.org/10.1016/S0004-3702(97)00039-8