Introduction

SNoW (Sparse Network of Winnows^1.1) is a learning architecture framework that is specifically tailored for learning in the presence of a very large number of features and can be used as a general purpose multi-class classifier.

The current release of the SNoW architectural framework is the third generation of the original SNoW learning system developed by Dan Roth. The learning framework is a sparse network of sparse linear functions over a predefined or incrementally acquired feature space. Several update rules^1.2 may be used: classical Winnow and Perceptron, variations of a regularized Winnow and a regularized Perception, regression algorithms based on Gradient Descent, and the naive Bayes algorithm.

SNoW is a multi-class learner, where each class label is represented as a linear function over the feature space. Both one-vs-all and true multi-class training policies^1.3 are supported. Predictions are done via a winner-take-all policy or via a voted combination of several learners.

SNoW takes input examples of variable size. Only those features that are active need be mentioned in each example. The expressivity of the linear learner can then be increased by automatically generating new features as combination of primitive features. Input features can be either Boolean or real valued. Decisions made by SNoW are either binary, indicating which of the labels is predicted for a given example, or continuous (in ), indicating a prediction confidence. Several other output modes are available.

Training SNoW is very efficient - order(s) of magnitude more efficient than other linear learners - and is competitive in performance to the best learners^1.4.

SNoW has been used successfully in several applications in the natural language and visual processing domains. You are welcome to experiment with it. This release is meant to be used only for research purposes, with the hope that it can be a useful research tool for studying learning in these domains. Feedback of any sort is welcome.

Dan Roth                   Urbana, IL. August, 2003.

The document is organized as follows. Chapter 2 contains the software license under the University of Illinois terms. Users need to agree to it and register on-line in order to use the software. Chapter 3 describes how to install the SNoW system. Chapter 4 gives a brief overview of the learning architecture framework and the technical approach including a description of the algorithms and some references. Next, in Chapter 6, the formats of the various files used by the system are described. A detailed description of how to use the system follows in Chapter 5, where all command line parameters and execution modes are described.

Finally, Chapter 7 is a tutorial showing how to use the system with various parameters. A glossary of terms and notations is also supplied.

A new user is encouraged to read all of this document, but the best starting place for learning to use the system is the tutorial. The tutorial gives a good sense of the required steps for using the system. Once a user is comfortable with the default method of using the system, the more detailed description of the command line parameters given in Chapter 5 may be more useful.

Footnotes

... Winnows^1.1

To winnow: to separate chaff from grain.

... rules^1.2

All implemented algorithms are described in Section 4.2.

... policies^1.3

See Section 4.3.1.

... learners^1.4

Scripts for parameter tuning and running experiments are supplied with the package.