Support Vector Machines

Support Vector Machines are a classifier that allows to build a non linear decision boundary much like multinomial logistic regression, but without having to manually choose the variations of the features ($x^2,\sqrt{x},x^2\sqrt[3]{x}$ etc.).

The main concepts behind how a SVM work are Optimal Margin Classifiers and Kernels.

Optimal Margin Classifier

For now we assume that the dataset is separable, meaning it can exists a linear boundary that separates the examples.

While at its core SVM is a linear classifier, it can become a nonlinear classifier with some kernel tricks, since it will always find a linear separator, but in a higher-dimensional transformed space that allows the model to capture non-linear relationships.

Functional Margin

• Recap on how binary classification works in logistic regression

  $$h_{\theta }(x)=g({\theta }^{T}x)$$

  The classifier predicts $1$ if ${\theta }^{T}x>0$, and $0$ otherwise. This because ${\theta }^{T}x>0\Rightarrow h_{\theta }(x)\ge 0.5$.

  In other words, this means that if $y^{(i)}=1$, we hope that ${\theta }^{T}x\gg 0$; if $y^{(i)}=0$, we hope that ${\theta }^{T}x\ll 0$.

💡 **New notation:**

• Labels $y\in \{-1,+1\}$
• $h$ output values in $\{-1,+1\}$ and not a probability
• $g(z)=\{\begin{array}{llc}1& & \text{if }z\ge 0\\ -1& & \text{otherwise}\end{array}$
• $h_{w,b}(x)=g(w^{T}x+b)$ where $x\in {\mathbb{R}}^n$ and $b\in \mathbb{R}$. (We drop the $x_0=1$ convention)

Functional margin of hyperplane defined by $(w,b)$ with respect to $(x^{(i)},y^{(i)})$

The parameters $w,b$ defines an hyperplane, that in just a higher dimension line that separates the samples.

We define the functional margin as following:

$${\hat{\gamma }}^{(i)}=y^{(i)}(w^T{x}^{(i)}+b)$$

As before for logistic regression:

• If $y^{(i)}=1$, we want and hope that $w^T{x}^{(i)}+b\gg 0$;
• If $y^{(i)}=0$, we want and hope that $w^T{x}^{(i)}+b\ll 0$

And this means that we want and hope that ${\hat{\gamma }}^{(i)}\gg 0$.

We can define the functional margin with respect to the entire training set as:

$$\hat{\gamma }=\underset{i=1}{\overset{n}{\min }}{\hat{\gamma }}^{(i)}$$

There is a problem here, since it’s possible to “cheat” and change the functional margin, without influencing the decision boundary, by just multiplying for the same factor both the parameters $w$ and $b$.

In order to solve this problem, is to normalize the length of the parameters. One way of doing this is forcing the magnitude of the vector to be 1 ($\Vert x\Vert =1$), or by replacing $(w,b)$ with $(\frac{w}{\Vert w\Vert },\frac{b}{\Vert b\Vert })$.

Geometric Margin

The geometric margin describes how much the decision boundary stands apart from the examples. A decision boundary that separates best the points, meaning that doesn’t comes very close to some training samples, has a larger geometric margin hence is better.

More formally, the geometric margin is the euclidean distance between the training sample coordinates and the line (or hyperplane) that represents the decision boundary.

We formally define the geometric margin with respect to a particular training sample $(x^{(i)},y^{(i)})$ as:

$${\gamma }^{(i)}=\frac{y^{(i)}(w^T{x}^{(i)}+b)}{\Vert x\Vert }$$

We can define the geometric margin with respect to entire training set as the worst gemetric margin w.r.t a particular training sample:

$$\gamma =\underset{i=1}{\overset{n}{\min }}{\gamma }^{(i)}$$

We can now see that the geometric margin and the functional margin are correlated:

$${\gamma }^{(i)}=\frac{{\hat{\gamma }}^{(i)}}{\Vert x\Vert }$$

An optimal margin classifier aims to find the parameters $w,b$ that maximise $\gamma$.

In other words, this means to find:

$$\underset{w,b}{\max }\gamma \text{s.t.}\forall i{\gamma }^{(i)}\ge \gamma$$

This problem written like this cannot be solved with algorithms like gradient descend or similar, but can be rewritten in order to be optimized with one of those algorithms:

$$\underset{w,b}{\min }\Vert x{\Vert }^2\text{s.t.}\forall i{\gamma }^{(i)}\ge 0$$

Kernels

Let’s suppose that the parameter $w$ can be expressed as a linear combination between the training examples:

$$w=\sum _{i=1}^n{\alpha }_i{y}^{(i)}{x}^{(i)}\text{where}{x}^{(i)}\in R^k\text{ with k very large}$$

The Representer theorem prove that this is possible without loosing any performances.

---

tags:#ai/machine-learning