Soft-Margin SVM

Soft-margin SVM is a type of SVM algorithm that allows for some misclassification of data points to create a more flexible decision boundary. It can handle cases where the data isn’t perfectly separable by a linear boundary. By allowing some misclassification, the algorithm can find a decision boundary that captures the general trend in the data while avoiding overfitting.

What is soft-margin SVM?

Finding a mapping $\phi$ that allows for linear separation with a good margin might prove difficult for certain datasets. Some datasets might not even be capable of linear separation at all. To tackle such situations, it becomes necessary to relax the condition of linear separability with a margin of at least $1$. Our approach involves allowing certain points to violate the hard-margin constraint, but we aim to minimize the total violation as much as possible. This technique is commonly referred to as soft-margin SVM.

Hard-margin vs. soft-margin

Hard-margin and soft-margin SVM differ in how they handle non-linearly separable data. Hard-margin SVM looks for a decision boundary that perfectly separates the classes with the largest possible margin, while soft-margin SVM allows for some misclassification with slack variablesSlack variables allow soft-margin SVM to handle noisy or non-linearly separable data by permitting controlled violations of the margin..

Mathematical formulation

The mathematical formulation for soft-margin SVM introduces slack variables $\bold e=\begin{bmatrix}e_1 & e_2 & \dots & e_n\end{bmatrix}^T$ to relax the constraint $y_i\bold w^T\phi(\bold x_i)\ge 1$ on the decision boundary, allowing for some misclassification.

$$\begin{aligned} \min_{\bold{w,e}} \quad & \|\bold w\|^2 + C\sum_{i=1}^ne_i\\ \textrm{s.t.} \quad & y_i\bold w^T\phi(\bold x_i)\ge 1-e_i \quad & i=1,2,\dots,n\\ \quad & e_j\ge0 \quad & j=1,2,\dots,n \\ \end{aligned}$$ ...