Using the Dual formulation of SVM, we can define an implicit feature mapping with kernels. 

Lets talk about what a kernel is, then give a couple examples of popular kernels.

Kernelization

Lagrangians are a tool for constrained optimization problems. Have a look at the video for an intuitive explanation: 

[www.khanacademy.org/math/multivariable-calculus/applications-of-multivariable-derivatives/lagrange-multipliers-and-constrained-optimization/v/the-lagrangian](https://www.khanacademy.org/math/multivariable-calculus/applications-of-multivariable-derivatives/lagrange-multipliers-and-constrained-optimization/v/the-lagrangian) 

Lagrangian Khan Academy Video

When we beginning to kernelize the SVM, we have just got to do some calculus. When solving the soft-margin optimization problem we rely on something called a *Lagrangian*. Watch the despicably helpful khan academy video cited, take a look at the proof, convince yourself of it, then accept the new, *dual* formulation for the soft margin problem:

$$\max_{\alpha} - \frac{1}{2} 
\sum_{i,j=1}^n\alpha_i\alpha_jy^iy^j\vec{x}^i\cdot\vec{x}^j + \sum_{i=1}^n\alpha_i$$
$$\text{subject to } \alpha_i \geq 0 \ \ \forall i \\ \text{ and } \sum_{i=1}^n\alpha_iy^i = 0$$


University of Michigan - Ann Arbor

To relax the optimization problem for Hard-Margin SVM, we allow data points to live inside of the margin for the decision boundary, however we introduce a penalty term $$\xi_i$$. 
We then reformulate the problem as follows: 
$$\min_{\bar{\theta}, b, \xi_i} \frac{1}{2}||\bar{\theta}||^2 + C\sum_{i=1}^N\xi_i$$
$$\text{subject to } y^i (\bar{\theta} \cdot \bar{x}^i + b) \geq 1 - \xi_i, \xi_i > 0 \ \forall i$$

You might notice that this formula is noticeably different than what is shown in the book. However, this reformulation will lead us down a very interesting rabbit hole.


Soft Margin Formulation

The open sourced class includes lecture pages, hands on lectures, discussions, jupyter notebooks... Very useful for very deep theoretical understanding.
[github.com/eecs445-f16/umich-eecs445-f16](https://github.com/eecs445-f16/umich-eecs445-f16) 

EECS 445 Github Notes

Each of these terms are called *slack-variables*. 
For a given training row $$\bar{x}^{(i)}$$, if:

- If $$\xi_i = 0$$, then  $$\bar{x}^{(i)}$$ is correctly classified, and is outside of the margin.
- If $$\xi_i>0$$, then $$\bar{x}^{(i)}$$ violates the margin, and is considered a *support vector*.
- If $$\xi_i > 1$$, then $$\bar{x}^{(i)}$$ is incorrectly classified by the decision boundary. 

When solving this optimization problem with SGD, we notice that correctly classified points that lie outside of the margin don't effect the update to $\bar{\theta}$. This is why the marginal/misclassified points are known as *support-vectors*.

What is $$\xi_i$$?

Dual Formulation

$C$ is a tuning parameter which determiens the threshold of error that the soft margin classifier will tolerate, typically determined via cross-validation. A small $C$ value means a low margin for errorand hence a more accurate classifier, whereas a higher $C$ value is more prone to errors. 

Learn Before

Related

Learn After