Catalano.MachineLearning.Classification

Class SVM<T>

java.lang.Object

Catalano.MachineLearning.Classification.SVM<T>

Type Parameters:

T - the type of input object.

All Implemented Interfaces:

java.io.Serializable

public class SVM<T>
extends java.lang.Object
implements java.io.Serializable

Support vector machines for classification. The basic support vector machine is a binary linear classifier which chooses the hyperplane that represents the largest separation, or margin, between the two classes. If such a hyperplane exists, it is known as the maximum-margin hyperplane and the linear classifier it defines is known as a maximum margin classifier.

If there exists no hyperplane that can perfectly split the positive and negative instances, the soft margin method will choose a hyperplane that splits the instances as cleanly as possible, while still maximizing the distance to the nearest cleanly split instances.

The nonlinear SVMs are created by applying the kernel trick to maximum-margin hyperplanes. The resulting algorithm is formally similar, except that every dot product is replaced by a nonlinear kernel function. This allows the algorithm to fit the maximum-margin hyperplane in a transformed feature space. The transformation may be nonlinear and the transformed space be high dimensional. For example, the feature space corresponding Gaussian kernel is a Hilbert space of infinite dimension. Thus though the classifier is a hyperplane in the high-dimensional feature space, it may be nonlinear in the original input space. Maximum margin classifiers are well regularized, so the infinite dimension does not spoil the results.

The effectiveness of SVM depends on the selection of kernel, the kernel's parameters, and soft margin parameter C. Given a kernel, best combination of C and kernel's parameters is often selected by a grid-search with cross validation.

The dominant approach for creating multi-class SVMs so is to reduce the single multi-class problem into multiple binary classification problems. Common methods for such reduction is to build binary classifiers which distinguish between (i) one of the labels to the rest (one-versus-all) or (ii) between every pair of classes (one-versus-one). Classification of new instances for one-versus-all case is done by a winner-takes-all strategy, in which the classifier with the highest output function assigns the class. For the one-versus-one approach, classification is done by a max-wins voting strategy, in which every classifier assigns the instance to one of the two classes, then the vote for the assigned class is increased by one vote, and finally the class with most votes determines the instance classification.

References

1. Christopher J. C. Burges. A Tutorial on Support Vector Machines for Pattern Recognition. Data Mining and Knowledge Discovery 2:121-167, 1998.
2. John Platt. Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines.
3. Rong-En Fan, Pai-Hsuen, and Chih-Jen Lin. Working Set Selection Using Second Order Information for Training Support Vector Machines. JMLR, 6:1889-1918, 2005.
4. Antoine Bordes, Seyda Ertekin, Jason Weston and Leon Bottou. Fast Kernel Classifiers with Online and Active Learning, Journal of Machine Learning Research, 6:1579-1619, 2005.
5. Tobias Glasmachers and Christian Igel. Second Order SMO Improves SVM Online and Active Learning.
6. Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a Library for Support Vector Machines.

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	SVM.Strategy The type of multi-class SVMs.

Constructor Summary

Constructors

Constructor and Description
SVM(IMercerKernel kernel, double C) Constructor of binary SVM.
SVM(IMercerKernel kernel, double Cp, double Cn) Constructor of binary SVM.
SVM(IMercerKernel kernel, double C, double[] weight, SVM.Strategy strategy) Constructor of multi-class SVM.
SVM(IMercerKernel kernel, double C, int k, SVM.Strategy strategy) Constructor of multi-class SVM.

Method Summary

Modifier and Type	Method and Description
void	Finish() Process support vectors until converge.
void	Learn(T[] x, int[] y) Trains the SVM with the given dataset for one epoch.
void	Learn(T[] x, int[] y, double[] weight) Trains the SVM with the given dataset for one epoch.
void	Learn(T x, int y)
void	Learn(T x, int y, double weight) Online update the classifier with a new training instance.
int	Predict(T x)
void	setTolerance(double tol) Sets the tolerance of convergence test.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SVM

public SVM(IMercerKernel kernel,
           double C)

Constructor of binary SVM.

Parameters:

kernel - the kernel function.

C - the soft margin penalty parameter.

SVM

public SVM(IMercerKernel kernel,
           double Cp,
           double Cn)

Constructor of binary SVM.

Parameters:

kernel - the kernel function.

Cp - the soft margin penalty parameter for positive instances.

Cn - the soft margin penalty parameter for negative instances.

SVM

public SVM(IMercerKernel kernel,
           double C,
           int k,
           SVM.Strategy strategy)

Constructor of multi-class SVM.

Parameters:

kernel - the kernel function.

C - the soft margin penalty parameter.

k - the number of classes.

SVM

public SVM(IMercerKernel kernel,
           double C,
           double[] weight,
           SVM.Strategy strategy)

Constructor of multi-class SVM.

Parameters:

kernel - the kernel function.

C - the soft margin penalty parameter

weight - class weight. Must be positive. The soft margin penalty of class i will be weight[i] * C.

Method Detail

setTolerance

public void setTolerance(double tol)

Sets the tolerance of convergence test.

Parameters:

tol - the tolerance of convergence test.

Learn

public void Learn(T x,
                  int y)

Learn

public void Learn(T x,
                  int y,
                  double weight)

Online update the classifier with a new training instance. Note that this method is NOT multi-thread safe.

Parameters:

x - training instance.

y - training label.

weight - instance weight. Must be positive. The soft margin penalty parameter for instance will be weight * C.

Learn

public void Learn(T[] x,
                  int[] y)

Trains the SVM with the given dataset for one epoch. The caller may call this method multiple times to obtain better accuracy although one epoch is usually sufficient. After calling this method sufficient times (usually 1 or 2), the users should call Object.finalize() to further process support vectors.

Parameters:

x - training instances.

y - training labels in [0, k), where k is the number of classes.

Learn

public void Learn(T[] x,
                  int[] y,
                  double[] weight)

Trains the SVM with the given dataset for one epoch. The caller may call this method multiple times to obtain better accuracy although one epoch is usually sufficient. After calling this method sufficient times (usually 1 or 2), the users should call Object.finalize() to further process support vectors.

Parameters:

x - training instances.

y - training labels in [0, k), where k is the number of classes.

weight - instance weight. Must be positive. The soft margin penalty parameter for instance i will be weight[i] * C.

Finish

public void Finish()

Process support vectors until converge.

Predict

public int Predict(T x)