gov.sandia.cognition.learning.algorithm.svm
Class SuccessiveOverrelaxation<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.SuccessiveOverrelaxation<InputType>
Type Parameters:
InputType - The type of the input data.
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>>>, CloneableSerializable, Serializable, 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,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
protected  class SuccessiveOverrelaxation.Entry
          The Entry class represents the data that the algorithm keeps about each training example.
 
Field Summary
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  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  LinkedHashMap<InputOutputPair<? extends InputType,? extends 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
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
protected  void cleanupAlgorithm()
          Called to clean up the learning algorithm's state after learning has finished.
protected  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<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  LinkedHashMap<InputOutputPair<? extends InputType,? extends 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(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(LinkedHashMap<InputOutputPair<? extends InputType,? extends 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 ArrayList<SuccessiveOverrelaxation.Entry> entries
The entry information that the algorithm keeps.


supportsMap

protected LinkedHashMap<InputOutputPair<? extends InputType,? extends 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<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.

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<Collection<? extends InputOutputPair<? extends InputType,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 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(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 LinkedHashMap<InputOutputPair<? extends InputType,? extends 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(LinkedHashMap<InputOutputPair<? extends InputType,? extends 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<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.