The winnow algorithm[1] is a technique from machine learning for learning a linear classifier from labeled examples.
However, the perceptron algorithm uses an additive weight-update scheme, while Winnow uses a multiplicative scheme that allows it to perform much better when many dimensions are irrelevant (hence its name winnow).
It is a simple algorithm that scales well to high-dimensional data.
During training, Winnow is shown a sequence of positive and negative examples.
From these it learns a decision hyperplane that can then be used to label novel examples as positive or negative.
, that is, each instance is described as a set of Boolean-valued features.
The algorithm maintains non-negative weights
, which are initially set to 1, one weight for each feature.
, it applies the typical prediction rule for linear classifiers: Here
is a real number that is called the threshold.
Together with the weights, the threshold defines a dividing hyperplane in the instance space.
For each example with which it is presented, the learner applies the following update rule: A typical value for α is 2.
Winnow2[1] is similar except that in the demotion step the weights are divided by α instead of being set to 0.
Balanced Winnow maintains two sets of weights, and thus two hyperplanes.
In certain circumstances, it can be shown that the number of mistakes Winnow makes as it learns has an upper bound that is independent of the number of instances with which it is presented.
, then for any sequence of instances the total number of mistakes is bounded by: