gov.sandia.cognition.learning.algorithm.perceptron

Class OnlinePassiveAggressivePerceptron

java.lang.Object

gov.sandia.cognition.util.AbstractCloneableSerializable

gov.sandia.cognition.learning.algorithm.AbstractBatchAndIncrementalLearner<InputOutputPair<? extends InputType,OutputType>,ResultType>

gov.sandia.cognition.learning.algorithm.AbstractSupervisedBatchAndIncrementalLearner<Vectorizable,java.lang.Boolean,LinearBinaryCategorizer>

gov.sandia.cognition.learning.algorithm.perceptron.AbstractOnlineLinearBinaryCategorizerLearner

gov.sandia.cognition.learning.algorithm.perceptron.AbstractKernelizableBinaryCategorizerOnlineLearner

gov.sandia.cognition.learning.algorithm.perceptron.AbstractLinearCombinationOnlineLearner

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

All Implemented Interfaces:

BatchAndIncrementalLearner<InputOutputPair<? extends Vectorizable,java.lang.Boolean>,LinearBinaryCategorizer>, BatchLearner<java.util.Collection<? extends InputOutputPair<? extends Vectorizable,java.lang.Boolean>>,LinearBinaryCategorizer>, IncrementalLearner<InputOutputPair<? extends Vectorizable,java.lang.Boolean>,LinearBinaryCategorizer>, KernelizableBinaryCategorizerOnlineLearner, SupervisedBatchAndIncrementalLearner<Vectorizable,java.lang.Boolean,LinearBinaryCategorizer>, SupervisedBatchLearner<Vectorizable,java.lang.Boolean,LinearBinaryCategorizer>, SupervisedIncrementalLearner<Vectorizable,java.lang.Boolean,LinearBinaryCategorizer>, VectorFactoryContainer, CloneableSerializable, java.io.Serializable, java.lang.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://jmlr.org/papers/volume7/crammer06a/crammer06a.pdf")
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

Nested Classes

Modifier and Type	Class and Description
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

Fields

Modifier and Type	Field and Description
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

Constructors

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

Method Summary

Modifier and Type	Method and Description
<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.