Winnow Algorithm

A Winnow Algorithm is an linear classification algorithm that uses a Multiplicative Weight-Update Method.

• Context:
  • …
• Counter-Example(s):
  • a Perceptron Algorithm, which uses an Additive Weight-Update Method.
• See: Online Machine Learning, Linear Classifier, Perceptron, Multiplicative Weight Update Method, Hyperplane.

---

---

References

2017

• (Wikipedia, 2017) ⇒ https://en.wikipedia.org/wiki/Winnow_(algorithm) Retrieved:2017-12-30.
  • 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 (hence its name). 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.

1988

• (Littlestone, 1988) ⇒ Nick Littlestone. (1988). “Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm.” Machine learning 2, no. 4

---