decision boundary of support vector machine when data is not linearly separable

Question

Screenshot from this video:

This describes the decision boundary of support vector machine as a optimization problem with two constraints. But it seems to assume that the data points are linearly separable, what if they are not?

Answer 1

For problems which are not linearly separable soft margin SVM is used instead: $$ \begin{align} \min_{\mathbf{w},b,\xi} &\frac{1}{2}\|\mathbf{w}\|^2 + C\sum_{i=1}^{N} \xi_i, \\ \text{s.t. } &y_i\big(\langle \mathbf{w}, \phi(\mathbf{x}_i) \rangle + b)\big) \geq 1 - \xi_i \quad \forall i, \\ &\xi_i \geq 0 \quad \forall i, \end{align}$$ where $\mathbf{w}$ is the separating hyperplane in feature space, $\mathbf{x}_i$ are the training instances, $y_i \in \{-1, +1\}$ the labels and $\phi(\cdot)$ the embedding function. The slack variables $\xi$ allow us to violate constraints (e.g. training instances that lie inside the margin or on the wrong side of the separating hyperplane) but violations are minimized by adding the slack variables to the cost function.

The solution to this problem is a separating hyperplane that does permit some misclassifications. The hyperparameter $C$ is used to balance between training misclassifications and the complexity of the separating hyperplane.