WINNOW .*;

Introduction

The Winnow algorithm is a single layer network (e.g.; perceptron).

Winnow was originally developed by Nick Littlestone in the late 1980's in hope of finding a faster learning algorithm to compete with the slower artificial neural networks.  It's called "'WINNOW' because it has been designed for efficiency in separating relevant from irrelevant attributes (Littlestone, 1988)."

Because of Winnow's simplicity, it can be trained very quickly.  Only the weights which are involved with a given input are trained, while the rest are ignored until needed.

The most useful aspects of this algorithm are online training and the dynamic addition of input nodes.  In other words, the network is supposed to grow as the input becomes more diverse, and it's trained while it's in use.  Normal applications will often grow to include hundreds or even thousands of input nodes, so code implementations rely on data structures that can expand dynamically (i.e.; static arrays won't work well).

In Littlestone's original design, Winnow's output was binary, so only one or two output nodes were needed.  However, later researchers easily added multiple output nodes.

The only real disadvantage to Winnow is that the number of output nodes need to be specified prior to use.

It's really unfortunate that WINNOW never became more popular.  It found brief success in the spam filtering industry between 2002 and 2005, but not much else.  It's unfortunate because online training and dynamic input node addition is incredibly useful.

 

 

Figure 1.  Originally, Winnow was designed to find a linear separation between patterns of ones and zeros.

 

 

Figure 2.  Later researchers modified the Winnow algorithm to recognize patterns for two or more classifications (i.e.; acceptable email versus spam). 

 

 

Works Cited:

Siefkes, C., Assis, F., Chhabra, S. & Yerazunis, W. S.  (2004).  "Combining Winnow and Orthogonal Sparse Bigrams for Incremental Spam Filtering."  J.-F. Boulicaut et al. (Eds.): PKDD 2004, LNAI 3202.  Springer-Verlag Berlin Heidelberg.  pp. 410-421.

Littlestone, N.  (1988).  "Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm".  Machine Learning vol. 2.  pp. 285-318.

 

public void footer() {
About | Contact | Privacy Policy | Terms of Service | Site Map
Copyright© 2009-2012 John McCullock. All Rights Reserved.
}