gov.sandia.cognition.learning.algorithm.perceptron
Class Winnow

java.lang.Object
  extended by gov.sandia.cognition.util.AbstractCloneableSerializable
      extended by gov.sandia.cognition.learning.algorithm.AbstractBatchAndIncrementalLearner<InputOutputPair<? extends InputType,OutputType>,ResultType>
          extended by gov.sandia.cognition.learning.algorithm.AbstractSupervisedBatchAndIncrementalLearner<Vectorizable,Boolean,LinearBinaryCategorizer>
              extended by gov.sandia.cognition.learning.algorithm.perceptron.AbstractOnlineLinearBinaryCategorizerLearner
                  extended by gov.sandia.cognition.learning.algorithm.perceptron.Winnow
All Implemented Interfaces:
BatchAndIncrementalLearner<InputOutputPair<? extends Vectorizable,Boolean>,LinearBinaryCategorizer>, BatchLearner<Collection<? extends InputOutputPair<? extends Vectorizable,Boolean>>,LinearBinaryCategorizer>, IncrementalLearner<InputOutputPair<? extends Vectorizable,Boolean>,LinearBinaryCategorizer>, SupervisedBatchAndIncrementalLearner<Vectorizable,Boolean,LinearBinaryCategorizer>, SupervisedBatchLearner<Vectorizable,Boolean,LinearBinaryCategorizer>, SupervisedIncrementalLearner<Vectorizable,Boolean,LinearBinaryCategorizer>, VectorFactoryContainer, CloneableSerializable, Serializable, Cloneable

@PublicationReference(author="Nick Littlestone",
                      title="Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm",
                      year=1988,
                      type=Journal,
                      publication="Machine Learning",
                      pages={285,318})
public class Winnow
extends AbstractOnlineLinearBinaryCategorizerLearner

An implementation of the Winnow incremental learning algorithm. It uses a multiplicative weight update rule to learn a binary categorization from binary features and produces a linear categorizer. It supports being used as either the Winnow1 or Winnow2 variants, which vary in how the demotion step is performed. Winnow1 demotes weights to zero while Winnow2 divides by the weight update value (alpha).

Since:
3.1
Author:
Justin Basilico
See Also:
Serialized Form

Field Summary
static boolean DEFAULT_DEMOTE_TO_ZERO
          The default value of demoteToZero is false.
static double DEFAULT_WEIGHT_UPDATE
          The default value of the weight update is 2.0.
protected  boolean demoteToZero
          An option to demote to zero.
protected  double weightUpdate
          The amount of the weight update (alpha).
protected  double weightUpdateInverse
          The cached value of the inverse of weight update (commonly alpha or 1 + epsilon).
 
Fields inherited from class gov.sandia.cognition.learning.algorithm.perceptron.AbstractOnlineLinearBinaryCategorizerLearner
vectorFactory
 
Constructor Summary
Winnow()
          Creates a new Winnow with default parameters.
Winnow(double weightUpdate)
          Creates a new Winnow with the given weight update and the default demote to zero (false).
Winnow(double weightUpdate, boolean demoteToZero)
          Creates a new Winnow with the given parameters.
 
Method Summary
 Winnow clone()
          This makes public the clone method on the Object class and removes the exception that it throws.
 LinearBinaryCategorizer createInitialLearnedObject()
          Creates a new initial learned object, before any data is given.
 double getWeightUpdate()
          Gets the multiplicative weight update term.
 boolean isDemoteToZero()
          Gets whether or not the algorithm will demote features involved in an incorrect categorization to zero (Winnow1).
 void setDemoteToZero(boolean demoteToZero)
          Sets whether or not the algorithm will demote features involved in an incorrect categorization to zero (Winnow1).
 void setWeightUpdate(double weightUpdate)
          Sets the multiplicative weight update term.
 void update(LinearBinaryCategorizer target, Vector input, boolean actual)
          The update method updates an object of ResultType using the given a new supervised input-output pair, using some form of "learning" algorithm.
 
Methods inherited from class gov.sandia.cognition.learning.algorithm.perceptron.AbstractOnlineLinearBinaryCategorizerLearner
getVectorFactory, setVectorFactory, update
 
Methods inherited from class gov.sandia.cognition.learning.algorithm.AbstractSupervisedBatchAndIncrementalLearner
update
 
Methods inherited from class gov.sandia.cognition.learning.algorithm.AbstractBatchAndIncrementalLearner
learn, learn, update
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface gov.sandia.cognition.learning.algorithm.BatchAndIncrementalLearner
learn
 
Methods inherited from interface gov.sandia.cognition.learning.algorithm.BatchLearner
learn
 
Methods inherited from interface gov.sandia.cognition.learning.algorithm.IncrementalLearner
update
 

Field Detail

DEFAULT_WEIGHT_UPDATE

public static final double DEFAULT_WEIGHT_UPDATE
The default value of the weight update is 2.0.

See Also:
Constant Field Values

DEFAULT_DEMOTE_TO_ZERO

public static final boolean DEFAULT_DEMOTE_TO_ZERO
The default value of demoteToZero is false.

See Also:
Constant Field Values

weightUpdate

protected double weightUpdate
The amount of the weight update (alpha). Must be greater than 1.


demoteToZero

protected boolean demoteToZero
An option to demote to zero.


weightUpdateInverse

protected double weightUpdateInverse
The cached value of the inverse of weight update (commonly alpha or 1 + epsilon).

Constructor Detail

Winnow

public Winnow()
Creates a new Winnow with default parameters.


Winnow

public Winnow(double weightUpdate)
Creates a new Winnow with the given weight update and the default demote to zero (false).

Parameters:
weightUpdate - The multiplicative factor to update the weights. Must be greater than one.

Winnow

public Winnow(double weightUpdate,
              boolean demoteToZero)
Creates a new Winnow with the given parameters.

Parameters:
weightUpdate - The multiplicative factor to update the weights. Must be greater than one.
demoteToZero - True to demote to zero (Winnow1) and false to demote by dividing by the weight (Winnow2).
Method Detail

clone

public Winnow clone()
Description copied from class: AbstractCloneableSerializable
This makes public the clone method on the Object class and removes the exception that it throws. Its default behavior is to automatically create a clone of the exact type of object that the clone is called on and to copy all primitives but to keep all references, which means it is a shallow copy. Extensions of this class may want to override this method (but call super.clone() to implement a "smart copy". That is, to target the most common use case for creating a copy of the object. Because of the default behavior being a shallow copy, extending classes only need to handle fields that need to have a deeper copy (or those that need to be reset). Some of the methods in ObjectUtil may be helpful in implementing a custom clone method. Note: The contract of this method is that you must use super.clone() as the basis for your implementation.

Specified by:
clone in interface CloneableSerializable
Overrides:
clone in class AbstractBatchAndIncrementalLearner<InputOutputPair<? extends Vectorizable,Boolean>,LinearBinaryCategorizer>
Returns:
A clone of this object.

createInitialLearnedObject

public LinearBinaryCategorizer createInitialLearnedObject()
Description copied from interface: IncrementalLearner
Creates a new initial learned object, before any data is given.

Specified by:
createInitialLearnedObject in interface IncrementalLearner<InputOutputPair<? extends Vectorizable,Boolean>,LinearBinaryCategorizer>
Overrides:
createInitialLearnedObject in class AbstractOnlineLinearBinaryCategorizerLearner
Returns:
The initial learned object.

update

public void update(LinearBinaryCategorizer target,
                   Vector input,
                   boolean actual)
Description copied from class: AbstractOnlineLinearBinaryCategorizerLearner
The update method updates an object of ResultType using the given a new supervised input-output pair, using some form of "learning" algorithm.

Specified by:
update in class AbstractOnlineLinearBinaryCategorizerLearner
Parameters:
target - The object to update.
input - The supervised input vector to learn from.
actual - The supervised output label to learn from.

getWeightUpdate

public double getWeightUpdate()
Gets the multiplicative weight update term.

Returns:
The multiplicative factor to update the weights. Must be greater than one.

setWeightUpdate

public void setWeightUpdate(double weightUpdate)
Sets the multiplicative weight update term.

Parameters:
weightUpdate - The multiplicative factor to update the weights. Must be greater than one.

isDemoteToZero

public boolean isDemoteToZero()
Gets whether or not the algorithm will demote features involved in an incorrect categorization to zero (Winnow1). If false, it is demoted using the inverse of the promotion weight (Winnow2).

Returns:
True to demote to zero (Winnow1) and false to demote by dividing by the weight.

setDemoteToZero

public void setDemoteToZero(boolean demoteToZero)
Sets whether or not the algorithm will demote features involved in an incorrect categorization to zero (Winnow1). If false, it is demoted using the inverse of the promotion weight (Winnow2).

Parameters:
demoteToZero - True to demote to zero (Winnow1) and false to demote by dividing by the weight (Winnow2).