Winnow (algorithm)

The winnow algorithm is a technique from machine learning. It is closely related to the Perceptron, but it uses a multiplicative weight-update scheme that allows it perform much better than the perceptron when many dimensions are irrelevant (hence its name). It is not a sophisticated algorithm but it scales well to high-dimensional spaces. During training, winnow is shown a sequence of positive and negative examples. From these it learns a decision hyperplane.

The algorithm

The basic algorithm, Winnow1, is given as follows. The instance space is $X=\{0,1\}^{n}$. The algorithm maintains non-negative weights $w_{i}$ for $i\in \{1...n\}$ which are initially set to 1. When the learner is given an example $(x_1,...x_n)$, the learner follows the following prediction rule:

• If $\sum _{i=1}^{n}w_{i}x_{i}>\Theta$, then it predicts 1
• Otherwise it predicts 0

Where $\Theta$ is a real number that is called the 'threshold'. Good bounds are obtained if $\Theta =n/2$.

The update rule is (loosely):

• If an example is correctly classified, do nothing.
• If an example is predicted to be 1 but the correct result was 0, all of the weights involved in the mistake are set to zero (demotion step).
• If an example is predicted to be 0 but the correct result was 1, all of the weights involved in the mistake are multiplied by $\alpha$ (promotion step).

A good value for $\alpha$ is 2.

Variations are also used. For example, Winnow2 is the same as Winnow1 except that in the demotion step, the weights are multiplied by ${\frac {1}{\alpha }}$ instead of being set to 0.