# 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**.

![](/files/-M5-0SGQrZxVKuWZHUes)

### 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.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://vikram-bajaj.gitbook.io/cs-gy-6923-machine-learning/main-4/types-of-machine-learning/supervised-learning/support-vector-machines.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.