Kernel Support Vector Machine

Kernel Support Vector Machine is a binary classifier which finds a data-separating hyperplane in a Hilbert space induced by a positive definite kernel. The hyperplane is chosen to maximize the margins between the two classes. The loss function that needs to be minimized is:

\[\max_{\bf \alpha} \sum_{i=0}^{N-1} \alpha_i - \sum_{i=0}^{N-1}\sum_{j=0}^{N-1} \alpha_i y_i \alpha_j y_j k({\bf x}_i, {\bf x}_j)\]

subject to:

\[0 \leq \alpha_i \leq C, \sum_{i=0}^{N-1} \alpha_i y_i = 0\]

where \(N\) is the number of training samples, \({\bf x}_i\) are training samples, \(k\) is a kernel, \(\alpha_i\) are the weights, \(y_i\) is the corresponding label where \(y_i \in \{-1,+1\}\) and \(C\) is a pre-specified regularization parameter.

This example uses LibSVM [CL11] as backend, Shogun has many more SVM implementations, see CSVM.

See [ScholkopfS02] and Chapter 6 in [CST00] for a detailed introduction.

Example

Imagine we have files with training and test data. We create CDenseFeatures (here 64 bit floats aka RealFeatures) and CBinaryLabels as

features_train = RealFeatures(f_feats_train)
features_test = RealFeatures(f_feats_test)
labels_train = BinaryLabels(f_labels_train)
labels_test = BinaryLabels(f_labels_test)
features_train = RealFeatures(f_feats_train);
features_test = RealFeatures(f_feats_test);
labels_train = BinaryLabels(f_labels_train);
labels_test = BinaryLabels(f_labels_test);
RealFeatures features_train = new RealFeatures(f_feats_train);
RealFeatures features_test = new RealFeatures(f_feats_test);
BinaryLabels labels_train = new BinaryLabels(f_labels_train);
BinaryLabels labels_test = new BinaryLabels(f_labels_test);
features_train = Modshogun::RealFeatures.new f_feats_train
features_test = Modshogun::RealFeatures.new f_feats_test
labels_train = Modshogun::BinaryLabels.new f_labels_train
labels_test = Modshogun::BinaryLabels.new f_labels_test
features_train <- RealFeatures(f_feats_train)
features_test <- RealFeatures(f_feats_test)
labels_train <- BinaryLabels(f_labels_train)
labels_test <- BinaryLabels(f_labels_test)
features_train = modshogun.RealFeatures(f_feats_train)
features_test = modshogun.RealFeatures(f_feats_test)
labels_train = modshogun.BinaryLabels(f_labels_train)
labels_test = modshogun.BinaryLabels(f_labels_test)
RealFeatures features_train = new RealFeatures(f_feats_train);
RealFeatures features_test = new RealFeatures(f_feats_test);
BinaryLabels labels_train = new BinaryLabels(f_labels_train);
BinaryLabels labels_test = new BinaryLabels(f_labels_test);
auto features_train = some<CDenseFeatures<float64_t>>(f_feats_train);
auto features_test = some<CDenseFeatures<float64_t>>(f_feats_test);
auto labels_train = some<CBinaryLabels>(f_labels_train);
auto labels_test = some<CBinaryLabels>(f_labels_test);

In order to run CLibSVM, we need to initialize a kernel like CGaussianKernel with training features and some parameters like \(C\) and epsilon i.e. residual convergence parameter which is optional.

C = 1.0
epsilon = 0.001
gauss_kernel = GaussianKernel(features_train, features_train, 15)
C = 1.0;
epsilon = 0.001;
gauss_kernel = GaussianKernel(features_train, features_train, 15);
double C = 1.0;
double epsilon = 0.001;
GaussianKernel gauss_kernel = new GaussianKernel(features_train, features_train, 15);
C = 1.0
epsilon = 0.001
gauss_kernel = Modshogun::GaussianKernel.new features_train, features_train, 15
C <- 1.0
epsilon <- 0.001
gauss_kernel <- GaussianKernel(features_train, features_train, 15)
C = 1.0
epsilon = 0.001
gauss_kernel = modshogun.GaussianKernel(features_train, features_train, 15)
double C = 1.0;
double epsilon = 0.001;
GaussianKernel gauss_kernel = new GaussianKernel(features_train, features_train, 15);
auto C = 1.0;
auto epsilon = 0.001;
auto gauss_kernel = some<CGaussianKernel>(features_train, features_train, 15);

We create an instance of the CLibSVM classifier by passing it regularization coefficient, kernel and labels.

svm = LibSVM(C, gauss_kernel, labels_train)
svm.set_epsilon(epsilon)
svm = LibSVM(C, gauss_kernel, labels_train);
svm.set_epsilon(epsilon);
LibSVM svm = new LibSVM(C, gauss_kernel, labels_train);
svm.set_epsilon(epsilon);
svm = Modshogun::LibSVM.new C, gauss_kernel, labels_train
svm.set_epsilon epsilon
svm <- LibSVM(C, gauss_kernel, labels_train)
svm$set_epsilon(epsilon)
svm = modshogun.LibSVM(C, gauss_kernel, labels_train)
svm:set_epsilon(epsilon)
LibSVM svm = new LibSVM(C, gauss_kernel, labels_train);
svm.set_epsilon(epsilon);
auto svm = some<CLibSVM>(C, gauss_kernel, labels_train);
svm->set_epsilon(epsilon);

Then we train and apply it to test data, which here gives CBinaryLabels.

svm.train()
labels_predict = svm.apply_binary(features_test)
svm.train();
labels_predict = svm.apply_binary(features_test);
svm.train();
BinaryLabels labels_predict = svm.apply_binary(features_test);
svm.train 
labels_predict = svm.apply_binary features_test
svm$train()
labels_predict <- svm$apply_binary(features_test)
svm:train()
labels_predict = svm:apply_binary(features_test)
svm.train();
BinaryLabels labels_predict = svm.apply_binary(features_test);
svm->train();
auto labels_predict = svm->apply_binary(features_test);

We can extract \(\alpha\) and \(b\).

alphas = svm.get_alphas()
b = svm.get_bias()
alphas = svm.get_alphas();
b = svm.get_bias();
DoubleMatrix alphas = svm.get_alphas();
double b = svm.get_bias();
alphas = svm.get_alphas 
b = svm.get_bias 
alphas <- svm$get_alphas()
b <- svm$get_bias()
alphas = svm:get_alphas()
b = svm:get_bias()
double[] alphas = svm.get_alphas();
double b = svm.get_bias();
auto alphas = svm->get_alphas();
auto b = svm->get_bias();

Finally, we can evaluate test performance via e.g. CAccuracyMeasure.

eval = AccuracyMeasure()
accuracy = eval.evaluate(labels_predict, labels_test)
eval = AccuracyMeasure();
accuracy = eval.evaluate(labels_predict, labels_test);
AccuracyMeasure eval = new AccuracyMeasure();
double accuracy = eval.evaluate(labels_predict, labels_test);
eval = Modshogun::AccuracyMeasure.new 
accuracy = eval.evaluate labels_predict, labels_test
eval <- AccuracyMeasure()
accuracy <- eval$evaluate(labels_predict, labels_test)
eval = modshogun.AccuracyMeasure()
accuracy = eval:evaluate(labels_predict, labels_test)
AccuracyMeasure eval = new AccuracyMeasure();
double accuracy = eval.evaluate(labels_predict, labels_test);
auto eval = some<CAccuracyMeasure>();
auto accuracy = eval->evaluate(labels_predict, labels_test);

References

Wikipedia: Support_vector_machine

[CL11]C.C. Chang and C.J. Lin. Libsvm: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2(3):27, 2011.
[CST00]N. Cristianini and J. Shawe-Taylor. An Introduction To Support Vector Machines And Other Kernel-Based Learning Methods. Cambridge University Press, 2000.
[ScholkopfS02]B. Schölkopf and A.J. Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.