# Support Vector Machines

This is a machine learning model.

## Summary

Support Vector Machines are supervised models that take positive and negative instances of classes in some feature space as training instances, and learn a linear decision boundary between the two classes. Unlike probability based methods such as logistic regression that attempt to learn a hyperplane that maximizes the likelihood of the training data, SVMs rely on margin and learn hyperplanes that maximize the distance separation between positive and negative instances. For cases where the training data isn't perfectly separable, they make use of slack variables.

## Formal Description

We are given some training data ${\displaystyle {\mathcal {D}}}$, a set of n points of the form

${\displaystyle {\mathcal {D}}=\left\{(\mathbf {x} _{i},y_{i})\mid \mathbf {x} _{i}\in \mathbb {R} ^{p},\,y_{i}\in \{-1,1\}\right\}_{i=1}^{n}}$

where the yi is either 1 or −1, indicating the class to which the point ${\displaystyle \mathbf {x} _{i}}$ belongs. Each ${\displaystyle \mathbf {x} _{i}}$ is a p-dimensional real vector. We want to find the maximum-margin hyperplane that divides the points having ${\displaystyle y_{i}=1}$ from those having ${\displaystyle y_{i}=-1}$.

We want to choose the ${\displaystyle {\mathbf {w} }}$ and ${\displaystyle b}$ to maximize the margin, or distance between the parallel hyperplanes that are as far apart as possible while still separating the data, i.e.

Minimize (in ${\displaystyle {\mathbf {w} ,b}}$)

${\displaystyle \|\mathbf {w} \|}$

subject to (for any ${\displaystyle i=1,\dots ,n}$)

${\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)\geq 1.\,}$

We can substitute ||w|| with ${\displaystyle {\tfrac {1}{2}}\|\mathbf {w} \|^{2}}$ without changing the solution. This now becomes a quadratic programming problem. Some of this math is obtained from Wikipedia, refer to the corresponding Wikipedia article for more details.

## Training

There exist several specialized algorithms for quickly solving the Quadratic Programming problem that arises from SVMs, mostly reliant on heuristics for breaking the problem down into smaller, more-manageable chunks. A common method is the Sequential Minimal Optimization (SMO) algorithm, which breaks the problem down into 2-dimensional sub-problems that can be solved analytically and runs in cubic time.