Support Vector Machines — Complete Derivation

Hard and soft margin, the Lagrangian, every KKT condition interpreted, both duals derived in full, the kernel trick, and the margin generalisation bound.

Classical MLGraduate⏱ 1 day23 min readsvmmarginkktdualitysupport vectors

8 problems →

AssumesLagrangian Duality and the KKT Conditions · Kernels, RKHS and the Representer Theorem · VC Dimension, Sauer's Lemma and Rademacher Complexity

Data $(x_i,y_i)_{i=1}^n$ with $x_i\in\R^d$ and $y_i\in\{\pm1\}$ . A hyperplane is $\{x : \ip{w}{x}+b = 0\}$ , and the classifier is $x\mapsto\sign(\ip{w}{x}+b)$ .

The geometric margin

PropositionThe geometric margin

The Euclidean distance from $x_0$ to the hyperplane $\{\ip wx+b=0\}$ is

\frac{|\ip{w}{x_0}+b|}{\norm w_2},

and for a correctly classified point the signed distance is $\dfrac{y_0(\ip{w}{x_0}+b)}{\norm{w}_2}$ .

Hard margin

We want the hyperplane that maximises the distance to the closest point:

\max_{w,b}\ \min_i \frac{y_i(\ip{w}{x_i}+b)}{\norm w_2}.

PropositionThe hard-margin primal

Assume the data is linearly separable. The margin-maximisation problem is equivalent to

\boxed{\ \min_{w,b}\ \tfrac12\norm w_2^2 \quad\text{subject to}\quad y_i(\ip{w}{x_i}+b)\ge1,\ i=1,\dots,n\ }

which is a strictly convex quadratic program in $w$ (convex, not strict, in $(w,b)$ jointly).

The Lagrangian and the dual

TheoremThe hard-margin SVM dual

With multipliers $\alpha\in\R^n_{\ge0}$ for the $n$ constraints, the dual problem is

\boxed{\ \max_{\alpha\ge0}\ \ \sum_{i=1}^n\alpha_i - \frac12\sum_{i,j}\alpha_i\alpha_jy_iy_j\ip{x_i}{x_j} \quad\text{subject to}\quad \sum_{i=1}^n\alpha_iy_i = 0 \ }

and strong duality holds. The primal solution is recovered as

w^\star = \sum_i\alpha_i^\star y_ix_i, \qquad b^\star = y_k - \ip{w^\star}{x_k}\ \text{ for any } k \text{ with } \alpha_k^\star>0 .

Key idea

Three things happened in that derivation and all three matter.

The dual involves the data only through the inner products $\ip{x_i}{x_j}$ . Replace them with $K(x_i,x_j)$ and the entire derivation goes through verbatim. That is the kernel trick, and it is available because the dual was derived, not as a separate idea.
The dual has $n$ variables and the primal has $d+1$ . For $d\gg n$ — the kernel case, where $d$ may be infinite — the dual is the tractable one.
The equality constraint is an artefact of the unregularised bias. Formulations without a bias term, or with $b$ inside the penalty, have no such constraint. It is worth knowing which convention a piece of software uses.

CorollarySupport vectors

At the optimum, $\alpha_i^\star>0$ only for points with $y_i(\ip{w^\star}{x_i}+b^\star)=1$ — the points lying exactly on the margin. Consequently

w^\star = \sum_{i\in\mathrm{SV}}\alpha_i^\star y_ix_i, \qquad \mathrm{SV} = \{i : \alpha_i^\star>0\},

and deleting any non-support vector from the training set does not change the solution.

Soft margin

Real data is not separable, so relax the constraints with slacks $\xi_i \ge 0$ :

\min_{w,b,\xi}\ \frac12\norm w_2^2 + C\sum_{i=1}^n\xi_i \quad\text{subject to}\quad y_i(\ip w{x_i}+b)\ge 1-\xi_i,\qquad \xi_i\ge0 .

TheoremThe soft-margin SVM dual

The dual is

\boxed{\ \max_{\alpha}\ \sum_i\alpha_i - \frac12\sum_{i,j}\alpha_i\alpha_jy_iy_j\ip{x_i}{x_j} \quad\text{subject to}\quad 0\le\alpha_i\le C,\quad \sum_i\alpha_iy_i=0 \ }

— identical to the hard-margin dual except that the multipliers are boxed above by $C$ . The slack variables do not appear.

PropositionThe three regimes of a training point

At the optimum, exactly one of the following holds for each $i$ :

$\alpha_i^\star$	$\xi_i^\star$	Margin $y_i(\ip{w^\star}{x_i}+b^\star)$	Interpretation
$0$	$0$	$\ge1$	interior, correctly classified with room to spare
$(0,C)$	$0$	$=1$	on the margin — a margin support vector
$C$	$\ge0$	$\le1$	inside the margin or misclassified — a bound support vector

Key idea

This table is the whole behaviour of the algorithm in one place, and every entry was derived from the KKT conditions rather than asserted. Note that $C$ has a clean interpretation: it is the cap on how much influence a single point may have. Small $C$ means no point can pull the boundary far — a wide, soft margin tolerant of violations; large $C$ approaches the hard-margin problem. It is the inverse of a regularisation strength, as the next proposition makes explicit.

PropositionThe soft-margin SVM is regularised hinge-loss minimisation

The soft-margin primal is equivalent to the unconstrained convex problem

\min_{w,b}\ \frac{1}{2}\norm{w}_2^2 + C\sum_{i=1}^n\big[1 - y_i(\ip{w}{x_i}+b)\big]_+, \qquad [u]_+ = \max(u,0) .

The kernel SVM

Since the dual depends on the data only through $\ip{x_i}{x_j}$ , substitute any positive definite kernel:

\max_{0\le\alpha\le C,\ \alpha^\top y=0}\ \sum_i\alpha_i - \frac12\sum_{i,j}\alpha_i\alpha_jy_iy_jK(x_i,x_j),

with decision function

f(x) = \sum_{i\in\mathrm{SV}}\alpha_i^\star y_iK(x_i,x) + b^\star .

Positive definiteness of $K$ is exactly what makes the dual objective concave (the matrix $Q_{ij} = y_iy_jK(x_i,x_j)$ is PSD, being $\diag(y)\mathbf{K}\diag(y)$ ), so the dual remains a convex program. Note also that $f$ is precisely the form the representer theorem predicts, with the additional information that most coefficients are zero.

The margin generalisation bound

TheoremMargin-based generalisation bound

Let $\norm{x_i}_2\le R$ and consider the class $\Fcal_B = \{x\mapsto\ip wx : \norm w_2\le B\}$ . Fix $\gamma>0$ . With probability at least $1-\delta$ , simultaneously for all $f\in\Fcal_B$ ,

\P\big(Y f(X) \le 0\big) \;\le\; \frac1n\sum_{i=1}^n\one\big\{y_if(x_i)\le\gamma\big\} + \frac{2BR}{\gamma\sqrt n} + \sqrt{\frac{\log(1/\delta)}{2n}} .

No dependence on the dimension $d$ .

Key idea

Read the bound. It trades empirical margin error against $BR/(\gamma\sqrt n)$ . Maximising the margin $\gamma$ at fixed $\norm w_2 \le B$ — which is exactly what the SVM primal does — directly minimises the bound's second term. So the algorithm is not a heuristic that happens to have a bound attached; the bound is the justification for the objective.

And the absence of $d$ is the point. A linear classifier in infinite dimension (the kernel case) can still generalise, provided the margin is large relative to $BR$ . This is the precise reason the kernel trick is not automatically a recipe for overfitting.

What this does not say

The bound has real limitations. $\gamma$ must be fixed before seeing the data, or a union bound over a grid of $\gamma$ values must be paid. $B$ and $R$ are typically unknown and must be estimated or bounded a priori. And the bound is usually numerically loose: for realistic $n$ , $B$ , $R$ and $\gamma$ , the term $2BR/(\gamma\sqrt n)$ often exceeds $1$ , making the statement vacuous even when the classifier performs well. It explains the shape of the right objective without certifying the performance of a particular trained model — which is the standard situation in learning theory.

Solving the dual

Algorithm — SMO — sequential minimal optimisation

Observation. The equality constraint $\sum_i\alpha_iy_i=0$ means no single $\alpha_i$ can be changed alone; two must move together.
Select a pair $(i,j)$ violating the KKT conditions most severely.
Solve exactly the two-variable subproblem: with $\alpha_iy_i+\alpha_jy_j$ held fixed, the objective is a one-dimensional concave quadratic on an interval, so it has a closed-form maximiser followed by clipping to the box $[0,C]$ .
Update $b$ from the KKT conditions of the changed pair.
Repeat until the KKT conditions hold to tolerance.

Each step is $O(n)$ (to update the cached decision values) and closed-form, which is why SMO made kernel SVMs practical. There is no need for a general QP solver.

Empirical observationWhy SVMs are no longer the default

Empirical observation — a regularity seen in experiments. No theorem on this page establishes it in general.

SVMs dominated applied machine learning from roughly 1995 to 2012 and are now rare in large-scale settings.

What this does not say

The reasons are computational, not theoretical:

The kernel matrix is $O(n^2)$ to store and the exact solve is $O(n^3)$ ; SMO reduces the constant but not the asymptotics. At $n = 10^7$ this is impossible.
Prediction costs $O(|\mathrm{SV}|)$ kernel evaluations, and the number of support vectors typically grows linearly with $n$ on noisy problems, so inference does not amortise.
Multi-class requires one-versus-rest or one-versus-one reductions rather than a native formulation.
The kernel must be chosen; learning the representation from data, which is what deep networks do, has proved more effective on perceptual tasks.

What has not aged is the mathematics. The margin theory, the duality derivation and the representer-theorem structure are all still correct and still the cleanest example in the subject of an algorithm derived from a generalisation bound. Linear SVMs, trained by primal methods on the hinge loss, remain competitive and widely used for high-dimensional sparse data.

Problems

The geometric marginProof · Foundation · 15 min Derive the hard-margin SVM dualProof · Graduate · 3 hours Derive the soft-margin SVM dualProof · Graduate · 3 hours The three regimes of a training pointProof · Advanced · 30 min The soft-margin SVM is regularised hinge-loss minimisationProof · Intermediate · 30 min Solve a two-point SVM by handNumerical · Beginner · 30 min The SVM margin boundProof · Graduate · 1 hour Implement SMO for the SVM dualCoding · Graduate · 1 day

References

PaperBernhard E. Boser, Isabelle M. Guyon and Vladimir N. Vapnik (1992). A Training Algorithm for Optimal Margin Classifiers
PaperCorinna Cortes and Vladimir Vapnik (1995). Support-Vector NetworksThe soft-margin formulation.
BookBernhard Schölkopf and Alexander J. Smola (2002). Learning with Kernels
PaperJohn C. Platt (1998). Sequential Minimal Optimization
BookIngo Steinwart and Andreas Christmann (2008). Support Vector Machines

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

PropositionThe geometric marginproof includedThe distance from a point to a hyperplane is the functional margin divided by the norm of the weight vector.
PropositionThe hard-margin primal is a well-posed convex programproof includedScaling invariance is removed by the canonical normalisation, giving a strictly convex quadratic program.
TheoremThe hard-margin SVM dualproof includedMaximise the sum of multipliers minus a quadratic form in the labelled Gram matrix, subject to non-negativity and a label-balance constraint.
CorollarySupport vectors and complementary slacknessproof includedOnly points exactly on the margin can have non-zero multipliers, so the solution depends on those points alone.
TheoremThe soft-margin SVM dualproof includedThe same dual with the multipliers box-constrained above by C; the slack variables disappear entirely.
PropositionThe three regimes of a training pointproof includedEvery point is interior, on the margin, or a margin violator, determined by its multiplier.
PropositionThe soft-margin SVM is regularised hinge-loss minimisationproof includedEliminating the slack variables turns the constrained program into an unconstrained convex objective.
TheoremMargin-based generalisation boundproof includedThe risk is controlled by the empirical margin loss plus a term depending on the margin and the data radius, with no dimension dependence.
Empirical observationWhy SVMs are no longer the defaultThe cubic cost in the sample size, not a theoretical deficiency, is what displaced them.

Problems (8)

All problems