Winnow (algorithm)

Winnow (algorithm)
This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Winnow_(algorithm)".

content

The introduction to this article provides insufficient context for those unfamiliar with the subject.
Please help improve the article with a good introductory style.

The winnow algorithm ^[1] 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. It can also be used in the online learning setting, where the learning phase is not separated from the training phase.

1 The algorithm
2 Mistake bounds
3 References
- 3.1 Citations and notes

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 $Θ$ is a real number that is called the 'threshold'. Good bounds are obtained if $Θ = 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 $α$ (promotion step).

A good value for $α$ 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.

Mistake bounds

If Winnow1 is run with $α > 1$ and $\Theta\geq 1/\alpha$ on a target function that is a $k$ -literal monotone disjunction given by $f(x_1,...x_n)=x_{i_1}\cup ... \cup x_{i_k}$ , then for any sequence of instances the total number of mistakes is bounded by $\alpha k ( \log_\alpha \Theta+1)+\frac{n}{\Theta}$ .

References

Citations and notes

^ Littlestone, N. (1988) "Learning Quickly When Irrelevant Attributes About: A New Linear-threshold Algorithm" Machine Learning 285-318(2)

This computer science-related article is a stub. You can help Wikipedia by expanding it.

Your Ad Here

Contents

The algorithm

Mistake bounds

References

Citations and notes