Classification Overview

Chapter 9 predicted a real number. Chapter 10 found a compact representation. Chapter 11 estimated a density. Chapter 12 predicts one of two labels — the last of the book’s four pillars — and it does so with no probability anywhere in it.

$$f : \mathbb{R}^D \to \{+1, -1\} \qquad \text{(12.1)}$$

The book gives two reasons for choosing the SVM to carry this chapter. First, “the SVM allows for a geometric way to think about supervised machine learning” — it reasons about inner products and projections rather than likelihoods, which makes it the counterpart of Chapter 10 rather than of Chapter 9. Second, “the optimization problem for SVM does not admit an analytic solution so that we need to resort to a variety of optimization tools introduced in Chapter 7.”

This chapter prints no numbers

Chapters 9, 10 and 11 all carried worked numerical examples. Chapter 12 has none — no Example environments, no tables of values, no figure with a number on an axis. Everything it says is geometric or algebraic.

That makes it the chapter where a measured reading has the most to add, and it means this module has to supply its own running example. Eight points in $\mathbb{R}^2$, chosen so the answer is exact and checkable by hand:

$$\mathbf{w}^* = (1, 0), \qquad b^* = -2, \qquad \lVert\mathbf{w}^*\rVert = 1, \qquad r = 1$$

with three of the eight examples sitting exactly on the margin. Every page from 1201 to 1211 checks against it.

One classifier, four derivations

	§12.2.1	§12.2.2	§12.3.1	§12.3.2
the question asked	how far is the closest point?	same, with the scale fixed differently	what do the Lagrange multipliers say?	which two points of the two hulls are closest?
what is optimised	$\max r$	$\min\tfrac12\lVert\mathbf{w}\rVert^2$	$\min$ over $\boldsymbol\alpha$	$\min\lVert\mathbf{c}-\mathbf{d}\rVert$
variables	$D+2$	$D+1$	$N$	$N$
convex	no	yes	yes	yes

They are not four methods that happen to agree. Measured across $300$ random datasets, the first two return hyperplanes whose normals differ by at most $7.492\times10^{-6}$ degrees. The fourth, converted through a formula the book does not state, matches a primal solve to $9.185\times10^{-8}$.

The conversion is worth having, because §12.3.2 leaves it out:

$$\mathbf{w}^* = \frac{2(\mathbf{c}-\mathbf{d})}{\lVert\mathbf{c}-\mathbf{d}\rVert^2}, \qquad r = \frac{\lVert\mathbf{c}-\mathbf{d}\rVert}{2}$$

The margin is half the distance between the two convex hulls. That is the shortest true statement of what an SVM computes, and it appears nowhere in the chapter.

The one property everything follows from

The hinge loss reaches exactly zero:

$$\ell(t) = \max\{0,\ 1 - t\}, \qquad t = y f(\mathbf{x}) \qquad \text{(12.28)}$$

An example beyond its margin contributes nothing. Not a small amount — nothing. Four consequences, each measured on a different page:

consequence	where	measured
a distant correct point cannot move the fit	1205	boundary at $2.000000$ with the outlier at $6$, $20$ or $80$
most multipliers are zero	1206	$3$ of $8$ examples carry the answer
deleting the rest changes nothing	1206	adding $500$ more changes nothing either — $8.289\times10^{-12}$ of mass
the support vector count bounds leave-one-out error	1210	$2$ of $60$ gives a guarantee of $0.0333$

Contrast the logistic loss, which the book names as the maximum-likelihood counterpart in §12.6: it is $0.000045$ at $t = 10$ and never zero. Every example keeps a gradient forever, so logistic regression has no support vectors — measured, deleting the SVM’s ignored examples leaves the SVM bit-for-bit identical and moves logistic regression’s offset by $0.537167$.

Where the measuring pays off

Zero training error does not pick a classifier. $9{,}628$ sampled hyperplanes separate the eight running-example points perfectly, and their held-out accuracy spans $0.1119$. Something has to break the tie, and the margin is what §12.2 proposes.

But the margin raises the floor, not the ceiling. Binned by margin, the worst held-out accuracy climbs from $0.8757$ to $0.9777$ while the best barely moves. Across $192$ datasets the max-margin solution averages the $84$th percentile among separators that fit equally well — and beats all of them on only $6$. It gives up $0.00819$ on average against the best that existed. Maximising the margin is insurance, not optimisation, which is what the generalisation bounds the book cites actually prove.

Equation 12.10 is not a convex problem, and the book presents Theorem 12.1 as an equivalence rather than an upgrade. The constraint $\lVert\mathbf{w}\rVert = 1$ is a sphere; measured, a local solver fails on $12.55\%$ of random starts, against $0.00\%$ for Equation 12.21.

Leaving $b$ out of the regulariser is not a technical inconvenience. The book calls it a complication for theory and efficiency. It is what makes the answer independent of where the origin sits: shifting the data by $(10, 0)$ leaves the optimal value unchanged to $1.993\times10^{-15}$, while penalising $b$ changes it by $\mathbf{10.48}$.

“Infinite-dimensional feature space” has a measurable consequence. A feature map of dimension $M$ gives a Gram matrix of rank at most $M$. Polynomial kernels saturate exactly — $6$, $10$, $21$ at every $N$ from $50$ to $800$ — and the RBF’s never levels off, climbing from $50$ to $171$. That is what having no finite feature map looks like from outside.

The chapter never mentions standardising, and it is worth a quarter of a point of accuracy. Scaling one feature by $s$ and refitting is the same as minimising $w_1^2 + w_2^2/s^2$ under the original constraints — so the units decide how expensive each feature is to use. On data where the cheap feature is the bad one, held-out accuracy swings by $0.2638$. Standardising first collapses the spread to $0.0029$.

The pages

#	page	book section	the measured claim
1201	Separating Hyperplanes	§12.1	$9{,}628$ perfect classifiers, accuracy spanning $0.1119$
1202	The Concept of the Margin	§12.2.1	Equation 12.10 is non-convex; $12.55\%$ of solves fail
1203	Why the Margin Can Be Set to One	§12.2.2–12.2.3	Theorem 12.1 to $7.492\times10^{-6}$ degrees
1204	The Soft Margin SVM	§12.2.4	unregularised $b$ buys translation invariance, $10.48$
1205	The Hinge Loss	§12.2.5	a distant correct point moves the squared-loss boundary $2.33 \to 3.97$
1206	The Dual Support Vector Machine	§12.3.1	$\sum_n\alpha_n = \lVert\mathbf{w}\rVert^2$, an identity the book omits
1207	The Convex Hull View	§12.3.2	the margin is half the distance between the hulls
1208	Kernels	§12.4	polynomial Gram rank saturates at $6$, $10$, $21$; the RBF’s never does
1209	Numerical Solution	§12.5	a generic solver is $49{,}548$ times slower at $N = 2000$
1210	Chapter 12 Worked Problems	§12.6	eight problems, this module’s own
1211	Chapter 12 Formula Sheet	—	every equation and every measured constant

Chapter 12 has no end-of-chapter exercises

Like Chapters 8, 9, 10 and 11, it runs straight from §12.6 into the references. Page 1210’s problems are this module’s own, built from claims the chapter makes, and should not be attributed to Deisenroth, Faisal and Ong.

Two small corrections

Neither changes anything that follows, but both are worth knowing about while reading.

Equations 12.5, 12.6 and 12.7 are not quite equivalent. Equation 12.6 is strict and 12.7 is not, so a point sitting exactly on the hyperplane satisfies 12.7 and violates 12.6. The disagreement is confined to a set of measure zero — and page 1204 found a case where it matters numerically, with an optimal boundary running exactly through two training points whose labels are then decided by a quantity of size $10^{-15}$.

§12.3.1’s margin note runs only one way. It says examples on the margin are those with $0 < \alpha_i < C$. The KKT conditions give that implication, not its converse: $\alpha_n = C$ permits $y_nf(\mathbf{x}_n) = 1$ too, and at $C = 2$ on the running example three on-margin examples sit exactly at the bound. The optimum there is unique, so it is not a solver artefact.

There is also a third, smaller one: §12.3.1’s fallback rule for recovering $b$ takes a median of absolute differences, which discards the sign and returns $+2$ where the answer is $-2$.

What the chapter assumes, and what it costs

§12.6 is a page of pointers. Page 1210 runs the ones that can be run:

what the chapter says or omits	measured
“a classifier with large margin turns out to generalize well”	true as a percentile — $84.11\%$ — and false as an optimum
$C$ is introduced and never chosen	its good plateau is four orders of magnitude wide
kernel parameters “chosen using nested cross-validation”	$C$ and $\gamma$ do not tune independently: $\gamma = 0.01$ runs $0.7143 \to 0.9965$ across $C$
“does not naturally lend itself to a probabilistic interpretation”	$74.40\%$ of its scores fall outside $[-1, 1]$
Platt scaling as the repair	costs accuracy in the probabilities: Brier $0.09695$ against logistic regression’s $0.09540$
(never mentioned) feature scaling	worth $0.2638$ of held-out accuracy
(never mentioned) class balance	at $10$ positives against $200$ negatives, recall on the minority is exactly $0.0000$

Where it goes next

§12.6’s pointer	and where it already appeared
logistic regression — the maximum-likelihood counterpart	page 1205’s loss table; page 1210’s measurement that it has no support vectors
Platt scaling and class probability estimation	page 1210, measured against a known true posterior
kernel methods more broadly	page 1208, and Chapter 10’s §10.5 where the same $N\times N$ matrix appeared
the Legendre–Fenchel transform as another route to the dual	Chapter 7’s §7.3.3
empirical risk minimisation and the theory behind the margin	Chapter 8’s §8.2
Gaussian process classification — a latent function prior	Chapter 9’s §9.3, and Chapter 11’s latent variables

And that closes the four pillars: regression in Chapter 9, dimensionality reduction in Chapter 10, density estimation in Chapter 11, classification here.

Recall card

• Chapter 12 is the last of the four pillars, classification, and it reasons geometrically rather than probabilistically.
• It prints no numbers at all — no worked examples anywhere — so every value in this module is its own, checked against an eight-point running example whose answer is exact.
• One classifier is reached four ways, and they agree to seven millionths of a degree across three hundred random datasets.
• Only one of those four formulations is convex. The unit-sphere constraint of Equation 12.10 makes a local solver fail on one start in eight, while the squared-norm form never fails.
• Zero training error does not pick a classifier, and the margin is what breaks the tie.
• But the margin raises the floor rather than the ceiling. It lands at the 84th percentile every time and is almost never the best separator available.
• The hinge loss reaches exactly zero, and everything distinctive about the method follows: distant points cannot move the fit, most multipliers are zero, deleting them changes nothing, and the support vector count bounds the leave-one-out error.
• The logistic loss never reaches zero, which is why logistic regression has no support vectors and every example influences it forever.
• The dual’s size depends on the number of examples and never on the number of features, which is the only reason an infinite-dimensional feature map is usable.
• An infinite-dimensional feature space is measurable as a Gram rank that never saturates — polynomial kernels stop at 6, 10 and 21, and the RBF keeps climbing.
• Read geometrically, the whole method is: find the two closest points of the two convex hulls and bisect the segment, and the margin is half its length.
• Leaving the intercept out of the regulariser is what makes the answer independent of the coordinate system, which the book mentions only as a complication.
• The chapter never mentions standardising, and a change of units on one feature is worth a quarter of a point of held-out accuracy.

Start here: Separating Hyperplanes