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

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

James, G., Witten, D., Hastie, T., & Tibshirani, R. (2013). An introduction to statistical learning (Vol. 112, pp. 3-7). New York: springer.

An Introduction to Statistical Learning with Applications in R

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$$?

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$$


Learn Before

Related