gov.sandia.cognition.learning.algorithm.perceptron.kernel

Class Forgetron<InputType>

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<InputType,java.lang.Boolean,DefaultKernelBinaryCategorizer<InputType>>

gov.sandia.cognition.learning.algorithm.perceptron.kernel.AbstractOnlineKernelBinaryCategorizerLearner<InputType>

gov.sandia.cognition.learning.algorithm.perceptron.kernel.AbstractOnlineBudgetedKernelBinaryCategorizerLearner<InputType>

gov.sandia.cognition.learning.algorithm.perceptron.kernel.Forgetron<InputType>

Type Parameters:

InputType - The type of input to learn over. Passed to the kernel function.

All Implemented Interfaces:

BatchAndIncrementalLearner<InputOutputPair<? extends InputType,java.lang.Boolean>,DefaultKernelBinaryCategorizer<InputType>>, BatchLearner<java.util.Collection<? extends InputOutputPair<? extends InputType,java.lang.Boolean>>,DefaultKernelBinaryCategorizer<InputType>>, IncrementalLearner<InputOutputPair<? extends InputType,java.lang.Boolean>,DefaultKernelBinaryCategorizer<InputType>>, SupervisedBatchAndIncrementalLearner<InputType,java.lang.Boolean,DefaultKernelBinaryCategorizer<InputType>>, SupervisedBatchLearner<InputType,java.lang.Boolean,DefaultKernelBinaryCategorizer<InputType>>, SupervisedIncrementalLearner<InputType,java.lang.Boolean,DefaultKernelBinaryCategorizer<InputType>>, KernelContainer<InputType>, CloneableSerializable, java.io.Serializable, java.lang.Cloneable

Direct Known Subclasses:

Forgetron.Greedy

@PublicationReference(author={"Ofer Dekel","Shai Shalev-Shwartz","Yoram Singer"},
                      title="The Forgetron: A Kernel-based Perceptron on a Budget",
                      year=2008,
                      type=Journal,
                      publication="SIAM Journal on Computing",
                      pages={1342,1372},
                      url="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.134.7604&rep=rep1&type=pdf",
                      notes="This is the self-tuned version.")
public class Forgetron<InputType>
extends AbstractOnlineBudgetedKernelBinaryCategorizerLearner<InputType>

An implementation of the "self-tuned" Forgetron algorithm, which is an online budgeted kernel binary categorizer learner. Note that this class requires its own extension of the DefaultKernelBinaryCategorizer to keep some extra information about learning.

Since:

3.3.0

Author:

Justin Basilico

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	Forgetron.Basic<InputType> An implementation of the "basic" Forgetron algorithm, which is an online budgeted kernel binary categorizer learner.
static class	Forgetron.Greedy<InputType> An implementation of the "greedy" Forgetron algorithm, which is an online budgeted kernel binary categorizer learner.
static class	Forgetron.Result<InputType> The result object learned by the Forgetron, which extends the DefaultKernelBinaryCategorizer with some additional state information needed in the update step.

Field Summary

Fields inherited from class gov.sandia.cognition.learning.algorithm.perceptron.kernel.AbstractOnlineBudgetedKernelBinaryCategorizerLearner

budget, DEFAULT_BUDGET

Fields inherited from class gov.sandia.cognition.learning.algorithm.perceptron.kernel.AbstractOnlineKernelBinaryCategorizerLearner

kernel

Constructor Summary

Constructors

Constructor and Description
Forgetron() Creates a new Forgetron with a null kernel and the default budget.
Forgetron(Kernel<? super InputType> kernel, int budget) Creates a new Forgetron with the given kernel and budget.

Method Summary

Modifier and Type	Method and Description
DefaultKernelBinaryCategorizer<InputType>	createInitialLearnedObject() Creates a new initial learned object, before any data is given.
protected void	shrink(Forgetron.Result<InputType> result) Apply the shrinking step of the algorithm.
void	update(DefaultKernelBinaryCategorizer<InputType> target, InputType input, boolean label) Updates the target categorizer based on the given input and its associated output.

Methods inherited from class gov.sandia.cognition.learning.algorithm.perceptron.kernel.AbstractOnlineBudgetedKernelBinaryCategorizerLearner

getBudget, setBudget

Methods inherited from class gov.sandia.cognition.learning.algorithm.perceptron.kernel.AbstractOnlineKernelBinaryCategorizerLearner

getKernel, setKernel, 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.util.CloneableSerializable

clone

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

Constructor Detail

Forgetron

public Forgetron()

Creates a new Forgetron with a null kernel and the default budget.

Forgetron

public Forgetron(Kernel<? super InputType> kernel,
                 int budget)

Creates a new Forgetron with the given kernel and budget.

Parameters:

kernel - The kernel to use.

budget - The budget for the maximum number of supports.

Method Detail

createInitialLearnedObject

public DefaultKernelBinaryCategorizer<InputType> 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 InputType,java.lang.Boolean>,DefaultKernelBinaryCategorizer<InputType>>

Overrides:

createInitialLearnedObject in class AbstractOnlineKernelBinaryCategorizerLearner<InputType>

Returns:

The initial learned object.

update

public void update(DefaultKernelBinaryCategorizer<InputType> target,
                   InputType input,
                   boolean label)

Description copied from class: AbstractOnlineKernelBinaryCategorizerLearner

Updates the target categorizer based on the given input and its associated output.

Specified by:

update in class AbstractOnlineKernelBinaryCategorizerLearner<InputType>

Parameters:

target - The target categorizer to update.

input - The input value to learn from.

label - The output value associated with the input.

shrink

protected void shrink(Forgetron.Result<InputType> result)

Apply the shrinking step of the algorithm.

Parameters:

result - The shrinking step.