gov.sandia.cognition.learning.algorithm.svm
Class SequentialMinimalOptimization<InputType>

java.lang.Object
  extended by gov.sandia.cognition.util.AbstractCloneableSerializable
      extended by gov.sandia.cognition.algorithm.AbstractIterativeAlgorithm
          extended by gov.sandia.cognition.algorithm.AbstractAnytimeAlgorithm<ResultType>
              extended by gov.sandia.cognition.learning.algorithm.AbstractAnytimeBatchLearner<Collection<? extends InputOutputPair<? extends InputType,OutputType>>,ResultType>
                  extended by gov.sandia.cognition.learning.algorithm.AbstractAnytimeSupervisedBatchLearner<InputType,Boolean,KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>>>
                      extended by gov.sandia.cognition.learning.algorithm.svm.SequentialMinimalOptimization<InputType>
Type Parameters:
InputType - The type of the input data to learn the support vector machine.
All Implemented Interfaces:
AnytimeAlgorithm<KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>>>, IterativeAlgorithm, MeasurablePerformanceAlgorithm, StoppableAlgorithm, AnytimeBatchLearner<Collection<? extends InputOutputPair<? extends InputType,Boolean>>,KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>>>, BatchLearner<Collection<? extends InputOutputPair<? extends InputType,Boolean>>,KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>>>, SupervisedBatchLearner<InputType,Boolean,KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>>>, KernelContainer<InputType>, CloneableSerializable, Randomized, Serializable, Cloneable

@PublicationReference(title="Fast training of support vector machines using sequential minimal optimization",
                      author="John C. Platt",
                      year=1999,
                      type=BookChapter,
                      pages={185,208},
                      publication="Advances in Kernel Methods",
                      url="http://research.microsoft.com/pubs/68391/smo-book.pdf")
public class SequentialMinimalOptimization<InputType>
extends AbstractAnytimeSupervisedBatchLearner<InputType,Boolean,KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>>>
implements KernelContainer<InputType>, Randomized, MeasurablePerformanceAlgorithm

An implementation of the Sequential Minimal Optimization (SMO) algorithm for training a Support Vector Machine (SVM), which is a kernel-based binary categorizer.

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

Field Summary
static double DEFAULT_EFFECTIVE_ZERO
          The default effective value for zero is 1.0E-10.
static double DEFAULT_ERROR_TOLERANCE
          The default error tolerance is 0.001, which is what was recommended in the original Sequential Minimal Optimization paper.
static int DEFAULT_KERNEL_CACHE_SIZE
          The default size of the kernel cache.
static int DEFAULT_MAX_ITERATIONS
          The default maximum number of iterations is 1000.
static double DEFAULT_MAX_PENALTY
          The default maximum penalty is infinite, which means that it is hard-assignment.
static String PERFORMANCE_NAME
          The performance name is "Change count".
 
Fields inherited from class gov.sandia.cognition.learning.algorithm.AbstractAnytimeBatchLearner
data, keepGoing
 
Fields inherited from class gov.sandia.cognition.algorithm.AbstractAnytimeAlgorithm
maxIterations
 
Fields inherited from class gov.sandia.cognition.algorithm.AbstractIterativeAlgorithm
DEFAULT_ITERATION, iteration
 
Constructor Summary
SequentialMinimalOptimization()
          Creates a new instance of Sequential Minimal Optimization.
SequentialMinimalOptimization(Kernel<? super InputType> kernel)
          Creates a new instance of Sequential Minimal Optimization with the given kernel.
SequentialMinimalOptimization(Kernel<? super InputType> kernel, double maxPenalty, double errorTolerance, double effectiveZero, int kernelCacheSize, int maxIterations, Random random)
          Creates a new instance of Sequential Minimal Optimization with the given kernel and random number generator.
SequentialMinimalOptimization(Kernel<? super InputType> kernel, Random random)
          Creates a new instance of Sequential Minimal Optimization with the given kernel and random number generator.
 
Method Summary
protected  void cleanupAlgorithm()
          Called to clean up the learning algorithm's state after learning has finished.
protected  int examineExample(int j)
          Examines one example in order to try and take a step of SMO using it.
 int getChangeCount()
          Gets the number of changes made on the last iteration of the algorithm.
 double getEffectiveZero()
          Gets the effective value for zero to use in the computation to deal with numerical imprecision.
 double getErrorTolerance()
          Gets the error tolerance for the algorithm.
 Kernel<? super InputType> getKernel()
          Gets the kernel.
 int getKernelCacheSize()
          Gets the size of the kernel cache or 0 if no kernel cache is to be used.
 double getMaxPenalty()
          Gets the maximum penalty parameter for the algorithm, which is also known as C in the paper and in other related literature.
 DefaultNamedValue<Integer> getPerformance()
          Gets the name-value pair that describes the current performance of the algorithm.
 Random getRandom()
          Gets the random number generator used by this object.
 KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>> getResult()
          Gets the current result of the algorithm.
protected  boolean initializeAlgorithm()
          Called to initialize the learning algorithm's state based on the data that is stored in the data field.
 void setEffectiveZero(double effectiveZero)
          Sets the effective value for zero to use in the computation to deal with numerical imprecision.
 void setErrorTolerance(double errorTolerance)
          Sets the error tolerance for the algorithm.
 void setKernel(Kernel<? super InputType> kernel)
          Sets the kernel to use in training the SVM.
 void setKernelCacheSize(int kernelCacheSize)
          Sets the size of the kernel cache or 0 if no kernel cache is to be used.
 void setMaxPenalty(double maxPenalty)
          Sets the maximum penalty parameter for the algorithm, which is also known as C in the paper and in other related literature.
 void setRandom(Random random)
          Sets the random number generator used by this object.
protected  boolean step()
          Called to take a single step of the learning algorithm.
 
Methods inherited from class gov.sandia.cognition.learning.algorithm.AbstractAnytimeBatchLearner
clone, getData, getKeepGoing, learn, setData, setKeepGoing, stop
 
Methods inherited from class gov.sandia.cognition.algorithm.AbstractAnytimeAlgorithm
getMaxIterations, isResultValid, setMaxIterations
 
Methods inherited from class gov.sandia.cognition.algorithm.AbstractIterativeAlgorithm
addIterativeAlgorithmListener, fireAlgorithmEnded, fireAlgorithmStarted, fireStepEnded, fireStepStarted, getIteration, getListeners, removeIterativeAlgorithmListener, setIteration, setListeners
 
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.BatchLearner
learn
 
Methods inherited from interface gov.sandia.cognition.algorithm.AnytimeAlgorithm
getMaxIterations, setMaxIterations
 
Methods inherited from interface gov.sandia.cognition.algorithm.IterativeAlgorithm
addIterativeAlgorithmListener, getIteration, removeIterativeAlgorithmListener
 
Methods inherited from interface gov.sandia.cognition.algorithm.StoppableAlgorithm
isResultValid
 

Field Detail

DEFAULT_MAX_ITERATIONS

public static final int DEFAULT_MAX_ITERATIONS
The default maximum number of iterations is 1000.

See Also:
Constant Field Values

DEFAULT_MAX_PENALTY

public static final double DEFAULT_MAX_PENALTY
The default maximum penalty is infinite, which means that it is hard-assignment.

See Also:
Constant Field Values

DEFAULT_ERROR_TOLERANCE

public static final double DEFAULT_ERROR_TOLERANCE
The default error tolerance is 0.001, which is what was recommended in the original Sequential Minimal Optimization paper.

See Also:
Constant Field Values

DEFAULT_EFFECTIVE_ZERO

public static final double DEFAULT_EFFECTIVE_ZERO
The default effective value for zero is 1.0E-10.

See Also:
Constant Field Values

DEFAULT_KERNEL_CACHE_SIZE

public static final int DEFAULT_KERNEL_CACHE_SIZE
The default size of the kernel cache.

See Also:
Constant Field Values

PERFORMANCE_NAME

public static final String PERFORMANCE_NAME
The performance name is "Change count".

See Also:
Constant Field Values
Constructor Detail

SequentialMinimalOptimization

public SequentialMinimalOptimization()
Creates a new instance of Sequential Minimal Optimization. It initializes the parameters to default values and the kernel to null.


SequentialMinimalOptimization

public SequentialMinimalOptimization(Kernel<? super InputType> kernel)
Creates a new instance of Sequential Minimal Optimization with the given kernel. All other parameters are set to their default values.

Parameters:
kernel - The kernel to use.

SequentialMinimalOptimization

public SequentialMinimalOptimization(Kernel<? super InputType> kernel,
                                     Random random)
Creates a new instance of Sequential Minimal Optimization with the given kernel and random number generator. All other parameters are set to their default values.

Parameters:
kernel - The kernel to use.
random - The random number generator to use.

SequentialMinimalOptimization

public SequentialMinimalOptimization(Kernel<? super InputType> kernel,
                                     double maxPenalty,
                                     double errorTolerance,
                                     double effectiveZero,
                                     int kernelCacheSize,
                                     int maxIterations,
                                     Random random)
Creates a new instance of Sequential Minimal Optimization with the given kernel and random number generator. All other parameters are set to their default values.

Parameters:
kernel - The kernel to use.
maxPenalty - The maximum penalty parameter (C). Must be greater than 0.0.
errorTolerance - The error tolerance for the algorithm. Must be non-negative.
effectiveZero - The effective value for zero. Must be non-negative.
kernelCacheSize - The size of the kernel cache. Must be non-negative.
maxIterations - The maximum number of iterations to run the algorithm.
random - The random number generator to use.
Method Detail

initializeAlgorithm

protected boolean initializeAlgorithm()
Description copied from class: AbstractAnytimeBatchLearner
Called to initialize the learning algorithm's state based on the data that is stored in the data field. The return value indicates if the algorithm can be run or not based on the initialization.

Specified by:
initializeAlgorithm in class AbstractAnytimeBatchLearner<Collection<? extends InputOutputPair<? extends InputType,Boolean>>,KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>>>
Returns:
True if the learning algorithm can be run and false if it cannot.

step

protected boolean step()
Description copied from class: AbstractAnytimeBatchLearner
Called to take a single step of the learning algorithm.

Specified by:
step in class AbstractAnytimeBatchLearner<Collection<? extends InputOutputPair<? extends InputType,Boolean>>,KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>>>
Returns:
True if another step can be taken and false it the algorithm should halt.

cleanupAlgorithm

protected void cleanupAlgorithm()
Description copied from class: AbstractAnytimeBatchLearner
Called to clean up the learning algorithm's state after learning has finished.

Specified by:
cleanupAlgorithm in class AbstractAnytimeBatchLearner<Collection<? extends InputOutputPair<? extends InputType,Boolean>>,KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>>>

examineExample

protected int examineExample(int j)
Examines one example in order to try and take a step of SMO using it.

Parameters:
j - The index of the example to examine.
Returns:
1 if the example created an update. Otherwise, 0.

getResult

public KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>> getResult()
Description copied from interface: AnytimeAlgorithm
Gets the current result of the algorithm.

Specified by:
getResult in interface AnytimeAlgorithm<KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>>>
Returns:
Current result of the algorithm.

getKernel

public Kernel<? super InputType> getKernel()
Description copied from interface: KernelContainer
Gets the kernel.

Specified by:
getKernel in interface KernelContainer<InputType>
Returns:
Internal kernel encapsulated by the KernelContainer.

setKernel

public void setKernel(Kernel<? super InputType> kernel)
Sets the kernel to use in training the SVM.

Parameters:
kernel - The kernel to use in training the SVM.

getMaxPenalty

public double getMaxPenalty()
Gets the maximum penalty parameter for the algorithm, which is also known as C in the paper and in other related literature.

Returns:
The maximum penalty parameter (C). Must be greater than 0.0.

setMaxPenalty

public void setMaxPenalty(double maxPenalty)
Sets the maximum penalty parameter for the algorithm, which is also known as C in the paper and in other related literature.

Parameters:
maxPenalty - The maximum penalty parameter (C). Must be greater than 0.0.

getErrorTolerance

public double getErrorTolerance()
Gets the error tolerance for the algorithm. This is how close the output of the SVM must be to the target values of +1.0 or -1.0. In the original paper, this is the "tolerance" or "tol" term. Typically close to zero, but larger than the effective zero.

Returns:
The error tolerance for the algorithm. Must be non-negative.

setErrorTolerance

public void setErrorTolerance(double errorTolerance)
Sets the error tolerance for the algorithm. This is how close the output of the SVM must be to the target values of +1.0 or -1.0. In the original paper, this is the "tolerance" or "tol" term. Typically close to zero, but larger than the effective zero.

Parameters:
errorTolerance - The error tolerance for the algorithm. Must be non-negative.

getEffectiveZero

public double getEffectiveZero()
Gets the effective value for zero to use in the computation to deal with numerical imprecision. It is also known as "epsilon" or "eps" in the original paper. Must be a non-negative number. Typically a very small value.

Returns:
The effective value for zero. Must be non-negative.

setEffectiveZero

public void setEffectiveZero(double effectiveZero)
Sets the effective value for zero to use in the computation to deal with numerical imprecision. It is also known as "epsilon" or "eps" in the original paper. Must be a non-negative number. Typically a very small value.

Parameters:
effectiveZero - The effective value for zero. Must be non-negative.

getKernelCacheSize

public int getKernelCacheSize()
Gets the size of the kernel cache or 0 if no kernel cache is to be used.

Returns:
The size of the kernel cache. Must be non-negative.

setKernelCacheSize

public void setKernelCacheSize(int kernelCacheSize)
Sets the size of the kernel cache or 0 if no kernel cache is to be used.

Parameters:
kernelCacheSize - The size of the kernel cache. Must be non-negative.

getRandom

public Random getRandom()
Description copied from interface: Randomized
Gets the random number generator used by this object.

Specified by:
getRandom in interface Randomized
Returns:
The random number generator used by this object.

setRandom

public void setRandom(Random random)
Description copied from interface: Randomized
Sets the random number generator used by this object.

Specified by:
setRandom in interface Randomized
Parameters:
random - The random number generator for this object to use.

getChangeCount

public int getChangeCount()
Gets the number of changes made on the last iteration of the algorithm.

Returns:
The number of changes made on the last iteration of the algorithm.

getPerformance

public DefaultNamedValue<Integer> getPerformance()
Description copied from interface: MeasurablePerformanceAlgorithm
Gets the name-value pair that describes the current performance of the algorithm. For most algorithms, this is the value that they are attempting to optimize.

Specified by:
getPerformance in interface MeasurablePerformanceAlgorithm
Returns:
The name-value pair that describes the current performance of the algorithm.