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

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<InputType,Boolean,DefaultKernelBinaryCategorizer<InputType>>
              extended by gov.sandia.cognition.learning.algorithm.perceptron.kernel.AbstractOnlineKernelBinaryCategorizerLearner<InputType>
                  extended by gov.sandia.cognition.learning.algorithm.perceptron.kernel.AbstractOnlineBudgetedKernelBinaryCategorizerLearner<InputType>
                      extended by 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,Boolean>,DefaultKernelBinaryCategorizer<InputType>>, BatchLearner<Collection<? extends InputOutputPair<? extends InputType,Boolean>>,DefaultKernelBinaryCategorizer<InputType>>, IncrementalLearner<InputOutputPair<? extends InputType,Boolean>,DefaultKernelBinaryCategorizer<InputType>>, SupervisedBatchAndIncrementalLearner<InputType,Boolean,DefaultKernelBinaryCategorizer<InputType>>, SupervisedBatchLearner<InputType,Boolean,DefaultKernelBinaryCategorizer<InputType>>, SupervisedIncrementalLearner<InputType,Boolean,DefaultKernelBinaryCategorizer<InputType>>, KernelContainer<InputType>, CloneableSerializable, Serializable, 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
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
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
 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,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.