07 Soft Margin SVM - Primal and Dual Formulations

Standard “Hard Margin” SVMs can suffer from “overfitting” because they attempt to classify every single training point perfectly. This often leads to fitting the noise in the data rather than the underlying pattern, which degrades performance on unseen data.
By allowing a Soft Margin, the model can ignore certain outliers or noisy points, resulting in a simpler decision boundary that typically generalises better

Slack Variables $(\xi )$

To implement a soft margin, we introduce a slack variable ${\xi }_n$ for every training example $(x_n,y_n)$ where ${\xi }^{(n)}\ge 0$. These variables measure the “error” or “displacement” of a point relative to its ideal position.

Intuition of Slack Values

The value of ${\xi }_n$ tells us exactly where a point lies in relation to the decision boundary and the margin.

• ${\xi }^{(n)}=0$: The point is correctly classified and lies either on or outside the margin.
• $0<{\xi }^{(n)}<1$: The point correctly classified but falls within the margin area.
• ${\xi }^{(n)}=1$: The point sits exactly on the decision boundary.
• ${\xi }^{(n)}>1$: The point is misclassified (on the wrong side of the decision boundary).

Tip

In exam problems, if a point is “correctly classified but inside the margin”, its slack variable $\xi$ must be between $0$ and $1$.

The Primal Optimisation Problem

The goal is to find a balance between a large margin and small classification errors.

The Objective Function

We minimise the following:

$$\arg \underset{w,b\xi }{\min }\left\{\frac{1}{2}\Vert w{\Vert }^2+C\sum _{n=1}^N{\xi }^{(n)}\right\}$$

Subject to

1. $y_n(w^T\varphi (x_n)+b)\ge 1-{\xi }^{(n)}$ (Modified margin constraint)
2. ${\xi }^{(n)}\ge 0$ for all $n$.

The Role of Hyperparameter $C$

$C$ acts as a “penalty” for errors.

• Large $C$: Penalise slack heavily, forcing the model to behave like a Hard Margin SVM with a narrower margin and fewer errors.
• Small $C$: More tolerant of slack, allowing a wider margin even if it means more training points are misclassified or fall within the margin.

The Dual Formulation

To solve the optimisation efficiently (especially with kernels), we convert the primal problems into a dual representation using Lagrange Multipliers $(a_n)$

The Dual Objective

$$\arg \underset{\mathbf{a}}{\max }\tilde{L}(\mathbf{a})=\sum _{n=1}^N{a}^{(n)}-\frac{1}{2}\sum _{n=1}^N\sum _{m=1}^N{a}^{(n)}{a}^{(m)}{y}^{(n)}{y}^{(m)}K(x^{(n)},x^{(m)})$$

Subject to (Box Constraints):

• $0\le a^{(n)}\le C$ for all $n$
• ${\sum }_{n=1}^N{a}_n{y}_n=0$

Important

The primary difference between Hard Margin and Soft Margin duals is the addition of the upper boundary $C$ on the Lagrange multipliers $a_n$

Predictions and Support Vectors

Once the model is trained, we make predictions for a new point $x$ using:

$$h(x)=\sum _{n\in S}{a}^{(n)}{y}^{(n)}k(x,x^{(n)})+b$$

Identifying Support Vectors

In a Soft Margin SVM, Support Vectors $(S)$ are all example where $a_n>0$.

• If $0<a^{(n)}<C$, the point lies exactly on the margin $({\xi }^{(n)}=0)$.
• If $a^{(n)}=C$, the point is a non-margin support vector and lies inside the margin or is misclassified $({\xi }^{(n)}>0)$

Calculating the Bias $b$

The bias term is calculated by averaging the results from support vectors that lie exactly on the margin $(M)$:

$$b=\frac{1}{|N_M|}\sum _{n\in M}\left(y^{(n)}-\sum _{m\in S}{a}^{(m)}{y}^{(m)}K(x^{(n)},x^{(m)})\right)$$

Step-by-Step: From Primal to Dual

1. Define Constraints: Express constraints as $f_i(x)\le 0$. For SVM, these are $1-{\xi }^{(n)}-y_n(w^T\varphi (x_n)+b)\le 0$ and $-{\xi }_n\le 0$.
2. Lagrange Relaxation: Create the Lagrangian function $L(w,b,\xi ,a,\beta )$ by adding constraints multiplied by Lagrange multipliers $a_n$ and ${\beta }_n$.
3. KKT Stationarity: Take derivatives of $L$ with respect to the primal variables ($w,b,\xi$) and set them to zero.

• $\frac{\partial L}{\partial w}=0⟹w=\sum a_n{y}_n\varphi (x_n)$
• $\frac{\partial L}{\partial b}=0⟹\sum a_n{y}_n=0$
• $\frac{\partial L}{\partial {\xi }_n}=0⟹C-a_n-{\beta }_n=0$

4. Substitution: Substitute these back into the Lagrangian to eliminate primal variables, resulting in the dual function $\tilde{L}(a)$