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

Even though soft-margin SVM allows us to fit a classifier when a few outliers lay outside of their linearly separable classes, it doesn’t mean that a linear decision boundary should **always** be used. For example consider the below scatterplot. A soft-margin SVM might converge to a find a solution by drawing a diameter to the circle, however this is not at all sufficient, since we will have 50% accuracy. Your classifier is effectively a coin toss. 

We would instead want to fit a boundary that looks like the inner circle in the below image. In comes non-linear Kernel methods to save the day!

img src - [www.mathworks.com/help/stats/support-vector-machines-for-binary-classification.html](https://www.mathworks.com/help/stats/support-vector-machines-for-binary-classification.html) 

Addressing Explicit Non-Linearity

A downside to using the maximal margin hyperplane is that it is extremely sensitive to outliers and may have a tendency to overfit the training data. In this case, it may be beneficial to pick a hyperplane that misclassifies some of the training observations using the support vector classifier (AKA soft margin classifier). Instead of making sure that all the training observations fall on the correct sides of the margin and hyperplane, we can allow for some to be on the incorrect side of the margin, and even the hyperplane. This allows for more accurate classifications for future observations. This increases the bias of our method since it is not as flexible as we allow misclassifications, but it has a lower variance when using new observations.


Misclassification and Support Vector Classifier


The hard margin classifier will not even find a solution for data that is not linearly separable (in its original feature space). In that case we prefer to use a *support vector classifier*, also known as a *soft-margin* classifier. From the below figure, we see that our data is not linearly separable, due to some noisy data points. The soft margin version of SVM will allow us to build a classifier that has <100% training accuracy but will perform well with most of the observations. 


University of Michigan - Ann Arbor

- Hard Margin SVM (Solving the maximum margin separator problem)
- Soft Margin SVM (Allow minimally misclassified points)

Types of SVM

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


The motivation for using SVM’s is to generate a separating hyperplane for a binary dataset, which is **linearly separable**. 

In topological parlance, we are assuming that the positive and negative classes are contained in **disconnected** sets. 

Visually in $$\mathbb{R}^2$$, this means that we can draw a line between all of the data points, such that all of the positive points are on one side of the line, or hyperplane, and all of the negative points are on the other. 

Interestingly, a dataset might not be linearly separable in $$\mathbb{R}^k$$, but might be linearly separable in some $$d > k$$ dimensional space. More on this when talking about kernels.


Learn Before

Related

Learn After