Chapter 07

Support Vector Machines

The decision boundary that does not just separate the data but separates it with the most breathing room possible. Maximum-margin geometry, the primal/dual quadratic programs and KKT, support vectors and sparsity, the kernel trick, the soft margin with slack and C, and the hinge-loss view that ties SVMs into the regularized-loss family.

Reading: ~46 min Interactive: 3 widgets Source: Bishop §7.1 · Vapnik 1995

What you'll leave with

A clear mental picture of the maximum-margin hyperplane — and why “biggest possible street between the classes” is the right thing to want.
How the perceptron rewrites into instance-based form, and why that rewrite is the doorway to kernels and SVMs.
The primal QP: minimise $\tfrac{1}{2}\|\mathbf{w}\|^2$ subject to $t_n(\mathbf{w}^\top\boldsymbol{\phi}(\mathbf{x}_n)+b) \geq 1$ , derived from “fix the margin, minimise the weights”.
A short Lagrangian primer — enough to follow KKT without an optimization course in your back pocket.
The dual QP and KKT — why most $\alpha_n$ end up at zero, and what the non-zero ones (the support vectors) mean.
The kernel trick: replacing $\boldsymbol{\phi}(\mathbf{x})^\top\boldsymbol{\phi}(\mathbf{x}')$ with $k(\mathbf{x},\mathbf{x}')$ for non-linear classifiers, while staying convex — plus the kernels you will actually use.
Soft-margin SVMs: slack $\xi_n$ , the cost $C$ , and the hinge-loss view that unifies SVMs with ridge and logistic regression.
Generalisation guarantees: the margin bound and the leave-one-out support-vector bound.
The exam-favourite traps: scaling, what “support vector” means precisely, how $C$ trades bias and variance, and why dual $\neq$ primal in dimensionality.

01 · Motivation

Why does this matter?

In Chapter 03 we learned that any line putting the positives on one side and the negatives on the other is a valid linear classifier. The perceptron stops the moment it finds any such line. But “any” is not “good”. Between two clouds of points there are infinitely many separating lines, and most of them are nervous — a single new test point could fall on the wrong side because the boundary skimmed too close to existing data.

Support Vector Machines fix this by asking a sharper question: among all the separating hyperplanes, which one leaves the most breathing room? The answer turns out to be unique, computable from a single convex optimization problem, and — through the kernel trick — capable of drawing decision boundaries of essentially arbitrary shape without losing convexity. Three reasons SVMs occupy the place they do:

Robust by construction

The widest possible margin keeps the classifier as far as possible from every training point. Small measurement noise on a new sample cannot easily flip its prediction — the boundary has already moved out of the way.

A sparse, interpretable model

The trained model depends only on a handful of training points — the support vectors. Throw the rest away and the predictions are identical. Few other methods answer “which examples actually mattered?” so cleanly.

Non-linear without local minima

With kernels, the same algorithm learns curved boundaries — even infinite-dimensional ones — by changing one line of code. And the optimization stays a convex QP: one global minimum, no random seeds.

why

The deeper reason SVMs work

The PAC bounds in Chapter 05 told us that to generalise well we want a hypothesis class with limited capacity. Vapnik’s insight: large-margin classifiers form a smaller effective hypothesis class than arbitrary separators — even if the underlying feature space is huge. Margin is a regulariser, and SVMs are the algorithm that turns this idea into a one-shot quadratic program.

This chapter sits at the confluence of every previous one. From Ch. 03 we keep the linear classifier; from Ch. 05 the VC-dimension argument that motivates large margins; from Ch. 06 we keep kernels — which here are not an afterthought but the engine. Think of the result as kernel ridge classification with a different loss: same mathematical family, sharper geometric story.

02 · Intuition

The idea in plain language

Imagine two clusters of points on a 2-D plot — blue on the left, orange on the right, well separated. Your job is to draw a single straight line that splits them. There are many ways to do it. How do you pick?

The picture below shows two ideas at once. The solid line is the decision boundary. The two dashed lines parallel to it are the margins — the boundary’s safety zones. The width of the corridor between the dashed lines is the margin width; SVMs pick the corridor that is as wide as possible while still being empty in the middle. The points touching the margin are the support vectors: pull any other point inward and the corridor does not move; pull a support vector and the corridor moves with it. They “hold the corridor in place”, and they are the only training points that survive in the final model.

key

Mantra

Widest possible street, with the smallest number of points touching its edges. Everything in this chapter is some rephrasing or generalisation of that one sentence — including the dual formulation, the kernel trick, and even the soft-margin variant.

Why is a wider margin better?

Two arguments — one geometric, one statistical — both pointing the same way:

Robustness. If a future point is a slightly noisy version of a training point, it lands in a small ball around the original. The wider the corridor, the more likely that ball stays entirely on the correct side.
Capacity control. Among all hyperplanes, those achieving a margin of at least $\gamma$ on data bounded in a sphere of radius $R$ form a hypothesis class with VC-dimension bounded by $(R/\gamma)^2$ . Bigger margin $\to$ smaller effective class $\to$ better generalisation (Ch. 05).

From perceptron to kernel — the rewrite that opens the door

Recall the perceptron from Ch. 03: $f(\mathbf{x}_q) = \mathrm{sign}\bigl(\sum_{j} w_j\,\phi_j(\mathbf{x}_q)\bigr)$ . During training, every weight $w_j$ ends up a sum of contributions from the training points it has seen: $w_j = \sum_n \alpha_n t_n \phi_j(\mathbf{x}_n)$ , where $\alpha_n$ counts how many times point $n$ was used. Plug this into the prediction and swap the order of summation:

f(\mathbf{x}_q) \;=\; \mathrm{sign}\!\left[\sum_{n=1}^{N} \alpha_n t_n \bigl(\boldsymbol{\phi}(\mathbf{x}_n)^\top \boldsymbol{\phi}(\mathbf{x}_q)\bigr)\right]

The sum over features has become a sum over training points. The model now talks about similarities between examples, not about feature weights.

Two huge things just happened. First, the inner product $\boldsymbol{\phi}(\mathbf{x}_n)^\top \boldsymbol{\phi}(\mathbf{x}_q)$ is the only place the features appear — replace it with any valid kernel $k(\mathbf{x}_n, \mathbf{x}_q)$ and the algorithm keeps working, even if $\boldsymbol{\phi}$ lives in an infinite-dimensional space (Ch. 06). Second, if most $\alpha_n = 0$ , the prediction depends only on a sparse subset of the training data — exactly the support-vector picture. SVMs are what you get when you combine this rewrite with the maximum-margin criterion.

tip

An SVM has three pieces, and that is it

A subset of training points — the support vectors.
A weight $\alpha_n$ for each of them.
A kernel $k(\mathbf{x},\mathbf{x}')$ that measures similarity.

The prediction is just a weighted vote of how similar the query is to each support vector. It is instance-based learning at heart — only the choice of which instances matter is found by optimisation instead of being memorised wholesale.

03 · Formalism

Definitions and equations

Let the training set be $\{ (\mathbf{x}_n, t_n) \}_{n=1}^N$ with binary labels $t_n \in \{-1, +1\}$ — note: not $\{0, 1\}$ like in logistic regression. This convention lets us multiply labels into expressions and simplify nicely.

The decision function

We use a linear model in some (possibly transformed) feature space, exactly like Ch. 03:

Predictor

y(\mathbf{x}) \;=\; \mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}) + b, \qquad \text{predict } \mathrm{sign}\,y(\mathbf{x}).

The decision boundary is $y(\mathbf{x}) = 0$ , a hyperplane in feature space. The vector $\mathbf{w}$ is its normal; $b$ is the offset that shifts it away from the origin.

The functional and geometric margin

Two related notions, and the distinction trips students up every single year:

Functional margin: $\hat{\gamma}_n = t_n\,(\mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}_n) + b)$ . Positive when classification is correct; rescales with $(\mathbf{w}, b)$ .
Geometric margin: $\gamma_n = \dfrac{t_n\,(\mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}_n) + b)}{\|\mathbf{w}\|}$ . The signed Euclidean distance from $\mathbf{x}_n$ to the hyperplane — invariant to rescaling $(\mathbf{w}, b)$ .

The geometric margin of the whole dataset is the smallest such distance:

\gamma \;=\; \min_{n=1,\dots,N}\;\frac{t_n\,(\mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}_n) + b)}{\|\mathbf{w}\|}.

The maximum-margin hyperplane maximises this $\gamma$ . Written directly it is messy:

Max-margin (direct)

\mathbf{w}^*, b^* \;=\; \arg\max_{\mathbf{w}, b}\; \left\{\frac{1}{\|\mathbf{w}\|}\,\min_{n}\bigl(t_n(\mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}_n) + b)\bigr)\right\}

Outer max over the parameters, inner min over the data. The $1/\|\mathbf{w}\|$ converts the functional margin into a Euclidean distance.

The rescaling trick → the clean primal

$(\mathbf{w}, b)$ and $(c\mathbf{w}, c b)$ for any $c > 0$ define the same hyperplane, so we are free to choose the scale. Rescale so that the closest training point has functional margin exactly 1: $\min_n t_n(\mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}_n) + b) = 1$ . Then $\gamma = 1/\|\mathbf{w}\|$ , and maximising the margin is the same as minimising $\|\mathbf{w}\|$ . This is the SVM primal in its standard form:

Hard-margin primal

\begin{aligned} &\min_{\mathbf{w}, b}\quad \tfrac{1}{2}\,\|\mathbf{w}\|^2 \\ &\text{subject to}\quad t_n\bigl(\mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}_n) + b\bigr) \;\geq\; 1, \quad n = 1, \dots, N. \end{aligned}

The factor ½ is cosmetic — it cancels under differentiation. The objective is convex (a paraboloid), the constraints linear, the feasible region a convex polytope. So this is a convex quadratic program with a unique global minimum, provided the data are linearly separable.

A 60-second primer on constrained optimization

The primal is constrained and we want something we can differentiate. The standard tool is the Lagrangian. Two facts to carry into the rest of the chapter:

map

Constrained optimization in one paragraph

To minimise $f(\mathbf{w})$ subject to inequality constraints $g_n(\mathbf{w}) \leq 0$ , build the Lagrangian $L(\mathbf{w}, \boldsymbol{\alpha}) = f(\mathbf{w}) + \sum_n \alpha_n g_n(\mathbf{w})$ with multipliers $\alpha_n \geq 0$ . At the optimum, the KKT conditions hold: stationarity ( $\nabla_{\mathbf{w}} L = 0$ ), primal feasibility ( $g_n \leq 0$ ), dual feasibility ( $\alpha_n \geq 0$ ), and crucially complementary slackness $\alpha_n g_n(\mathbf{w}^*) = 0$ : for each constraint, either it is tight ( $g_n = 0$ , boundary touched) or its multiplier is zero ( $\alpha_n = 0$ , constraint slept through the whole problem). One of them must vanish, never both non-zero.

In our SVM, the constraints are $g_n(\mathbf{w}, b) = 1 - t_n(\mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}_n)+b) \leq 0$ . Complementary slackness will tell us that, at the optimum, only the points on the margin (where the constraint is tight) get non-zero $\alpha_n$ . Everything else — the support-vector property, the sparsity, the kernel trick — flows from this single observation.

The Lagrangian and the dual

One multiplier $\alpha_n \geq 0$ per constraint:

Lagrangian

L(\mathbf{w}, b, \boldsymbol{\alpha}) \;=\; \tfrac{1}{2}\|\mathbf{w}\|^2 \;-\; \sum_{n=1}^{N} \alpha_n\!\left[t_n\bigl(\mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}_n) + b\bigr) \;-\; 1\right].

Standard form for a minimisation with inequality constraints $g_n \leq 0$ is $L = f + \sum_n \alpha_n g_n$ . Here $g_n = 1 - t_n(\mathbf{w}^\top\boldsymbol{\phi}(\mathbf{x}_n)+b)$ , so $\alpha_n g_n = -\alpha_n[t_n(\cdots)-1]$ , explaining the minus sign. Each $\alpha_n \geq 0$ is a “tension” pulling the boundary away from the $n$ -th constraint.

Setting $\partial L / \partial \mathbf{w} = 0$ and $\partial L / \partial b = 0$ gives two stationarity conditions:

\mathbf{w} \;=\; \sum_{n=1}^{N} \alpha_n t_n \boldsymbol{\phi}(\mathbf{x}_n), \qquad \sum_{n=1}^{N} \alpha_n t_n \;=\; 0.

The first equation is profound: the optimal weight vector is a linear combination of the (transformed) training points, weighted by signed dual variables. This is the form that makes the kernel trick work. Substitute it back into $L$ and we obtain the dual:

Hard-margin dual

\begin{aligned} &\max_{\boldsymbol{\alpha}}\;\; \tilde{L}(\boldsymbol{\alpha}) \;=\; \sum_{n=1}^{N}\alpha_n \;-\; \tfrac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}\alpha_n \alpha_m\, t_n t_m\, k(\mathbf{x}_n, \mathbf{x}_m) \\ &\text{subject to}\quad \alpha_n \geq 0, \;\; n = 1,\dots,N, \quad \text{and}\quad \sum_{n=1}^{N} \alpha_n t_n = 0. \end{aligned}

Crucial fact: features have vanished. The data only appear through the kernel $k(\mathbf{x}_n, \mathbf{x}_m) = \boldsymbol{\phi}(\mathbf{x}_n)^\top \boldsymbol{\phi}(\mathbf{x}_m)$ . Choose any Mercer kernel and the algorithm just works — even when $\boldsymbol{\phi}$ is infinite-dimensional.

Primal vs dual — which one do you actually solve?

The primal has $D + 1$ variables (one per feature, plus the bias). The dual has $N$ variables (one per training point). Two regimes:

Solve the primal when

$D \ll N$ , and you use a linear kernel (or none). The decision function $y(\mathbf{x}) = \mathbf{w}^\top \mathbf{x} + b$ evaluates in $O(D)$ regardless of how many training points you had. Linear solvers like LIBLINEAR are primal-based.

Solve the dual when

You want a non-linear kernel — full stop. The primal involves $\boldsymbol{\phi}(\mathbf{x})$ explicitly; if $\boldsymbol{\phi}$ is high- or infinite-dimensional (RBF) you simply cannot write $\mathbf{w}$ down. The dual only ever evaluates $k(\mathbf{x}_n, \mathbf{x}_m)$ , which is finite and cheap. LIBSVM, SMO and friends are dual-based.

Either way, both problems have the same global optimum — strong duality holds because the primal is a convex QP with linear constraints — so the choice is purely about computational convenience.

KKT conditions and the meaning of support vectors

Because the primal has inequality constraints, the optimum satisfies the Karush–Kuhn–Tucker conditions:

\alpha_n \geq 0, \qquad t_n\bigl(\mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}_n) + b\bigr) - 1 \geq 0, \qquad \alpha_n\Bigl[t_n\bigl(\mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}_n) + b\bigr) - 1\Bigr] = 0.

The third equation is complementary slackness. For each point either the multiplier vanishes or the constraint is active — never both non-zero.

That last condition splits the training set into two camps:

$\alpha_n = 0$ — the point is strictly outside the margin. It does not contribute to $\mathbf{w}$ . Throw it away and the model is unchanged.
$\alpha_n > 0$ — the point lies exactly on the margin, $t_n y(\mathbf{x}_n) = 1$ . These are the support vectors.

The prediction for a new point is a weighted vote of similarities to the support vectors only:

Prediction

y(\mathbf{x}) \;=\; \sum_{n \in \mathcal{S}} \alpha_n t_n\, k(\mathbf{x}, \mathbf{x}_n) + b, \qquad b \;=\; \frac{1}{|\mathcal{S}|}\sum_{n \in \mathcal{S}}\left[t_n - \sum_{m \in \mathcal{S}} \alpha_m t_m\, k(\mathbf{x}_n, \mathbf{x}_m)\right].

$\mathcal{S}$ is the set of support-vector indices. The bias $b$ is recovered by averaging over support vectors using the fact that they satisfy $t_n y(\mathbf{x}_n) = 1$ exactly.

A short tour of kernels

Any function $k(\mathbf{x}, \mathbf{x}')$ writable as $\boldsymbol{\phi}(\mathbf{x})^\top \boldsymbol{\phi}(\mathbf{x}')$ for some feature map $\boldsymbol{\phi}$ is a valid kernel. The technical test is Mercer’s condition: the $N \times N$ Gram matrix $K_{nm} = k(\mathbf{x}_n, \mathbf{x}_m)$ must be symmetric and positive semi-definite for every finite sample. When this holds, the dual QP stays convex and the kernel is a drop-in replacement for the inner product. Three kernels cover the vast majority of practical use:

Linear

$k(\mathbf{x}, \mathbf{x}') = \mathbf{x}^\top \mathbf{x}'$ . No transformation — just the dot product. Use when data is already separable in input space, or when $D$ is huge (e.g. bag-of-words text). Cheapest and easiest to interpret: $\mathbf{w}$ lives in the same space as the data.

Polynomial

$k(\mathbf{x}, \mathbf{x}') = (1 + \mathbf{x}^\top \mathbf{x}')^d$ . Lifts into the space of all monomials up to degree $d$ — so the boundary can be a degree- $d$ polynomial in the original features. Good for explicit feature interactions. The “+1” includes lower-degree terms.

RBF (Gaussian)

$k(\mathbf{x}, \mathbf{x}') = \exp(-\gamma\,\|\mathbf{x}-\mathbf{x}'\|^2)$ . The default workhorse. Implicitly maps into an infinite-dimensional space. The width $\gamma$ controls how “local” the similarity is: small $\gamma$ $\to$ smooth boundaries; large $\gamma$ $\to$ tightly localised, risks overfitting.

how

How to choose

Default to RBF and cross-validate $C$ and $\gamma$ on a 2-D log-spaced grid (the textbook recipe). Use Linear when $D \gg N$ — there is no benefit in lifting further, and it scales much better. Use Polynomial when domain knowledge tells you feature interactions of a known degree matter (e.g. degree-2 for physics features that combine multiplicatively). The kernel is a prior about what “similar” means — choose it like you would choose a model class.

Soft margin — letting some points misbehave

Real data is rarely perfectly separable. Two points overlap, a stray outlier sits on the wrong side — and the hard-margin problem becomes infeasible. The fix: introduce one non-negative slack variable $\xi_n \geq 0$ per point, allowing it to violate the margin condition, and penalise the total violation:

Soft-margin primal

\begin{aligned} &\min_{\mathbf{w}, b, \boldsymbol{\xi}}\quad \tfrac{1}{2}\|\mathbf{w}\|^2 \;+\; C\sum_{n=1}^{N}\xi_n \\ &\text{subject to}\quad t_n\bigl(\mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}_n) + b\bigr) \;\geq\; 1 - \xi_n,\qquad \xi_n \geq 0. \end{aligned}

$C > 0$ controls the cost of violating the margin. Large $C$ $\to$ almost hard margin (low bias, high variance). Small $C$ $\to$ wider margin tolerating more violations (high bias, low variance). $C$ is chosen by cross-validation (Ch. 04).

Repeating the Lagrangian dance with slacks yields the soft-margin dual — identical to the hard-margin dual except that the multipliers are now bounded:

Soft-margin dual

\begin{aligned} &\max_{\boldsymbol{\alpha}}\;\; \sum_{n=1}^{N} \alpha_n - \tfrac{1}{2}\sum_{n,m} \alpha_n \alpha_m t_n t_m\, k(\mathbf{x}_n, \mathbf{x}_m) \\ &\text{subject to}\quad 0 \leq \alpha_n \leq C, \quad \sum_{n} \alpha_n t_n = 0. \end{aligned}

Compare with the hard-margin dual: only one change — the box constraint $\alpha_n \leq C$ . The $C$ cap is the entire mathematical incarnation of “we tolerate some violations”.

The KKT analysis now classifies each training point into one of three regimes:

Not a support vector — outside the margin, safe

The point sits strictly on the correct side, beyond the margin. The constraint is not active and the slack is zero. $\alpha_n = 0,\ \xi_n = 0$

Margin support vector — sitting on the margin

The point lies exactly on the dashed line. It actively shapes the boundary but does not violate it. Used to compute the bias $b$ . $0 < \alpha_n < C,\ \xi_n = 0$

Bounded support vector — inside or misclassified

The constraint is violated; the multiplier is saturated at $C$ . If $\xi_n \leq 1$ the point is on the correct side but inside the corridor; if $\xi_n > 1$ it is on the wrong side outright. $\alpha_n = C,\ \xi_n > 0$

view

Soft margin in one sentence

“Maximise the margin and minimise the total margin violation, balanced by $C$ .” In Ch. 04 language this is structural risk minimisation: the $\|\mathbf{w}\|^2$ term is the capacity penalty, the $C\sum \xi_n$ term is the empirical risk, and $C$ is the bias–variance dial.

The hinge-loss view — SVMs as regularized loss minimization

Here is the perspective that ties SVMs into the rest of supervised learning. Look again at the soft-margin slack: $\xi_n = \max(0,\; 1 - t_n y(\mathbf{x}_n))$ . Why the max? Because the constraint is $\xi_n \geq 1 - t_n y(\mathbf{x}_n)$ and $\xi_n \geq 0$ , and the objective wants $\xi_n$ as small as possible — so it picks the larger of zero and the gap. That function has a name:

Hinge loss

\ell_{\text{hinge}}\bigl(y(\mathbf{x}_n),\, t_n\bigr) \;=\; \max\bigl(0,\; 1 - t_n\, y(\mathbf{x}_n)\bigr).

Zero when the point is correctly classified with margin at least 1; grows linearly as the point drifts inside the margin or across it.

Substituting back, the entire soft-margin SVM becomes the unconstrained minimisation

SVM = regularizer + hinge loss

\min_{\mathbf{w}, b}\;\; \underbrace{\tfrac{1}{2}\|\mathbf{w}\|^2}_{\text{capacity penalty}} \;+\; C \sum_{n=1}^{N}\underbrace{\max\!\bigl(0,\; 1 - t_n(\mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}_n) + b)\bigr)}_{\text{hinge loss per point}}.

Same problem, no slacks. The structure is identical to ridge regression: a quadratic regularizer plus a per-example loss, balanced by a hyperparameter.

This view unlocks three things at once:

SVMs are not exotic. They sit on the same shelf as ridge regression (squared loss + L2) and L2-regularized logistic regression (log loss + L2). Only the loss differs.
The hinge is why SVMs are sparse. Unlike the squared or log losses, the hinge is exactly zero for any point comfortably on the right side. Those points contribute nothing to the gradient — and nothing to the model. Compare to logistic regression, which gives every point a non-zero (if tiny) say.
$C$ is the inverse of the more familiar $\lambda$ . Divide by $C$ and the equivalent form is $\tfrac{1}{2C}\|\mathbf{w}\|^2 + \sum_n \ell_{\text{hinge}}(\cdots)$ . Large $C$ $\leftrightarrow$ small $\lambda$ $\leftrightarrow$ weak regularization, narrow margin. Small $C$ $\leftrightarrow$ large $\lambda$ $\leftrightarrow$ strong regularization, wide margin.

You can play with the hinge against the 0/1, squared, and logistic losses in Hands-on 3 below.

04 · Worked example

A four-point hard-margin SVM, by hand

We solve a tiny SVM end to end, getting explicit numbers for $\mathbf{w}$ , $b$ , $\boldsymbol{\alpha}$ , and the margin. The numbers are friendly enough to verify each step on paper. Four points in two dimensions, two per class:

$n$	$\mathbf{x}_n$	$t_n$
1	$(3, 3)$	$+1$
2	$(3, 4)$	$+1$
3	$(1, 1)$	$-1$
4	$(0, 0)$	$-1$

The positives sit up to the right, the negatives down to the left — clearly linearly separable. We use the linear kernel $k(\mathbf{x}, \mathbf{x}') = \mathbf{x}^\top \mathbf{x}'$ , no feature map.

Worked example Solving the four-point SVM

1 · Guess the geometry first

Eyeball the four points. The two classes are stretched along the line $x_2 = x_1$ . The natural separator runs perpendicular to it — so $\mathbf{w}$ points along $(1,1)$ . The closest pair across the gap is $(3,3)$ and $(1,1)$ ; their midpoint is $(2,2)$ , so the boundary likely passes through $(2,2)$ with normal $(1,1)$ , i.e. the hyperplane $x_1 + x_2 = 4$ .

2 · Identify the active constraints

Conjecture that the support vectors are the two closest points across the gap, $\mathbf{x}_1 = (3,3)$ and $\mathbf{x}_3 = (1,1)$ . For these the constraint is active: $t_n(\mathbf{w}^\top \mathbf{x}_n + b) = 1$ . Write $\mathbf{w} = (w, w)$ (forced by symmetry) and solve. From $\mathbf{x}_1 = (3,3),\, t_1 = +1$ :

+1 \cdot (3w + 3w + b) \;=\; 1 \quad\Longrightarrow\quad 6w + b \;=\; 1.

From $\mathbf{x}_3 = (1,1),\, t_3 = -1$ :

-1 \cdot (w + w + b) \;=\; 1 \quad\Longrightarrow\quad 2w + b \;=\; -1.

3 · Solve for w and b

Subtracting the second from the first:

4w \;=\; 2 \quad\Longrightarrow\quad w = \tfrac{1}{2}, \qquad b = -1 - 2w = -2.

So $\mathbf{w} = (\tfrac{1}{2}, \tfrac{1}{2}),\; b = -2$ , and the decision function is

y(\mathbf{x}) \;=\; \tfrac{1}{2}x_1 + \tfrac{1}{2}x_2 - 2.

4 · Verify the non-active points

For $\mathbf{x}_2 = (3,4),\, t_2 = +1$ : $y(\mathbf{x}_2) = 1.5 + 2 - 2 = 1.5$ , and $t_2 y(\mathbf{x}_2) = 1.5 \geq 1$ . ✓ For $\mathbf{x}_4 = (0,0),\, t_4 = -1$ : $y(\mathbf{x}_4) = -2$ , and $t_4 y(\mathbf{x}_4) = +2 \geq 1$ . ✓ Both non-active constraints are satisfied with room to spare — confirming $\mathbf{x}_2$ and $\mathbf{x}_4$ are not support vectors and get $\alpha_n = 0$ .

5 · Compute the margin

The geometric margin is $1/\|\mathbf{w}\|$ . Here $\|\mathbf{w}\| = \sqrt{(\tfrac{1}{2})^2 + (\tfrac{1}{2})^2} = \tfrac{1}{\sqrt{2}}$ , so the margin is $\gamma = 1/\|\mathbf{w}\| = \sqrt{2}$ . The corridor width is $2\gamma = 2\sqrt{2} \approx 2.83$ . Check: the distance from $(1,1)$ to $x_1 + x_2 = 4$ is $|1+1-4|/\sqrt{2} = \sqrt{2}$ . ✓

6 · Recover α from the dual

Only $\alpha_1$ and $\alpha_3$ can be non-zero. Stationarity $\mathbf{w} = \sum_n \alpha_n t_n \mathbf{x}_n$ gives

(\tfrac{1}{2}, \tfrac{1}{2}) \;=\; \alpha_1 (+1)(3,3) + \alpha_3 (-1)(1,1) \;=\; (3\alpha_1 - \alpha_3,\; 3\alpha_1 - \alpha_3),

so $3\alpha_1 - \alpha_3 = \tfrac{1}{2}$ . The dual constraint $\sum_n \alpha_n t_n = 0$ gives $\alpha_1 - \alpha_3 = 0$ , hence $\alpha_1 = \alpha_3$ . Combined, $2\alpha_1 = \tfrac{1}{2}$ , so $\alpha_1 = \alpha_3 = \tfrac{1}{4}$ and $\alpha_2 = \alpha_4 = 0$ .

$n$	$\mathbf{x}_n$	$t_n$	$\alpha_n$	Role
1	$(3, 3)$	$+1$	$\tfrac14$	margin SV
2	$(3, 4)$	$+1$	$0$	not SV
3	$(1, 1)$	$-1$	$\tfrac14$	margin SV
4	$(0, 0)$	$-1$	$0$	not SV

map

Map the example back to the formalism

Decision function: $y(\mathbf{x}) = \tfrac{1}{2}x_1 + \tfrac{1}{2}x_2 - 2$ .
Margin: $\gamma = \sqrt{2}$ .
Support vectors: $\mathbf{x}_1$ and $\mathbf{x}_3$ , with $\alpha_1 = \alpha_3 = \tfrac{1}{4}$ .
Two of four training points contribute to the model. Throw away the rest and the predictions are identical — that is the sparsity property.

In larger problems you cannot guess the active set. The standard algorithm is SMO (Sequential Minimal Optimization): update two $\alpha_n$ at a time while respecting the equality constraint $\sum_n \alpha_n t_n = 0$ . Updating one alpha alone would break this constraint — two is the smallest feasible step. Hands-on 1 runs exactly this solver on a few preset datasets.

05 · Visual explanation

The geometry of the margin

One figure earns its keep three times: the same diagram explains the primal, the dual, and the soft-margin extension. Read it slowly.

A · Hard-margin geometry. Three parallel lines. The middle one is $y(\mathbf{x}) = 0$ — the decision boundary. The two dashed lines are $y(\mathbf{x}) = \pm 1$ — where the functional margin equals $\pm 1$ under the rescaling we imposed. The normal $\mathbf{w}$ points perpendicular to the boundary, from the negative side to the positive side. The corridor width is $2/\|\mathbf{w}\|$ , so minimising $\|\mathbf{w}\|$ really does widen it. Only the points sitting on the dashed lines are support vectors; delete the rest and the corridor does not move. Explore this live in Hands-on 1.

B · Soft margin — the same picture with slack. Mix the classes slightly and some points end up where they “should not” be. Each carries a slack $\xi_n$ — the distance from where it sits to where it would need to be to satisfy the hard margin. Points with $\xi < 1$ are on the correct side but inside the corridor; points with $\xi > 1$ are misclassified. The objective pays $C\xi_n$ for each. Adding slack invariably grows the SV set: the old margin SVs stay, and the new violating points join at $\alpha_n = C$ .

C · The $C$ dial. $C$ acts on the soft margin the way $\lambda$ acts on ridge regression — only in reverse. Large $C$ means “violations are expensive”: the algorithm shrinks the margin to satisfy almost every constraint, even if one outlier forces a contorted boundary. Small $C$ says “violations are cheap”: it prefers a wide, smooth corridor and accepts that some points end up inside. Drag the dial in Hands-on 2.

D · Kernels redraw the boundary

With a non-linear kernel, the same dual SVM produces a boundary that bends. The kernel implicitly maps the data into a higher (sometimes infinite-dimensional) feature space where a straight hyperplane lives; back in the original space, that hyperplane looks curved.

The left panel shows the original data — a ring of positives surrounded by negatives, definitely not linearly separable. The right panel sketches what an RBF kernel does conceptually: it “lifts” the data into a richer space where a straight hyperplane does the job. You never compute that lift explicitly — that is the whole point of the kernel trick.

view

Three lessons in one figure

(1) Margin is a corridor, not just a line. Widening it is the whole game. (2) Support vectors are the few points that pin the corridor; they live on the dashed boundaries (and, with soft margins, possibly inside or across them). (3) Kernels change the corridor’s shape, not the algorithm — the optimisation problem is identical; only the entry $k(\mathbf{x}_n, \mathbf{x}_m)$ of the Gram matrix changes.

06 · Hands-on

Try it yourself

Three labs, each isolating one idea you need to see move before it sticks. Push the controls, watch the numbers, then read the takeaway.

Hands-on 1

Maximum-margin geometry — find the widest corridor

Each preset is a small, linearly separable dataset. The SVM solves its dual and returns the unique maximum-margin hyperplane (solid gold), the two margin lines y = ±1 (dashed), and the support vectors — the only points that touch the corridor, ringed in green. Far-away points get αₙ = 0 and could be deleted without changing the answer.

w = (w₁, w₂)

(0.50, 0.50)

bias b

-2.00

Margin γ = 1/‖w‖

1.414

Support vectors

2 / 4

Try thisStart on Worked example: the line is ½x₁ + ½x₂ − 2 = 0, the margin is √2 ≈ 1.414, and exactly two of four points are support vectors — matching the by-hand derivation in §4. Switch to Three support vectors: now three points pin the corridor, yet the other three still vanish from the model.

TakeawayOnly the points on the dashed margin lines matter — the sparsity property. The corridor width 2γ = 2/‖w‖ is exactly what minimising ½‖w‖² maximises.

Hands-on 2

Soft margin — the C dial

The two classes overlap, so a hard margin is infeasible. The penalty C prices each margin violation ξₙ. Slide it from 10⁻² (wide corridor, many points inside it, calm boundary) to 10³ (narrow corridor, accuracy chased even at the cost of a contorted line). Terracotta stems mark each point's slack.

log₁₀ CC = 1.0

balanced

Margin γ

1.550

Σ ξ (violation)

8.56

Train accuracy

88%

Support vectors

10 / 26

Try thisAt log₁₀C = −2 the corridor is enormous and Σξ is large, but the line is steady. Drag to +3: the margin collapses, accuracy climbs, and the SV set shrinks toward the few points that pin a near-hard margin. Resample — the best C shifts with the noise level.

TakeawayC is a bias–variance dial and the inverse of ridge's λ: small C → wide margin, high bias, low variance; large C → narrow margin, low bias, high variance. Neither extreme generalises best, which is why C is chosen by cross-validation.

Hands-on 3

Hinge loss vs 0/1, squared, and logistic

The horizontal axis is the signed margin z = t·y(x): positive means correctly classified, and z ≥ 1 means correct with the full margin. Drag the probe to read each loss. The hinge (gold) is the tightest convex upper bound on the 0/1 loss that is flat past the margin — the property that makes SVMs sparse.

margin z = t·yz = 0.40

Hinge max(0, 1−z)

0.60

0/1 loss

Squared (1−z)²

0.36

Logistic log₂(1+e⁻ᶻ)

0.74

Try thisSlide z past 1: the hinge and 0/1 losses both hit exactly zero and stay there — a point comfortably outside the margin pays nothing. The squared loss, by contrast, keeps growing for z > 1, penalising correct-and-confident points. Now slide z negative (misclassified): the hinge rises linearly while the squared loss rises quadratically.

TakeawayThe hinge is the tightest convex surrogate for the non-convex 0/1 loss, and its flat tail past the margin is exactly why most αₙ end up at zero. The squared loss gives every point a non-zero gradient — which is why ridge classification is never sparse — while the logistic loss is smooth but asymptotes to zero only as z → ∞.

07 · Exam intel

What the exam actually tests

SVMs are a perennial Polimi favourite. A handful of question shapes account for almost every appearance.

Derive the primal from 'maximise the margin'

State the geometric margin $\gamma = \min_n t_n(\mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}_n)+b)/\|\mathbf{w}\|$ . Use the rescaling freedom $(\mathbf{w}, b) \mapsto (c\mathbf{w}, cb)$ to fix the minimum functional margin to 1. Then $\gamma = 1/\|\mathbf{w}\|$ , so maximising $\gamma$ is minimising $\|\mathbf{w}\|$ — equivalently $\tfrac{1}{2}\|\mathbf{w}\|^2$ . The constraints $t_n(\mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}_n)+b) \geq 1$ follow directly from the rescaling. State that the result is a convex QP — one global optimum.

Derive the dual

Write the Lagrangian $L = \tfrac{1}{2}\|\mathbf{w}\|^2 - \sum_n \alpha_n[t_n(\mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}_n)+b) - 1]$ , $\alpha_n \geq 0$ . Stationarity gives $\mathbf{w} = \sum_n \alpha_n t_n \boldsymbol{\phi}(\mathbf{x}_n)$ and $\sum_n \alpha_n t_n = 0$ . Substitute back to eliminate $\mathbf{w}, b$ :

\tilde{L}(\boldsymbol{\alpha}) = \sum_n \alpha_n - \tfrac{1}{2}\sum_{n,m} \alpha_n \alpha_m t_n t_m\, k(\mathbf{x}_n, \mathbf{x}_m), \quad \alpha_n \geq 0,\; \sum_n \alpha_n t_n = 0.

Highlight that only the kernel appears — this is what makes non-linear SVMs possible. State the dual is also a convex QP, with $N$ variables instead of $D$ (good when $D \gg N$ , e.g. kernels mapping to infinite-dimensional spaces).

State and use the KKT conditions

For the soft-margin SVM the KKT conditions are

\alpha_n \geq 0, \quad \mu_n \geq 0, \quad t_n y(\mathbf{x}_n) - 1 + \xi_n \geq 0, \quad \xi_n \geq 0,

\alpha_n\bigl[t_n y(\mathbf{x}_n) - 1 + \xi_n\bigr] = 0, \quad \mu_n \xi_n = 0, \quad \alpha_n + \mu_n = C.

From these derive the three regimes: $\alpha_n = 0$ (non-SV), $0 < \alpha_n < C$ (margin SV, $\xi_n = 0$ ), $\alpha_n = C$ (bounded SV, $\xi_n > 0$ ). State how the bias is recovered from margin SVs: $b = t_n - \sum_m \alpha_m t_m k(\mathbf{x}_n, \mathbf{x}_m)$ for any margin SV — or, for stability, average over all margin SVs.

Soft margin: derive the box constraint αₙ ≤ C

Add slacks $\xi_n \geq 0$ and a penalty $C \sum_n \xi_n$ to the primal. The Lagrangian gains terms $-\sum_n \mu_n \xi_n$ (with $\mu_n \geq 0$ ), and the slack-margin constraint enters with multiplier $\alpha_n$ . Stationarity in $\xi_n$ gives $C - \alpha_n - \mu_n = 0$ , i.e. $\alpha_n = C - \mu_n \leq C$ . Together with $\alpha_n \geq 0$ this gives the box $0 \leq \alpha_n \leq C$ . The rest of the dual derivation is identical to the hard-margin case.

Generalisation bounds

Two bounds to memorise:

Margin bound. The VC dimension of the class of separating hyperplanes with margin $\geq \gamma$ on data in a ball of radius $R$ is bounded by $\min(D+1,\, (R/\gamma)^2)$ . Bigger margin $\to$ smaller VC $\to$ tighter generalisation gap. Loose in practice but conceptually crucial.
Leave-one-out bound. $\mathbb{E}[L_{\text{LOO}}] \leq \mathbb{E}[\#\text{SVs}]/N$ . Data-dependent, requires no separate cross-validation, and is often what people quote in practice.

Both bounds explain why kernels can fail you: a very rich kernel makes all-vs-all points become SVs and both bounds go vacuous. The margin shrinks, the SV count explodes, and you overfit.

Rewrite the soft-margin SVM as regularized loss minimization

From the primal $\min \tfrac{1}{2}\|\mathbf{w}\|^2 + C\sum_n \xi_n$ with $t_n y(\mathbf{x}_n) \geq 1 - \xi_n,\, \xi_n \geq 0$ , the two constraints on $\xi_n$ together force $\xi_n = \max(0,\, 1 - t_n y(\mathbf{x}_n)) = \ell_{\text{hinge}}$ . So the SVM is the unconstrained problem $\min \tfrac{1}{2}\|\mathbf{w}\|^2 + C\sum_n \ell_{\text{hinge}}(y(\mathbf{x}_n), t_n)$ — the same template as ridge regression (squared loss + L2) and L2-logistic regression (log loss + L2); only the loss differs. Here $C$ plays the role of $1/\lambda$ : large $C$ = weak regularization.

When would you solve the primal vs the dual?

Primal has $D+1$ variables, dual has $N$ . Choose the primal when the feature map is explicit and cheap — linear kernel, $D \ll N$ , big datasets. Choose the dual when using a non-linear kernel: the primal $\mathbf{w}$ may live in an infinite-dimensional space (RBF) and cannot be represented, while the dual only needs the finite Gram matrix $K_{nm} = k(\mathbf{x}_n, \mathbf{x}_m)$ . Strong duality holds (convex QP

linear constraints) so the two give the same optimum.

tip

Memorise these five formulas — and you have the chapter

Primal: $\min \tfrac{1}{2}\|\mathbf{w}\|^2 + C \sum_n \xi_n$ s.t. $t_n(\mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}_n)+b) \geq 1-\xi_n,\; \xi_n \geq 0$ .
Dual: $\max \sum_n \alpha_n - \tfrac{1}{2}\sum_{n,m} \alpha_n \alpha_m t_n t_m k(\mathbf{x}_n, \mathbf{x}_m)$ s.t. $0 \leq \alpha_n \leq C,\; \sum_n \alpha_n t_n = 0$ .
Prediction: $y(\mathbf{x}) = \sum_{n \in \mathcal{S}} \alpha_n t_n k(\mathbf{x}, \mathbf{x}_n) + b$ .
LOO bound: $L_{\text{LOO}} \leq \#\text{SVs}/N$ .
Hinge-loss form: $\min \tfrac{1}{2}\|\mathbf{w}\|^2 + C\sum_n \max(0,\, 1 - t_n y(\mathbf{x}_n))$ — same SVM, unconstrained, slots into the ridge / logistic-regression family.

08 · Common mistakes

Where students get this wrong

'Support vectors are the points closest to the boundary'

Half right. Support vectors are the points with non-zero $\alpha_n$ . In the hard-margin case these are exactly the points on the margin (closest to the boundary, distance $\gamma$ ). In the soft-margin case they also include points inside the margin and across it — anywhere the constraint is active or violated. A point can be a support vector despite being misclassified.

Forgetting to scale features before training

SVMs depend on Euclidean distances — through $\|\mathbf{w}\|$ in the linear case and through kernel evaluations like $\exp(-\gamma \|\mathbf{x}-\mathbf{x}'\|^2)$ in the RBF case. If one feature is in metres and another in kilograms, the metres feature dominates everything. Always standardise (zero mean, unit variance) before fitting. This is not optional; it changes the boundary.

'C is a regulariser, so larger C means more regularisation'

Backwards. Larger $C$ penalises violations more heavily, so the algorithm allows fewer violations and shrinks the margin — that is less regularisation. Small $C$ lets the margin be wide at the cost of more slack — that is more regularisation. Mentally connect: large $C$ $\leftrightarrow$ small $\lambda$ (in ridge-regression language).

'The dual has N variables, so it is always slower than the primal'

Depends on which is bigger, $N$ or $D$ . When $D \gg N$ — text classification with bag-of-words, or any kernel method where $\boldsymbol{\phi}$ is high- or infinite-dimensional — the dual is vastly cheaper. When $N \gg D$ , the primal can be faster. SVMs are usually solved in the dual because the kernel trick demands it; SMO was designed specifically for this.

Using accuracy alone to choose the kernel and C

A 99% training accuracy can hide a fragile model with 80% of points as support vectors. Use cross-validated accuracy on a held-out set (or the LOO bound). The kernel and $C$ are model-selection parameters and must be tuned exactly like $\lambda$ in ridge regression (Ch. 04).

Treating SVMs as black boxes after computing accuracy

Two diagnostics are free and very informative: the fraction of support vectors and the distribution of $\xi_n$ . If 80%+ of points are SVs, your kernel is too rich or $C$ too large — overfitting. If $\xi_n$ is small for nearly everyone, the data is well-separated and you could probably reduce $C$ . Look at the numbers before believing the accuracy.

'SVMs only do classification'

The same margin-maximisation idea works for regression (Support Vector Regression, with an $\varepsilon$ -insensitive loss), novelty detection (one-class SVM), ranking, feature selection, and even semi-supervised learning. The chapter focuses on classification because the geometry is cleanest there — but the optimisation framework is much more general.

09 · Self-check

Can you answer these?

Seven questions in the style the exam likes. Click an option for instant feedback.

A trained hard-margin SVM has 200 training points; only 5 have non-zero αₙ. You add a new training point well inside positive territory (far from the boundary), retrain, and ask: which is true?

In the soft-margin dual, what is the meaning of a training point with αₙ = C?

You train an RBF SVM and observe that 90% of training points are support vectors. Train accuracy is 100%. What is most likely?

In the hard-margin SVM, the optimum satisfies w = Σₙ αₙ tₙ φ(xₙ). Which statement about this equation is FALSE?

You can write the soft-margin SVM as min ½‖w‖² + C Σₙ max(0, 1 − tₙ y(xₙ)). Which statement about this view is MOST accurate?

You train an SVM on text with N = 5,000 documents and D = 50,000 sparse TF-IDF features, using a linear kernel. Which approach is most appropriate?

Two hyperplanes both separate the data perfectly. Hyperplane A has γ = 0.2; hyperplane B has γ = 0.8 on data inside a ball of radius R = 1. Which generalises better, and why?

10 · Recap

One-screen summary

Chapter 07 — load-bearing ideas

The maximum-margin hyperplane. Among all separating hyperplanes, pick the one with the widest empty corridor. Geometric margin $\gamma = 1/\|\mathbf{w}\|$ after the standard rescaling.
Hard-margin primal. $\min \tfrac{1}{2}\|\mathbf{w}\|^2$ subject to $t_n(\mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}_n)+b) \geq 1$ . Convex QP, unique global optimum, requires linear separability.
Hard-margin dual. $\max \sum_n \alpha_n - \tfrac{1}{2}\sum_{n,m}\alpha_n \alpha_m t_n t_m k(\mathbf{x}_n,\mathbf{x}_m)$ subject to $\alpha_n \geq 0,\; \sum_n \alpha_n t_n = 0$ . Features have vanished; only the kernel appears.
KKT and support vectors. Complementary slackness $\alpha_n[t_n y(\mathbf{x}_n)-1]=0$ partitions the data: most points have $\alpha_n = 0$ (non-SVs); a few sit on the margin with $\alpha_n > 0$ (SVs). The model depends only on SVs.
Soft-margin SVM. Add slacks $\xi_n \geq 0$ and penalty $C\sum_n \xi_n$ . Dual is identical except $0 \leq \alpha_n \leq C$ . Three regimes: outside-margin ( $\alpha=0$ ), on-margin ( $0<\alpha<C$ ), inside/across ( $\alpha=C, \xi>0$ ).
Kernel trick. Replace $\boldsymbol{\phi}(\mathbf{x})^\top \boldsymbol{\phi}(\mathbf{x}')$ with any Mercer kernel $k(\mathbf{x},\mathbf{x}')$ . Linear, polynomial, RBF — all just different Gram matrices. The optimisation stays convex.
Prediction. $y(\mathbf{x}) = \sum_{n\in\mathcal{S}} \alpha_n t_n k(\mathbf{x}, \mathbf{x}_n) + b$ . Recover $b$ by averaging $t_n - \sum_m \alpha_m t_m k(\mathbf{x}_n, \mathbf{x}_m)$ over margin SVs.
Generalisation. Margin bound: VC $\leq (R/\gamma)^2$ . LOO bound: $L_{\text{LOO}} \leq \#\text{SVs}/N$ — free, data-dependent, often quoted in practice.
Hinge-loss view. Soft-margin SVM $\Leftrightarrow$ $\min \tfrac{1}{2}\|\mathbf{w}\|^2 + C \sum_n \max(0,\, 1 - t_n y(\mathbf{x}_n))$ . Same template as ridge and logistic regression; only the loss differs. The hinge’s flat tail past the margin is exactly what creates sparsity in $\alpha_n$ .
Primal vs dual. Primal has $D+1$ variables — solve when $D \ll N$ and the kernel is linear. Dual has $N$ variables — solve whenever the kernel is non-linear (RBF, polynomial). Strong duality means the same optimum either way.

→

Looking ahead → Chapter 08

We have built the cleanest convex classifier in the book. Next we leave convexity behind for models that stack non-linear transformations — neural networks — where the loss surface is riddled with local minima but the representational power is unmatched.