# Winnow (algorithm)

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Winnow_(algorithm)
> Markdown URL: https://mediated.wiki/source/Winnow_(algorithm).md
> Source: https://en.wikipedia.org/wiki/Winnow_(algorithm)
> Source revision: 1322526698
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Algorithm from machine learning}}
The '''winnow algorithm'''<ref name="littlestone88"> Nick Littlestone (1988). "Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm", [https://doi.org/10.1023%2FA%3A1022869011914  ''Machine Learning'' 285–318(2)].</ref> is a technique from [machine learning](/source/machine_learning) for learning a [linear classifier](/source/linear_classifier) from labeled examples.  It is very similar to the [perceptron algorithm](/source/perceptron).  However, the perceptron algorithm uses an additive weight-update scheme, while Winnow uses a [multiplicative scheme](/source/Multiplicative_Weight_Update_Method) that allows it to perform much better when many dimensions are irrelevant (hence its name [winnow](/source/winnowing)). 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](/source/hyperplane) that can then be used to label novel examples as positive or negative.  The algorithm can also be used in the [online learning](/source/Online_machine_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 <math>X=\{0,1\}^n</math>, that is, each instance is described as a set of [Boolean-valued](/source/Boolean-valued) [features](/source/features_(pattern_recognition)).  The algorithm maintains non-negative weights <math>w_i</math> for <math>i\in \{1,\ldots,n\}</math>, which are initially set to 1, one weight for each feature.  When the learner is given an example <math>(x_1,\ldots,x_n)</math>, it applies the typical prediction rule for linear classifiers:

* '''If''' <math>\sum_{i=1}^n w_i x_i > \Theta </math>, '''then''' predict 1
* '''Otherwise''' predict 0

Here <math>\Theta</math> is a real number that is called the ''threshold''.  Together with the weights, the threshold defines a dividing hyperplane in the instance space.  Good bounds are obtained if <math>\Theta=n/2</math> (see below).

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 <math>x_{i}=1</math>, the corresponding weight <math>w_{i}</math> is set to 0 (demotion step).
*: <math>\forall x_{i} = 1, w_{i} = 0</math>
* If an example is predicted incorrectly and the correct result was 1, for each feature <math>x_{i}=1</math>, the corresponding weight <math>w_{i}</math> multiplied by {{mvar|&alpha;}}(promotion step).
*: <math>\forall x_{i} = 1, w_{i} = \alpha w_{i}</math>

A typical value for {{mvar|&alpha;}} is 2.

There are many variations to this basic approach.  ''Winnow2''<ref name="littlestone88"/> is similar except that in the demotion step the weights are divided by {{mvar|&alpha;}} 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](/source/multi-label_classification).

==Mistake bounds==
In certain circumstances, it can be shown that the number of mistakes Winnow makes as it learns has an [upper bound](/source/Upper_and_lower_bounds) that is independent of the number of instances with which it is presented.  If the Winnow1 algorithm uses <math>\alpha > 1</math> and <math>\Theta \geq 1/\alpha</math> on a target function that is a <math>k</math>-literal monotone disjunction given by <math>f(x_1,\ldots,x_n)=x_{i_1} \lor \cdots \lor x_{i_k}</math>, then for any sequence of instances the total number of mistakes is bounded by:
<math>\alpha k ( \log_\alpha \Theta+1)+\frac{n}{\Theta}</math>.<ref>
Nick Littlestone (1989). "Mistake bounds and logarithmic linear-threshold learning algorithms".
Technical report UCSC-CRL-89-11, University of California, Santa Cruz.</ref>

==References==
<references/>

Category:Classification algorithms

---
Adapted from the Wikipedia article [Winnow (algorithm)](https://en.wikipedia.org/wiki/Winnow_(algorithm)) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Winnow_(algorithm)?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.