Content deleted Content added
No edit summary |
No edit summary |
||
Line 2:
Nick Littlestone (1988). "Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm", ''[http://www.springerlink.com/content/j0k7t38567325716/ Machine Learning 285–318(2)].</ref> is a technique from [[machine learning]] for learning a [[linear classifier]] from labeled examples. It is very similar to the [[perceptron|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 machine learning|online learning]] setting, where the learning and the classification phase are not clearly separated.
==
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]] [[features (pattern recognition)|features]]. The algorithm maintains non-negative weights <math>w_i</math> for <math>i\in \{1...n\}</math>, which are initially set to 1, one weight for each feature. When the learner is given an example <math>(x_1,...x_n)</math>, it applies the typical prediction rule for linear classifiers:▼
▲The instance space is <math>X=\{0,1\}^n</math>, that is, each instance is described as a set of [[Boolean-valued]] [[features (pattern recognition)|features]]. The algorithm maintains non-negative weights <math>w_i</math> for <math>i\in \{1...n\}</math>, which are initially set to 1, one weight for each feature. When the learner is given an example <math>(x_1,...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
Line 15 ⟶ 14:
* 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 implicated in the mistake are set to
* If an example is predicted to be 0 but the correct result was 1, all of the weights implicated in the mistake are multiplied by <math>\alpha</math> (promotion step).
| |||