$$C$$ is a tuning parameter which determines 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 error and hence a more accurate classifier, whereas a higher $$C$$ value is more prone to errors.

University of Michigan - Ann Arbor

Google

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

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


Dual Formulation

In the soft-margin formulation of Support Vector Machines (SVM), the term $$\xi_i$$ is known as a **slack variable**. For a given training observation $$\bar{x}^{(i)}$$:
- If $$\xi_i = 0$$, then $$\bar{x}^{(i)}$$ is correctly classified and lies on or outside 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 stochastic gradient descent (SGD), correctly classified points that lie outside the margin do not affect the update to the parameter $$\bar{\theta}$$. Consequently, only the marginal and misclassified points serve as *support vectors*.

Learn Before

Related