smile.classification

Class SVM<T>

java.lang.Object

smile.classification.SVM<T>

Type Parameters:

T - the type of input object.

All Implemented Interfaces:

java.io.Serializable, Classifier<T>, OnlineClassifier<T>, SoftClassifier<T>

public class SVM<T>
extends java.lang.Object
implements OnlineClassifier<T>, SoftClassifier<T>, 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 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.Multiclass The type of multi-class SVMs.
class	SVM.SupportVector Support vector.
static class	SVM.Trainer<T> Trainer for support vector machines.

Constructor Summary

Constructors

Constructor and Description
SVM(MercerKernel<T> kernel, double C) Constructor of binary SVM.
SVM(MercerKernel<T> kernel, double Cp, double Cn) Constructor of binary SVM.
SVM(MercerKernel<T> kernel, double C, double[] weight, SVM.Multiclass strategy) Constructor of multi-class SVM.
SVM(MercerKernel<T> kernel, double C, int k, SVM.Multiclass strategy) Constructor of multi-class SVM.

Method Summary

Modifier and Type	Method and Description
void	finish() Process support vectors until converge.
java.util.List<SVM.SupportVector>	getSupportVectors() Returns the support vectors of binary nonlinear SVM.
boolean	hasPlattScaling() Indicates if Platt scaling is available.
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) Online update the classifier with a new training instance.
void	learn(T x, int y, double weight) Online update the classifier with a new training instance.
int	predict(T x) Predicts the class label of an instance.
int	predict(T x, double[] prob) Predicts the class label of an instance and also calculate a posteriori probabilities.
SVM<T>	setTolerance(double tol) Sets the tolerance of convergence test.
void	trainPlattScaling(T[] x, int[] y) After calling finish, the user should call this method to train Platt Scaling to estimate posteriori probabilities.

Methods inherited from class java.lang.Object

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

Methods inherited from interface smile.classification.Classifier

predict

Constructor Detail

SVM

public SVM(MercerKernel<T> kernel,
           double C)

Constructor of binary SVM.

Parameters:

kernel - the kernel function.

C - the soft margin penalty parameter.

SVM

public SVM(MercerKernel<T> 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(MercerKernel<T> kernel,
           double C,
           int k,
           SVM.Multiclass 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(MercerKernel<T> kernel,
           double C,
           double[] weight,
           SVM.Multiclass 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 SVM<T> setTolerance(double tol)

Sets the tolerance of convergence test.

Parameters:

tol - the tolerance of convergence test.

getSupportVectors

public java.util.List<SVM.SupportVector> getSupportVectors()

Returns the support vectors of binary nonlinear SVM.

learn

public void learn(T x,
                  int y)

Description copied from interface: OnlineClassifier

Online update the classifier with a new training instance. In general, this method may be NOT multi-thread safe.

Specified by:

learn in interface OnlineClassifier<T>

Parameters:

x - training instance.

y - training label.

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.

hasPlattScaling

public boolean hasPlattScaling()

Indicates if Platt scaling is available.

Returns:

true if Platt Scaling is available

trainPlattScaling

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

After calling finish, the user should call this method to train Platt Scaling to estimate posteriori probabilities.

Parameters:

x - training samples.

y - training labels.

predict

public int predict(T x)

Description copied from interface: Classifier

Predicts the class label of an instance.

Specified by:

predict in interface Classifier<T>

Parameters:

x - the instance to be classified.

Returns:

the predicted class label.

predict

public int predict(T x,
                   double[] prob)

Description copied from interface: SoftClassifier

Predicts the class label of an instance and also calculate a posteriori probabilities. Classifiers may NOT support this method since not all classification algorithms are able to calculate such a posteriori probabilities.

Specified by:

predict in interface SoftClassifier<T>

Parameters:

x - the instance to be classified.

prob - the array to store a posteriori probabilities on output.

Returns:

the predicted class label