The present tutorials covers the implementation of Support Vector Machines (SVM) and the notions of kernels.

Download the slides

• Support Vector Machines
• Properties of kernels

In this tutorial, we will cover a more advanced classification algorithm through the use of Support Vector Machines (SVMs). The goal is to gain an intuition of how SVMs works and how to use Gaussian kernel with SVMs to find out the decision boundary. The implementation proposed here follows a simplified version of the Sequential Minimal Optimization (SMO) algorithm for training support vector machines, which is detailed in the following paper. The complete SMO algorithm can then be quite easily implemented following the full paper.

Once again, to simplify your work, we provide the following set of functions that you should find in the 03_Support_Vector_Machines folder

We briefly recall here that the goal of SVMs is that given a set of input vectors \(\mathbf{x}\) separated in two classes (\(\mathbf{x}^{+}\) and \(\mathbf{x}^{-}\), we would like to find the optimal boundary (separating line) between the two classes. To do so, we want to find the separation that gives the maximal margin between the two sets. Hence, let us first try to find a solution to the following problem

By setting the variable \(y_{i}={+}/{-}1\), we can rewrite this problem as

The idea is that for some of the input vectors (called support vectors), we will have an equality in equation (1), where \(\mathbf{w}\cdot\mathbf{x}^{+}+\mathbf{b}=1\) and \(\mathbf{w}\cdot\mathbf{x}^{-}+\mathbf{b}=-1\). By substracting those two equation, we see that we are trying to find a solution to

Therefore, solving the set of equations amounts to find the maximal margin between the support vectors (as they support classification). As seen in the slides, we know that this problem can also be expressed as

Where we can introduce a kernel \(K\left(x_{i},x\right)=\phi\left(x_{i}\right)\cdot\phi\left(x\right)\) in the equation in order to solve non-linear optimization problems. We can use this formulation to perform the predictions of the algorithm and in the first part of this tutorial, we will only consider the linear kernel \(K\left(x_{i},x\right)=x_{i}\cdot x\). Computing the predictions should be performed in the svmPredict function

function pred = svmPredict(model, X)
% Returns a vector of predictions using a trained SVM model (svmTrain). 
% X       : m x n matrix where each example is a row. 
% model   : svm model returned from svmTrain.
% pred    : m x 1 column vector of class predictions ({0, 1} values).

The complete model and all of its corresponding parameters are summarized in the model structure defined as

model = struct;
model.X;            % Values of _support vectors_ in input data
model.y;            % Classes labels of _support vectors_
model.kernel;       % Type of kernel
model.b;            % Value of threshold
model.alphas;       % Value of alphas
model.w;            % Value of vectors

In order to perform learning, we will try to maximize the dual formulation problem expressed as

with \(0\leq \alpha_{i} \leq C\) and \(\sum_{i=1}^{m}{\alpha_{i} y_{i}} = 0\). \(C\) is a chosen regularization hyper-parameter. To ease your work, we will implement only a simplified version of the SMO algorithm which is mainly focused on the optimization aspects. The SMO algorithm selects two \(\alpha\) parameters, \(\alpha_{i}\) and \(\alpha_{j}\) and optimizes the objective value jointly for both these \(\alpha_{i,j}\). Finally it adjusts the \(b\) parameter based on the new \(\alpha_{i,j}\). This process is repeated until the \(\alpha_{i,j}\) converge.

Selecting \(\alpha\). The full SMO algorithm use heuristics to choose which \(\alpha_{i}\) and \(\alpha_{j}\) to optimize (which greatly increase the convergence speed. However, for this simplified version, we will simply iterate on all \(\alpha_{i},i=1,\cdots ,m\) and select a random \(\alpha_{j}\), to perform the joint optimization of \(\alpha_{i}\) and \(\alpha_{j}\)

Optimizing \(\alpha_{i}\) and \(\alpha_{j}\). To jointly optimize the value, we first find bounds \(L\) and \(H\) such that \(L\leq \alpha_{j} \leq H\) holds to satisfy the constraint of the original problem \(0\leq \alpha_{i} \leq C\)

Now we want to find \(\alpha_{j}\) so as to maximize the objective function. It can be shown (as in the original paper) that the optimal \(\alpha_{j}\) is given by

where

\(E_{k}\) defines the error between the prediction of the SVM on the example \(k\) and its desired label. When computing \(\eta\), we can also replace the inner product by a kernel function \(K\). Finally, we clip the value of \(\alpha_{j}\) to lie within the selected bounds.

Now that we have solved \(\alpha_{j}\), we can update the value for \(\alpha_{i}\) through

Computing threshold \(b\). Finally, we can compute the threshold \(b\) to satisfy the original constraints by selecting

where

\(b_{1}=b-E_{i}-y_{i}\left(\alpha_{i}^{(t-1)}-\alpha_{i}\right)\left\langle x_{i},x_{i}\right\rangle -y_{j}\left(\alpha_{j}^{(t-1)}-\alpha_{j}\right)\left\langle x_{i},x_{j}\right\rangle\) \(b_{2}=b-E_{i}-y_{i}\left(\alpha_{i}^{(t-1)}-\alpha_{i}\right)\left\langle x_{i},x_{j}\right\rangle -y_{j}\left(\alpha_{j}^{(t-1)}-\alpha_{j}\right)\left\langle x_{j},x_{j}\right\rangle\)

For the first part of this tutorial, we will compute the main iterations of the algorithm (minimization of the objective function), while relying on a linear kernel. This implies that we will only be able to perform linear discrimination. However, remember that the formulation of the SVMs provide an optimal and (gloriously) convex answer to this problem.

function [model] = svmTrain(X, Y, C, kernelFunction, tol, maxIter)
% Trains an SVM classifier using a simplified SMO algorithm. 
% X       : m x n matrix of m training examples (with n-dimensional features).
% Y       : column vector of class identifiers
% C       : standard SVM regularization parameter
% tol     : tolerance value used for determining equality of floating point numbers. 
% maxIter : number of iterations over the dataset before the algorithm stops.

Expected output [Reveal]

The Gaussian kernel (also called Radial Basis Function (RBF) kernel) allows to perform the optimization of non-linear classification problems. It is defined as

As seen in the slides, the underlying idea is that instead of trying to solve a non-linear separation problem in a given space, we might first transform the space into a target space in which the problem is linearly separable. Therefore, we transform the space through a kernel (which is directly expressed in the minimization problem) and solve the linear separation problem in the target space. Given the starter code and the previous exercise, you should be able to directly plug this kernel inside the svmTrain and svmPredict functions.

Expected output [Reveal]

Now that you have mastered the concept of kernels and updated your code to include the Gaussian kernel, you can augment your classifier and optimizaton problem to include several different kernels as those proposed afterwards.

Polynomial kernel. Intuitively, the polynomial kernel looks not only at the given features of input samples to determine their similarity, but also combinations of these.

Sigmoid (tanh) kernel. This kernel takes two parameters: \(a\) and \(r\). For \(a > 0\), we can view \(a\) as a scaling parameter of the input data, and \(r\) as a shifting parameter that controls the threshold of mapping. For \(a < 0\), the dot-product of the input data is not only scaled but reversed.

As seen in the previous tutorial, we have considered only a binary classification problem (where elements can only belong to one of two classes). This simplifies the work as we simply need to separate the space between two types of points. However, in real-world problems, we usually want to solve multi-class problems with any given number of classes. For this tutorial, we will rely on a simple trick which is to consider that a \(n\)-class problem can simply be restated as \(n\) different binary classification problems. The underlying idea is that each class defines a binary classifier which tells us if a given element is part of this class, or belongs to any of the other classes.