Support Vector Machines

SVMs are also called kernel methods.

Given linearly separable data (with real-valued attributes), we must find a linear discriminant function that separates the positives and negatives (i.e. the classes) and is as far as possible from any example in the data.

Therefore, SVMs aim to maximize the distance of the decision boundary to the closest point in the data set. This distance is called the margin of the hyperplane, and is denoted by $\rho$.

The line that achieves maximum margin is called the maximum margin hyperplane.

Computing the Equation for the Maximum Margin Hyperplane

Consider the data below (positive class: +1, negative class: -1)

$\begin{array}{c|c|c} x_1 & x_2 & r\\1 & 1 & -1\\2 & 2 & +1\\ 1 & 1/2 & -1\\3 & 2 & +1\\2 & 7/4 & +1\\3 & 1 & +1\end{array}$

Let $g(x) = w^Tx + w_0$

The hyperplane equation is g(x) = 0.

The distance from point x to the hyperplane is $\frac{g(x)}{||w||_2}$=$\frac{g(x)}{\sqrt{w_1^2+w_2^2+...+w_d^2}}$ (note that there is no $w_0$ in the denominator).

We need to determine $w, w_0$ such that $w^Tx^t + w_0 > 0$ if $r^t=+1$ and $w^Tx^t + w_0 \leq 0$ if $r^t=-1$.

For our data, we have the following linear constraints:

$w_1 + w_2 + w_0 \leq 0$

$2w_1 + 2w_2 + w_0 > 0$

$w_1 + \frac{1}{2}w_2 + w_0 \leq 0$, and so on.

For the maximum margin hyperplane, we have $\frac{g(x)}{||w||_2} = \rho$

Suppose we scale the coefficients of g, such that the new g(x)=1 (let's call it $g^\sim(x)$) for the points closest to the hyperplane. To do so, we must divide the coefficients of g by a certain quantity. Which quantity to use? Maybe the margin $\rho$?

Now, replace g(x) by $g^\sim(x)$, we have new g(x) = $^+_-1$ for the points closest to the hyperplane. These points are called support vectors. Typically, we have at least 3 support vectors, some of which are on the + side and some are on the - side. The intuiton behind calling them support vectors is that they support the hyperplane in place, and the hyperplane will move if any of them move.

So, for the support vectors, $g(x^t) = +1\,\,if\,\,r^t=+1$ and $g(x^t) = -1\,\,if\,\,r^t=-1$. For other examples:

$g(x^t) > +1 \,\, if \,\,r^t=+1$

$g(x^t) < -1 \,\,if \,\,r^t=-1$

Maximum margin hyperplane on support vectors x satisfies the cannonical form of the maximum margin hyperplane i.e. g(x) = $^+_-1$. So, $\rho = \frac{^+_-1}{||w||_2}$.

Therefore, we must maximize $\frac{^+_-1}{\sqrt{w_1^2+w_2^2+...+w_d^2}}$ subject to the constraints:

$w^Tx+w_0 \geq +1\,\, for\,\,all\,\,x^t\,\,where\,\,r^t=+1$

$w^Tx+w_0 \leq -1\,\, for\,\,all\,\,x^t\,\,where\,\,r^t=-1$

The solution gives the weights of the maximum margin hyperplane.

(to simplify, we minimize $w_1^2+w_2^2+...+w_d^2$).

This is, however, the theoretical computation. SVM softwares compute slightly differently.

SVM softwares often don't directly output the weights. Instead, they output a dual representation of the hyperplane g(x)=0 where g(x)=$w^Tx+w_0$:

Let I be the indices of the support vectors. The SVM software outputs g(x) as a function of the support vectors:

$g(x) = [\sum_{t\in I} (v_t[x^t])^T.x]+v_0$

where $x = \begin{bmatrix}x_1\\x_2\end{bmatrix}$ i.e. the example to be classified.

Suppose the support vectors are $\begin{bmatrix}2\\7/4\end{bmatrix}, \begin{bmatrix}3\\1\end{bmatrix}, \begin{bmatrix}1\\1\end{bmatrix}$say $x^{19}, x^{5}, x^{72}$ respectively, it will output coefficients for each support vector i.e. $v_{19}=3, v_5=9, v_{72}=-4$ respectively, and $v_0=3$(say).

The software will, therefore, output g(x). The coefficients of $x_1, x_2$ in g(x) give the weights $w_1, w_2$ and the constant term will be $w_0$.

So, we have two representtions of the maximum margin hyperplane:

The Primal Representation $g(x) = \sum_{i=1}^d w_ix_i + w_0$

The Dual Representation $g(x) = [\sum_{t\in I} (v_t[x^t])^T.x]+v_0$

($v_t=0$ for all t where $x^t$ is not a support vector).

SVM with Non-Linearly-Separable Data

The above works when the data is linearly-separable. What if the data is not linearly separable?

Say the data follows $x_1^2+x_2^2=1$. We can make the data linearly separable using $z_1=x_1^2, z_2=x_2^2$.

$g(x) = -x_1^2-x_2^2+1\Rightarrow g(z) = -z_1-z_2+1$

Then, the above technique can be used, since the data (in terms of z) is linearly separable.

However, this cannot always be done.

The idea is to map the data to a new space where it becomes linearly separable. This new space is an infinite-dimensional space.

Let $z^t=\phi(x^t)$ where $\phi$ is a mapping function.

Then, we have:

$g(\phi(x))=[\sum_{t\in I} v_t\phi(x^t)].\phi(x^t)+v_0 = [\sum_{t\in I} v_t[\phi(x^t).\phi(x)]] + v_0$

Suppose we have an easy way to compute $K(x,y)=\phi(x).\phi(y)$, for x,y in the original space, K is called a kernel function. Then, we have:

$g(\phi(x)) = [\sum_{t\in I} v_t[K(x^t,x)]]+v_0$ ------------------ (1)

The kernel trick is to avoid computing $\phi$ in the new space, by using a kernel function.

Some commonly-used kernel functions:

• Linear Kernel: $K(x,y)=x.y$
• Polynomial Kernel (of degree d):

  For d=2, $x_1, x_2 \rightarrow x_1^2, x_2^2, x_1x_2, x_1, x_2$

  Consider $K(x,y)=K(x_1,x_2,y_1,y_2)$

  Let $\phi^{new}(x) = \begin{bmatrix}1\\\sqrt{2}x_1\\\sqrt{2}x_2\\\sqrt{2}x_1x_2\\x_1^2\\x_2^2\end{bmatrix}$(this makes it easier to compute), then, $K^{new}(x,y)=\phi^{new}(x).\phi^{new}(y)$=$(1+x.y)^2$

  In general, if the degree is d, the kernel function is $K(x,y)=(1+x.y)^d$

  The hope is that the data becomes linearly separable by a d-degree polynomial in the attributes.

  Another version without lower order terms is $K(x,y)=(x.y)^d$

  d is a tunable parameter.

• Gaussian Kernel (Radial Basis Function RBF Kernel):

  $K(x,y)=e^{-\frac{||x-y||^2}{2\sigma^2}}$ where $||x-y||^2$ is the L2 norm i.e. basically the distance between x and y.

  $\sigma$ is a tunable parameter.

  Using a Gaussian kernel is analogous to computing a distance-weighted sum (similar to KNN). It is the most suitable kernel when the data forms a checker-board pattern. To use a Polynomial kernel for the same data, we would need to use high degree d.

  The Gaussian kernel is the most commonly-used kernel.

  It can also be computed as $K(x,y)=e^{-\gamma ||x-y||^2}$ where $\gamma = \frac{1}{2\sigma^2}$. Small $\sigma$ means a narrow Gaussian, while small $\gamma$ means a flat Gaussian.

In general, we predict + if $g(\phi(x))\geq 0$ and predict - otherwise. (from (1)).

Note: If the number of support vectors returned by the SVM software is not much smaller than the size of the training set, it is a clear sign of overfitting.

Soft-Margin Hyperplanes

The previously discussed hyperplane refers to a hard-margin hyperplane. A soft-margin hyperplane allows examples to be in the margin region, as well as on the wrong side of the hyperplane. To accomodate for the examples that are on the wrong side of the hyperplane, we penalize by the distance of those examples.

For a hard-margin hyperplane, we minimize $||w||^2$ subject to:

$w^Tx^t\geq 1\,\, if\,\, y^t=+1$, and $w^Tx^t \leq -1\,\, if\,\, y^t=-1$ Equivalently, $y^t*(w^Tx^t)\geq 1\,\,for\,\,all\,\,x^t\in X$

For a soft-margin hyperplane, we do the following:

$min\,\, ||w||^2 + \lambda \sum_t \varepsilon^t$, subject to:

$y^t*(w^Tx^t)\geq 1-\varepsilon^t$; $(\varepsilon^t\geq 0 \,\, for\,\, all\,\, t)$

$\lambda$ is the penalty paramater. Note that a large penalty may cause overfitting.