The Soft-Margin SVM

Slack variables ξᵢ let points sit inside the margin or on the wrong side at a cost C·Σξᵢ, so the SVM works on non-separable data. Its dual is the hard-margin dual with the box constraint 0 ≤ αᵢ ≤ C. Complementary slackness sorts the points into three groups: outside the margin (α = 0), on it (0 < α < C) and inside it (α = C). The whole thing is hinge-loss minimisation with an L2 penalty.

The hard-margin SVM demands that every training point sit outside the street. One mislabelled point, or two classes that genuinely overlap, makes that impossible, and the optimisation has no solution. Even when separation is possible, insisting on it can force a narrow street that bends around a single unusual point. The soft-margin SVM lets some points break the rule, at a price.

Slack variables

Give each point a slack $\xi_i \ge 0$ that measures how far it falls short of the margin, and relax its constraint to

y_i(w^\top x_i + b) \ge 1 - \xi_i .

$\xi_i = 0$ : the point is on or outside the margin, as before.
$0 < \xi_i \le 1$ : the point is inside the street but still on the correct side.
$\xi_i > 1$ : the point is on the wrong side of the boundary, a training mistake.

Slack is not free. The objective charges for it:

\begin{aligned} \min_{w,\, b,\, \xi}\quad & \tfrac12\lVert w \rVert^2 + C\sum_{i=1}^{n}\xi_i \\ \text{subject to}\quad & y_i(w^\top x_i + b) \ge 1 - \xi_i,\quad \xi_i \ge 0 . \end{aligned}

The cost $C > 0$ sets the trade-off between a wide street (small $\lVert w\rVert$ ) and few violations (small $\sum\xi_i$ ).

Large $C$ : violations are expensive, so the SVM tries hard to classify every training point correctly, at the cost of a narrow margin. As $C \to \infty$ it becomes the hard-margin SVM.
Small $C$ : violations are cheap, so the SVM accepts some of them in exchange for a wide, stable margin.

$C$ is a regularisation parameter, chosen by cross-validation like $\lambda$ in ridge regression (roughly, $C$ plays the role of $1/\lambda$ ).

Two overlapping classes, a boundary with a dashed margin on each side, some points inside the margin and two on the wrong side, each with a short segment showing its slack xi — Soft margin. Points may enter the street or cross the boundary; each pays a slack ξᵢ proportional to how far it goes, weighted by C in the objective.

The dual: a box around α

Repeating the Lagrangian derivation with the slack variables (and their non-negativity constraints, which get multipliers $\beta_i \ge 0$ ), the condition $\partial\mathcal{L}/\partial\xi_i = C - \alpha_i - \beta_i = 0$ forces $\alpha_i = C - \beta_i \le C$ . Everything else is unchanged, so the dual is

\begin{aligned} \max_{\alpha}\quad & \sum_{i}\alpha_i - \frac12\sum_{i,j}\alpha_i\alpha_j\, y_iy_j\, k(x_i, x_j) \\ \text{subject to}\quad & 0 \le \alpha_i \le C, \qquad \sum_i\alpha_iy_i = 0 . \end{aligned}

The only change from the hard margin is the box constraint $\alpha_i \le C$ : no single point may pull on the solution with more than strength $C$ . That is precisely what makes the soft margin robust to outliers. The prediction rule, $f(x) = \sum_i \alpha_iy_i\,k(x_i, x) + b$ , and the use of kernels are exactly as before.

Three kinds of points

Complementary slackness now involves both sets of multipliers: $\alpha_i\big(1 - \xi_i - y_i(w^\top x_i + b)\big) = 0$ and $\beta_i\,\xi_i = (C - \alpha_i)\,\xi_i = 0$ . Working through the cases sorts every training point into one of three groups.

$\alpha_i$	Where the point is	Role
$\alpha_i = 0$	outside the margin, $y_if(x_i) \ge 1$	no influence on the solution
$0 < \alpha_i < C$	exactly on the margin, $y_if(x_i) = 1$ , $\xi_i = 0$	support vector on the street's edge
$\alpha_i = C$	inside the margin or misclassified, $y_if(x_i) \le 1$ , $\xi_i \ge 0$	support vector, a "bounded" violator

Both of the last two groups are support vectors. The points on the edge ( $0 < \alpha_i < C$ ) are the ones used to compute $b$ , since for them $y_i f(x_i) = 1$ exactly. The sparsity of the SVM survives: every point comfortably on its correct side has $\alpha_i = 0$ and could be deleted without changing anything.

Try it yourself

Machine Learning Lab: soft margin →

Pick "Overlap" and slide C from small to large. Watch the street narrow, the number of support vectors fall, and the count of points at the limit α = C change.

The same thing as a loss

Eliminate the slack variables. At the optimum each $\xi_i$ is as small as the constraints allow:

\xi_i = \max\big(0,\; 1 - y_i(w^\top x_i + b)\big).

This is the hinge loss of point $i$ : zero when the point is outside the margin on the correct side, growing linearly as it moves into the street and beyond. Substituting, the soft-margin SVM is

\min_{w,\,b}\; \sum_{i=1}^{n}\max\big(0,\; 1 - y_i(w^\top x_i + b)\big) \;+\; \frac{1}{2C}\lVert w\rVert^2

(after dividing by $C$ ). That is: hinge loss plus an L2 penalty, the same pattern as ridge regression (squared loss plus L2) and regularised logistic regression (log loss plus L2). In this form the SVM can also be trained with (sub)gradient descent, which scales to very large data sets with linear kernels. Module 11 compares the hinge loss with the other classification losses side by side.

Primal or dual?

	Primal	Dual
Variables	$w, b, \xi$ : $d + 1 + n$	$\alpha$ : $n$
Kernels	no (needs explicit features)	yes (only dot products)
Best when	linear SVM, many points, $d$ moderate	non-linear kernels, $n$ moderate
Typical solver	(sub)gradient descent, coordinate descent	SMO (sequential minimal optimisation)

The simulator in the Machine Learning Lab trains its SVMs with a simplified version of SMO, which repeatedly picks two multipliers and solves for them exactly while keeping $\sum_i\alpha_iy_i = 0$ , the standard algorithm behind libraries such as LIBSVM.

MediumSVMSoft margin

A point has yᵢ(w·xᵢ + b) = 0.4 in a trained soft-margin SVM. What are its slack and its αᵢ?

MediumSVMRegularisation

What happens to a soft-margin SVM as C → 0 and as C → ∞?

MediumSVMHinge loss