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

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.AbstractKernelizableBinaryCategorizerOnlineLearner
                      extended by gov.sandia.cognition.learning.algorithm.perceptron.AbstractLinearCombinationOnlineLearner
                          extended by gov.sandia.cognition.learning.algorithm.perceptron.OnlinePassiveAggressivePerceptron
All Implemented Interfaces:
BatchAndIncrementalLearner<InputOutputPair<? extends Vectorizable,Boolean>,LinearBinaryCategorizer>, BatchLearner<Collection<? extends InputOutputPair<? extends Vectorizable,Boolean>>,LinearBinaryCategorizer>, IncrementalLearner<InputOutputPair<? extends Vectorizable,Boolean>,LinearBinaryCategorizer>, KernelizableBinaryCategorizerOnlineLearner, SupervisedBatchAndIncrementalLearner<Vectorizable,Boolean,LinearBinaryCategorizer>, SupervisedBatchLearner<Vectorizable,Boolean,LinearBinaryCategorizer>, SupervisedIncrementalLearner<Vectorizable,Boolean,LinearBinaryCategorizer>, VectorFactoryContainer, CloneableSerializable, Serializable, Cloneable
Direct Known Subclasses:
OnlinePassiveAggressivePerceptron.AbstractSoftMargin

@PublicationReference(title="Online Passive-Aggressive Algorithms",
                      author={"Koby Crammer","Ofer Dekel","Joseph Keshet","Shai Shalev-Shwartz","Yoram Singer"},
                      year=2006,
                      type=Journal,
                      publication="Journal of Machine Learning Research",
                      pages={551,585},
                      url="http://portal.acm.org/citation.cfm?id=1248566")
public class OnlinePassiveAggressivePerceptron
extends AbstractLinearCombinationOnlineLearner

An implementation of the Passive-Aggressive algorithm for learning a linear binary categorizer. The Passive-Aggressive algorithm is similar to the Perceptron algorithm, except that it attempt to enforce a unit margin and also aggressively updates errors so that if given the same example as the next input, it will get it correct. This is an implementation of the PA algorithm that is designed for linearly separable cases (hard margin). Two internal classes, LinearSoftMargin and QuadraticSoftMargin implement the soft-margin variants (PA-I and PA-II).

Solves the optimization problem:

w_{t+1} = argmin_{w \in R^n} 0.5 ||w - w_t||^2
such that
l(w; (x_t, y_t)) = 0
where l(w; (x_t, y_t)) is the hinge loss (0 if y(w * x) >= 1) and 1 - y(w * x) otherwise.

The actual update step of the PA algorithm is simple:
w_{t+1} = w_t + \tau_t * y_t * x_t
where
\tau_t = l_t / ||x_t||^2

Note: This algorithm does not modify the bias of the linear categorizer. Thus, it is recommended that a bias term be added to the inputs prior to use.

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

Nested Class Summary
static class OnlinePassiveAggressivePerceptron.AbstractSoftMargin
          An abstract class for soft-margin versions of the Passive-Aggressive algorithm.
static class OnlinePassiveAggressivePerceptron.LinearSoftMargin
          An implementation of the linear soft-margin variant of the Passive- Aggressive algorithm (PA-I).
static class OnlinePassiveAggressivePerceptron.QuadraticSoftMargin
          An implementation of the quadratic soft-margin variant of the Passive- Aggressive algorithm (PA-II).
 
Field Summary
static boolean DEFAULT_UPDATE_BIAS
          By default the Passive-Aggressive Perceptron does not use a bias.
 
Fields inherited from class gov.sandia.cognition.learning.algorithm.perceptron.AbstractLinearCombinationOnlineLearner
updateBias
 
Fields inherited from class gov.sandia.cognition.learning.algorithm.perceptron.AbstractOnlineLinearBinaryCategorizerLearner
vectorFactory
 
Constructor Summary
OnlinePassiveAggressivePerceptron()
          Creates a new OnlinePassiveAggressivePerceptron.
OnlinePassiveAggressivePerceptron(VectorFactory<?> vectorFactory)
          Creates a new OnlinePassiveAggressivePerceptron with the given vector factory.
 
Method Summary
<InputType>
double
computeUpdate(DefaultKernelBinaryCategorizer<InputType> target, InputType input, boolean actualCategory, double predicted)
          Compute the update weight in the linear case.
protected  double computeUpdate(double actual, double predicted, double loss, double inputNorm2Squared)
          Compute the update value (tau) for the algorithm.
 double computeUpdate(LinearBinaryCategorizer target, Vector input, boolean actualCategory, double predicted)
          Compute the update weight in the linear case.
 
Methods inherited from class gov.sandia.cognition.learning.algorithm.perceptron.AbstractLinearCombinationOnlineLearner
computeDecay, computeDecay, computeRescaling, computeRescaling, createInitialLearnedObject, initialize, initialize, isUpdateBias, setUpdateBias, update, update
 
Methods inherited from class gov.sandia.cognition.learning.algorithm.perceptron.AbstractKernelizableBinaryCategorizerOnlineLearner
createKernelLearner, learn, update, update, update
 
Methods inherited from class gov.sandia.cognition.learning.algorithm.perceptron.AbstractOnlineLinearBinaryCategorizerLearner
createInitialLearnedObject, getVectorFactory, setVectorFactory, update
 
Methods inherited from class gov.sandia.cognition.learning.algorithm.AbstractSupervisedBatchAndIncrementalLearner
update
 
Methods inherited from class gov.sandia.cognition.learning.algorithm.AbstractBatchAndIncrementalLearner
clone, 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.SupervisedIncrementalLearner
update
 
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
createInitialLearnedObject, update, update
 
Methods inherited from interface gov.sandia.cognition.util.CloneableSerializable
clone
 

Field Detail

DEFAULT_UPDATE_BIAS

public static final boolean DEFAULT_UPDATE_BIAS
By default the Passive-Aggressive Perceptron does not use a bias.

See Also:
Constant Field Values
Constructor Detail

OnlinePassiveAggressivePerceptron

public OnlinePassiveAggressivePerceptron()
Creates a new OnlinePassiveAggressivePerceptron.


OnlinePassiveAggressivePerceptron

public OnlinePassiveAggressivePerceptron(VectorFactory<?> vectorFactory)
Creates a new OnlinePassiveAggressivePerceptron with the given vector factory.

Parameters:
vectorFactory - The vector factory to use.
Method Detail

computeUpdate

protected double computeUpdate(double actual,
                               double predicted,
                               double loss,
                               double inputNorm2Squared)
Compute the update value (tau) for the algorithm. Other variants of the algorithm should override this method.

Parameters:
actual - The actual label represented as a double (-1 or +1).
predicted - The value predicted by the current categorizer (w * x + b).
loss - The loss function (1 - predicted).
inputNorm2Squared - The squared 2-norm of the input (||x||^2).
Returns:
The update value to scale the input by. Should be > 0.0. May be 0.0 in degenerate cases such as a zero-vector input.

computeUpdate

public double computeUpdate(LinearBinaryCategorizer target,
                            Vector input,
                            boolean actualCategory,
                            double predicted)
Description copied from class: AbstractLinearCombinationOnlineLearner
Compute the update weight in the linear case. Must be implemented by subclasses.

Specified by:
computeUpdate in class AbstractLinearCombinationOnlineLearner
Parameters:
target - Target to compute the update for.
input - Input to use in computing the update.
actualCategory - The actual category of the input.
predicted - The predicted category of the input.
Returns:
The update weight for how much to add the input to the target. May be zero if no update is needed.

computeUpdate

public <InputType> double computeUpdate(DefaultKernelBinaryCategorizer<InputType> target,
                                        InputType input,
                                        boolean actualCategory,
                                        double predicted)
Description copied from class: AbstractLinearCombinationOnlineLearner
Compute the update weight in the linear case. Must be implemented by subclasses.

Specified by:
computeUpdate in class AbstractLinearCombinationOnlineLearner
Type Parameters:
InputType - The input value for learning.
Parameters:
target - Target to compute the update for.
input - Input to use in computing the update.
actualCategory - The actual category of the input.
predicted - The predicted category of the input.
Returns:
The update weight for how much to add the input to the target. May be zero if no update is needed.