Winnow (algorithm)
The winnow algorithm is a technique from machine learning for learning a linear classifier from labeled examples. It is very similar to the perceptron algorithm. 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. 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. The algorithm can also be used in the online learning setting, where the learning and the classification phase are not clearly separated.
Algorithm
The basic algorithm, Winnow1, is as follows. The instance space is, that is, each instance is described as a set of Boolean-valued features. The algorithm maintains non-negative weights for, which are initially set to 1, one weight for each feature. When the learner is given an example, it applies the typical prediction rule for linear classifiers:- If, then predict 1
- Otherwise predict 0
For each example with which it is presented, the learner applies the following update rule:
- If an example is correctly classified, do nothing.
- If an example is predicted incorrectly and the correct result was 0, for each feature, the corresponding weight is set to 0.
- :
- If an example is predicted incorrectly and the correct result was 1, for each feature, the corresponding weight multiplied by.
- :
There are many variations to this basic approach. Winnow2 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. This can then be generalized for multi-label classification.