Winnow (algorithm)

This MedLibrary.org supplementary page on Winnow (algorithm) is provided directly from the open source Wikipedia as a service to our readers. Please see the note below on authorship of this content, as well as the Wikipedia usage guidelines. To search for other content from our encyclopedia supplement, please use the form below:

Related Sponsors

BM Pharmacy Generic pharmaceuticals at unbeatable prices. Insomnia, men's health, hair health, pain control. bmpharmacy.com
Online Pharmacy Carisoprodol, tadalafil, sildenafil, vardenafil and more... xlpharmacy.com
MedBasket.com Discreet. Inexpensive. Fast shipping. Great selection. What more can we say? medbasket.com
Frugalmed 2000 reasons to shop with us first. frugalmed.com
Ads by Tiva

 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.

Contents

The algorithm

The basic algorithm, Winnow1, is given as follows. The instance space is X = {0,1}n. The algorithm maintains non-negative weights wi for i\in \{1...n\} which are initially set to 1. When the learner is given an example (x1,...xn), 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

  1. ^ Littlestone, N. (1988) "Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm" Machine Learning 285-318(2)
Comp Sci logo This computer science-related article is a stub. You can help Wikipedia by expanding it.

Wikipedia content modification information:

  • This page was last modified on 22 October 2008, at 00:23.

Wikipedia Authorship and Review

Wikipedia content provided here is not reviewed directly by MedLibrary.org. Wikipedia content is authored by an open community of volunteers and is not produced by or in any way affiliated with MedLibrary.org.

Wikipedia Usage Guidelines

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

The URL for this specific entry is:

All Wikipedia text is available under the terms of the GNU Free Documentation License. (See Copyrights for details). Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc.