gov.sandia.cognition.learning.algorithm.svm

Class SequentialMinimalOptimization<InputType>

java.lang.Object

gov.sandia.cognition.util.AbstractCloneableSerializable

gov.sandia.cognition.algorithm.AbstractIterativeAlgorithm

gov.sandia.cognition.algorithm.AbstractAnytimeAlgorithm<ResultType>

gov.sandia.cognition.learning.algorithm.AbstractAnytimeBatchLearner<java.util.Collection<? extends InputOutputPair<? extends InputType,OutputType>>,ResultType>

gov.sandia.cognition.learning.algorithm.AbstractAnytimeSupervisedBatchLearner<InputType,java.lang.Boolean,KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>>>

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<java.util.Collection<? extends InputOutputPair<? extends InputType,java.lang.Boolean>>,KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>>>, BatchLearner<java.util.Collection<? extends InputOutputPair<? extends InputType,java.lang.Boolean>>,KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>>>, SupervisedBatchLearner<InputType,java.lang.Boolean,KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>>>, KernelContainer<InputType>, CloneableSerializable, Randomized, java.io.Serializable, java.lang.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,java.lang.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

Fields

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

Constructors

Constructor and Description
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, java.util.Random random) Creates a new instance of Sequential Minimal Optimization with the given kernel and random number generator.
SequentialMinimalOptimization(Kernel<? super InputType> kernel, java.util.Random random) Creates a new instance of Sequential Minimal Optimization with the given kernel and random number generator.

Method Summary

Modifier and Type	Method and Description
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<java.lang.Integer>	getPerformance() Gets the name-value pair that describes the current performance of the algorithm.
java.util.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(java.util.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 java.lang.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,
                                     java.util.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,
                                     java.util.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<java.util.Collection<? extends InputOutputPair<? extends InputType,java.lang.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<java.util.Collection<? extends InputOutputPair<? extends InputType,java.lang.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<java.util.Collection<? extends InputOutputPair<? extends InputType,java.lang.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 java.util.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(java.util.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<java.lang.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.