The winnow algorithm is a technique from machine learning

Machine learning

Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...

 for learning a linear classifier

Linear classifier

In the field of machine learning, the goal of statistical classification is to use an object's characteristics to identify which class it belongs to. A linear classifier achieves this by making a classification decision based on the value of a linear combination of the characteristics...

 from labeled examples. It is very similar to the perceptron algorithm

Perceptron

The perceptron is a type of artificial neural network invented in 1957 at the Cornell Aeronautical Laboratory by Frank Rosenblatt. It can be seen as the simplest kind of feedforward neural network: a linear classifier.- Definition :...

. 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 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

Hyperplane

A hyperplane is a concept in geometry. It is a generalization of the plane into a different number of dimensions.A hyperplane of an n-dimensional space is a flat subset with dimension n − 1...

 that can then be used to label novel examples as positive or negative. The algorithm can also be used in the online learning

Online machine learning

In machine learning, online learning is a model of induction that learns one instance at atime. The goal in online learning is to predict labels for instances.For example, the instances could describe the current conditions of...

 setting, where the learning and the classification phase are not clearly separated.

The algorithm

The basic algorithm, Winnow1, is given as follows.
The instance space is , that is, each instance is described as a set of Boolean-valued

Boolean-valued

Boolean-valued usually refers to:* in most applied fields: something taking one of two values referring to two-element Boolean algebra , e.g. Boolean-valued function or Boolean data type...

 features

Features (pattern recognition)

In pattern recognition, features are the individual measurable heuristic properties of the phenomena being observed. Choosing discriminating and independent features is key to any pattern recognition algorithm being successful in classification...

. The algorithm maintains non-negative weights for , which are initially set to 1, one weight for each feature. When the learner is given an example , it applies the typical prediction rule for linear classifiers:

• If , then predict 1
• Otherwise predict 0

Here 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 (see below).

For each example with which it is presented, the learner apples the following update rule:

• 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 zero (demotion step).
• 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 (promotion step).

Here, "implicated" means weights on features of the instance that have value 1. A typical value for is 2.

There are many variations to this basic approach. Winnow2 is similar except that in the demotion step the weights are divided by 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

Multi-label classification

In machine learning, multi-label classification is a variant of the classification problem where multiple target labels must be assigned to each instance...

.

Mistake bounds

In certain circumstances, it can be shown that the number of mistakes Winnow makes as it learns has an upper bound that is independent of the number of instances with which it is presented. If the Winnow1 algorithm uses and on a target function that is a -literal monotone disjunction given by , then for any sequence of instances the total number of mistakes is bounded by:
.