gov.sandia.cognition.learning.algorithm.svm

Class SuccessiveOverrelaxation<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.SuccessiveOverrelaxation<InputType>

Type Parameters:

InputType - The type of the input data.

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>>>, CloneableSerializable, java.io.Serializable, java.lang.Cloneable

@CodeReview(reviewer="Kevin R. Dixon",
            date="2008-07-23",
            changesNeeded=false,
            comments={"Minor cosmetic to javadoc.","Great looking code."})
 @PublicationReference(author={"Olvi L. Mangasarian","David R. Musicant"},
                      title="Successive Overrelaxation for Support Vector Machines",
                      type=Journal,
                      year=1999,
                      publication="IEEE Transactions on Neural Networks",
                      pages={1032,1037},
                      url="ftp://ftp.cs.wisc.edu/math-prog/tech-reports/98-18.ps")
public class SuccessiveOverrelaxation<InputType>
extends AbstractAnytimeSupervisedBatchLearner<InputType,java.lang.Boolean,KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>>>
implements MeasurablePerformanceAlgorithm

The SuccessiveOverrelaxation class implements the Successive Overrelaxation (SOR) algorithm for learning a Support Vector Machine (SVM).

Since:

2.1

Author:

Justin Basilico

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected class	SuccessiveOverrelaxation.Entry The Entry class represents the data that the algorithm keeps about each training example.

Field Summary

Fields

Modifier and Type	Field and Description
static int	DEFAULT_MAX_ITERATIONS The default maximum number of iterations, 1000.
static double	DEFAULT_MAX_WEIGHT The default maximum weight is 100.0.
static double	DEFAULT_MIN_CHANGE The default minimum change is 1.0E-4.
static double	DEFAULT_OVERRELAXATION The default overrelaxation is 1.3.
protected java.util.ArrayList<SuccessiveOverrelaxation.Entry>	entries The entry information that the algorithm keeps.
protected Kernel<? super InputType>	kernel The kernel to use.
protected double	maxWeight The maximum weight for a support vector.
protected double	minChange The minimum change to allow for the algorithm to keep going.
protected double	overrelaxation The overrelaxation parameter.
protected KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>>	result The result categorizer.
protected java.util.LinkedHashMap<InputOutputPair<? extends InputType,? extends java.lang.Boolean>,SuccessiveOverrelaxation.Entry>	supportsMap The mapping of weight objects to non-zero weighted examples (support vectors).
protected double	totalChange The total change on the most recent pass.

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
SuccessiveOverrelaxation() Creates a new instance of SuccessiveOverrelaxation.
SuccessiveOverrelaxation(Kernel<? super InputType> kernel) Creates a new instance of SuccessiveOverrelaxation.
SuccessiveOverrelaxation(Kernel<? super InputType> kernel, double maxWeight, double overrelaxation, double minChange, int maxIterations) Creates a new instance of SuccessiveOverrelaxation.

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 java.util.ArrayList<SuccessiveOverrelaxation.Entry>	getEntries() Gets the data that the algorithm keeps for each training instance.
Kernel<? super InputType>	getKernel() Gets the kernel to use.
double	getMaxWeight() Gets the maximum weight allowed on an instance (support vector).
double	getMinChange() Gets the minimum total weight change allowed for the algorithm to continue.
double	getOverrelaxation() Gets the overrelaxation parameter for the algorithm.
NamedValue<java.lang.Double>	getPerformance() Gets the performance, which is the total change on the last iteration.
KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>>	getResult() Gets the current result of the algorithm.
protected java.util.LinkedHashMap<InputOutputPair<? extends InputType,? extends java.lang.Boolean>,SuccessiveOverrelaxation.Entry>	getSupportsMap() Gets the mapping of examples to weight objects (support vectors).
double	getTotalChange() Gets the total change in weight from the most recent step 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.
protected void	setEntries(java.util.ArrayList<SuccessiveOverrelaxation.Entry> entries) Gets the data that the algorithm keeps for each training instance.
void	setKernel(Kernel<? super InputType> kernel) Sets the kernel to use.
void	setMaxWeight(double maxWeight) Sets the maximum weight allowed on an instance (support vector).
void	setMinChange(double minChange) Sets the minimum total weight change allowed for the algorithm to continue.
void	setOverrelaxation(double overrelaxation) Gets the overrelaxation parameter for the algorithm.
protected void	setResult(KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>> result) Sets the object currently being result.
protected void	setSupportsMap(java.util.LinkedHashMap<InputOutputPair<? extends InputType,? extends java.lang.Boolean>,SuccessiveOverrelaxation.Entry> supportsMap) Gets the mapping of examples to weight objects (support vectors).
protected void	setTotalChange(double totalChange) Gets the total change in weight from the most recent step of the algorithm.
protected boolean	step() Called to take a single step of the learning algorithm.
protected void	update(SuccessiveOverrelaxation.Entry entry) Performs an update step on the given entry using the successive overrelaxation procedure.

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.learning.algorithm.BatchLearner

learn

Methods inherited from interface gov.sandia.cognition.util.CloneableSerializable

clone

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, 1000.

See Also:

Constant Field Values

DEFAULT_MAX_WEIGHT

public static final double DEFAULT_MAX_WEIGHT

The default maximum weight is 100.0.

See Also:

Constant Field Values

DEFAULT_OVERRELAXATION

public static final double DEFAULT_OVERRELAXATION

The default overrelaxation is 1.3.

See Also:

Constant Field Values

DEFAULT_MIN_CHANGE

public static final double DEFAULT_MIN_CHANGE

The default minimum change is 1.0E-4.

See Also:

Constant Field Values

kernel

protected Kernel<? super InputType> kernel

The kernel to use.

maxWeight

protected double maxWeight

The maximum weight for a support vector. Must be greater than zero.

overrelaxation

protected double overrelaxation

The overrelaxation parameter. Must be in (0, 2), exclusive.

minChange

protected double minChange

The minimum change to allow for the algorithm to keep going. If the Total change is below this, then the algorithm will stop. Must be greater than zero.

result

protected KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>> result

The result categorizer.

totalChange

protected double totalChange

The total change on the most recent pass.

entries

protected java.util.ArrayList<SuccessiveOverrelaxation.Entry> entries

The entry information that the algorithm keeps.

supportsMap

protected java.util.LinkedHashMap<InputOutputPair<? extends InputType,? extends java.lang.Boolean>,SuccessiveOverrelaxation.Entry> supportsMap

The mapping of weight objects to non-zero weighted examples (support vectors).

Constructor Detail

SuccessiveOverrelaxation

public SuccessiveOverrelaxation()

Creates a new instance of SuccessiveOverrelaxation.

SuccessiveOverrelaxation

public SuccessiveOverrelaxation(Kernel<? super InputType> kernel)

Creates a new instance of SuccessiveOverrelaxation.

Parameters:

kernel - The kernel function to use.

SuccessiveOverrelaxation

public SuccessiveOverrelaxation(Kernel<? super InputType> kernel,
                                double maxWeight,
                                double overrelaxation,
                                double minChange,
                                int maxIterations)

Creates a new instance of SuccessiveOverrelaxation.

Parameters:

kernel - The kernel function to use.

maxWeight - The maximum weight allowed for a support vector. Must be positive.

overrelaxation - The overrelaxation parameter. Must be in (0, 2), exclusive.

minChange - The minimum change to allow for the algorithm to continue. Must be positive.

maxIterations - The maximum number of iterations to run for.

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.

update

protected void update(SuccessiveOverrelaxation.Entry entry)

Performs an update step on the given entry using the successive overrelaxation procedure. If the entry becomes a support vector, it will be added to the supports data structure.

Parameters:

entry - The entry to update.

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>>>

getKernel

public Kernel<? super InputType> getKernel()

Gets the kernel to use.

Returns:

The kernel to use.

setKernel

public void setKernel(Kernel<? super InputType> kernel)

Sets the kernel to use.

Parameters:

kernel - The kernel to use.

getMaxWeight

public double getMaxWeight()

Gets the maximum weight allowed on an instance (support vector). It must be positive.

Returns:

The maximum weight allowed on an instance.

setMaxWeight

public void setMaxWeight(double maxWeight)

Sets the maximum weight allowed on an instance (support vector). It must be positive.

Parameters:

maxWeight - The maximum weight allowed on an instance.

getOverrelaxation

public double getOverrelaxation()

Gets the overrelaxation parameter for the algorithm. It controls the size of the update step. It must be within the range (0, 2), exclusive.

Returns:

The overrelaxation parameter for the algorithm.

setOverrelaxation

public void setOverrelaxation(double overrelaxation)

Gets the overrelaxation parameter for the algorithm. It controls the size of the update step. It must be within the range (0, 2), exclusive.

Parameters:

overrelaxation - The overrelaxation parameter for the algorithm.

getMinChange

public double getMinChange()

Gets the minimum total weight change allowed for the algorithm to continue. Must be positive.

Returns:

The minimum total weight change allowed for the algorithm to continue.

setMinChange

public void setMinChange(double minChange)

Sets the minimum total weight change allowed for the algorithm to continue. Must be positive.

Parameters:

minChange - The minimum total weight change allowed for the algorithm to continue.

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.

setResult

protected void setResult(KernelBinaryCategorizer<InputType,DefaultWeightedValue<InputType>> result)

Sets the object currently being result.

Parameters:

result - The object currently being result.

getEntries

protected java.util.ArrayList<SuccessiveOverrelaxation.Entry> getEntries()

Gets the data that the algorithm keeps for each training instance.

Returns:

The data kept for each training instance.

setEntries

protected void setEntries(java.util.ArrayList<SuccessiveOverrelaxation.Entry> entries)

Gets the data that the algorithm keeps for each training instance.

Parameters:

entries - The data kept for each training instance.

getSupportsMap

protected java.util.LinkedHashMap<InputOutputPair<? extends InputType,? extends java.lang.Boolean>,SuccessiveOverrelaxation.Entry> getSupportsMap()

Gets the mapping of examples to weight objects (support vectors).

Returns:

The mapping of examples to weight objects.

setSupportsMap

protected void setSupportsMap(java.util.LinkedHashMap<InputOutputPair<? extends InputType,? extends java.lang.Boolean>,SuccessiveOverrelaxation.Entry> supportsMap)

Gets the mapping of examples to weight objects (support vectors).

Parameters:

supportsMap - The mapping of examples to weight objects.

getTotalChange

public double getTotalChange()

Gets the total change in weight from the most recent step of the algorithm.

Returns:

The total change in weight from the most recent step.

setTotalChange

protected void setTotalChange(double totalChange)

Gets the total change in weight from the most recent step of the algorithm.

Parameters:

totalChange - The total change in weight from the most recent step.

getPerformance

public NamedValue<java.lang.Double> getPerformance()

Gets the performance, which is the total change on the last iteration.

Specified by:

getPerformance in interface MeasurablePerformanceAlgorithm

Returns:

The performance of the algorithm.