Chapter 12 Formula Sheet

One page for the whole chapter. Equation numbers are the book’s; the measured columns are this module’s, computed on the eight-point running example unless stated otherwise. Chapter 12 prints no numbers of its own — it has no worked examples — so every value here was produced by these pages.

The running example

$$\mathbf{X} = \begin{bmatrix}3&1\\3&-1\\6&1\\6&-1\\1&0\\0&1\\0&-1\\-1&0\end{bmatrix}, \qquad \mathbf{y} = (+1,+1,+1,+1,-1,-1,-1,-1)$$

quantity	exact value
$\mathbf{w}^*$, $b^*$	$(1, 0)$, $-2$
$\lVert\mathbf{w}^*\rVert$, margin $r$	$1$, $1$
support vectors	$(3,1)$, $(3,-1)$, $(1,0)$ — $3$ of $8$
$\boldsymbol\alpha$	$(\tfrac14, \tfrac14, 0, 0, \tfrac12, 0, 0, 0)$
closest hull points $\mathbf{c}$, $\mathbf{d}$	$(3, 0)$, $(1, 0)$; $\lVert\mathbf{c}-\mathbf{d}\rVert = 2$

The chapter in one table

Four routes to one classifier.

	§12.2.1	§12.2.2	§12.3.1	§12.3.2
what is fixed	$\lVert\mathbf{w}\rVert = 1$	value $1$ at the closest point	—	—
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 (a sphere)	yes	yes	yes
equation	12.10	12.21	12.41	12.48
they agree to	$7.492\times10^{-6}$ degrees over $300$ datasets, and $9.185\times10^{-8}$ in $\mathbf{w}$

§12.1 Separating hyperplanes

what	equation
the task	$f : \mathbb{R}^D \to \{+1, -1\}$ — 12.1
the model	$f(\mathbf{x}) = \langle\mathbf{w},\mathbf{x}\rangle + b$ — 12.2a, 12.2b
the hyperplane	$\{\mathbf{x} : f(\mathbf{x}) = 0\}$ — 12.3
$\mathbf{w}$ is normal to it	$f(\mathbf{x}_a) - f(\mathbf{x}_b) = \langle\mathbf{w},\mathbf{x}_a - \mathbf{x}_b\rangle$ — 12.4a, 12.4b
correct classification	$\langle\mathbf{w},\mathbf{x}_n\rangle + b \geq 0$ if $y_n = +1$; $< 0$ if $y_n = -1$ — 12.5, 12.6
combined	$y_n(\langle\mathbf{w},\mathbf{x}_n\rangle + b) \geq 0$ — 12.7

Three things Section 12.1 leaves unsaid

Equation 12.3 names a set, not parameters. Every positive multiple of $(\mathbf{w}, b)$ gives the same classifier — measured identical at $c = 0.5, 1, 2, 17, 1000$ — so “distance to the hyperplane” is meaningless until a scale is fixed.

Equations 12.5 and 12.6 are not symmetric. One is inclusive and one strict, so a point exactly on the hyperplane is classified $+1$ by fiat, and Equation 12.7 is very slightly weaker than the pair it replaces.

Zero training error does not pick a classifier. $9{,}628$ sampled hyperplanes separate the eight points perfectly and their held-out accuracy spans $0.1119$.

§12.2.1 The margin

what	equation
vector addition	$\mathbf{x}_a = \mathbf{x}_a' + r\,\dfrac{\mathbf{w}}{\lVert\mathbf{w}\rVert}$ — 12.8
both classes at once	$y_n(\langle\mathbf{w},\mathbf{x}_n\rangle + b) \geq r$ — 12.9
the problem	$\max_{\mathbf{w},b,r} r$ s.t. 12.9, $\lVert\mathbf{w}\rVert = 1$, $r > 0$ — 12.10

$r$ is a signed coordinate along $\mathbf{w}/\lVert\mathbf{w}\rVert$: measured on all eight points, $\lvert r\rvert$ equals the distance to the projection to $0.000\times10^{0}$, and the sign gives the side. With $\lVert\mathbf{w}\rVert = 1$, $f(\mathbf{x})$ is that coordinate.

§12.2.2–12.2.3 Setting the margin to one

what	equation
the projection is on the hyperplane	$\langle\mathbf{w},\mathbf{x}_a'\rangle + b = 0$ — 12.11
substitute 12.8	12.12, expand by bilinearity — 12.13
the margin	$r = \dfrac{1}{\lVert\mathbf{w}\rVert}$ — 12.14
the constraint	$y_n(\langle\mathbf{w},\mathbf{x}_n\rangle + b) \geq 1$ — 12.15
maximise the reciprocal	12.16, 12.17
the hard margin SVM	$\min_{\mathbf{w},b}\tfrac12\lVert\mathbf{w}\rVert^2$ s.t. 12.15 — 12.18, 12.19
Theorem 12.1	12.10 and 12.21 are equivalent — 12.20, 12.21
the proof’s hinge	$\lVert\mathbf{w}''\rVert = 1/r$ — 12.24, checked to $1.137\times10^{-13}$

Theorem 12.1 is an upgrade, not just an equivalence

The constraint $\lVert\mathbf{w}\rVert = 1$ confines $\mathbf{w}$ to a sphere, which is not a convex set. Over $2{,}000$ random starts:

formulation	failed to converge	distinct optima
12.10	$251$ — $12.55\%$	$1$
12.21	$\mathbf{0}$ — $0.00\%$	$1$

Every run that converged found $r = 1$, so the non-convexity costs reliability rather than accuracy. Squaring the norm buys the same thing on the objective side: $\lVert\mathbf{w}\rVert$ failed $3$ of $500$ starts and took up to $29$ iterations; $\tfrac12\lVert\mathbf{w}\rVert^2$ failed none and never exceeded $5$.

§12.2.4–12.2.5 The soft margin, twice

what	equation
geometric view	$\min \tfrac12\lVert\mathbf{w}\rVert^2 + C\sum_n\xi_n$ s.t. $y_n f(\mathbf{x}_n) \geq 1-\xi_n$, $\xi_n \geq 0$ — 12.26a–c
the hypothesis class	$f(\mathbf{x}) = \langle\mathbf{w},\mathbf{x}\rangle + b$ — 12.27
the hinge loss	$\ell(t) = \max\{0, 1-t\}$, $t = yf(\mathbf{x})$ — 12.28
as two pieces	$0$ if $t \geq 1$, else $1-t$ — 12.29
the hard margin’s loss	$0$ if $t \geq 1$, else $\infty$ — 12.30
loss view	$\min \underbrace{\tfrac12\lVert\mathbf{w}\rVert^2}_{\text{regularizer}} + C\sum_n\underbrace{\max\{0, 1-y_nf(\mathbf{x}_n)\}}_{\text{error term}}$ — 12.31
why they are the same	$\min_t\max\{0,1-t\} \equiv \min_{\xi,t}\xi$ s.t. $\xi\geq0$, $\xi\geq1-t$ — 12.32, 12.33

$\xi_n$	where the example is
$0$	correct, at or beyond its margin — costs nothing
$(0, 1]$	correct side, inside the margin
$> 1$	wrong side of the hyperplane

What C does, and the remark that is not a remark

$C$ is the price of a violation, and large $C$ means low regularisation — the reverse of the usual convention, because $C$ multiplies the error term.

limit	measured
$C \to \infty$ on separable data	recovers the hard margin exactly by $C = 1$, $\lvert b - b^*\rvert = 0$
$C \to 0$	$\lVert\mathbf{w}\rVert \propto C$; margin balloons to $800$; at $C = 0$ the classifier is constant
above $C \approx 2$ here	the solution stops moving; only the objective scales

$b$ is left out of the regulariser, and that is what makes the method invariant to where the origin sits. Shifting the data by $(10, 0)$ leaves the optimal value unchanged to $1.993\times10^{-15}$; adding $\tfrac12 b^2$ to the objective changes it by $\mathbf{10.48}$ and shrinks $\lVert\mathbf{w}\rVert$ from $1.000000$ to $0.800000$.

§12.3.1 The dual

what	equation
the Lagrangian	$\mathfrak{L} = \tfrac12\lVert\mathbf{w}\rVert^2 + C\sum\xi_n - \sum\alpha_n(y_nf(\mathbf{x}_n)-1+\xi_n) - \sum\gamma_n\xi_n$ — 12.34
the three derivatives	12.35, 12.36, 12.37
the representer theorem	$\mathbf{w} = \sum_n \alpha_n y_n \mathbf{x}_n$ — 12.38
substituting back	12.39, 12.40
the dual SVM	$\min_{\boldsymbol\alpha}\tfrac12\sum_{i,j}y_iy_j\alpha_i\alpha_j\langle\mathbf{x}_i,\mathbf{x}_j\rangle - \sum_i\alpha_i$ s.t. $\sum_i y_i\alpha_i = 0$, $0 \leq \alpha_i \leq C$ — 12.41
recovering the intercept	$b^* = y_n - \langle\mathbf{w}^*,\mathbf{x}_n\rangle$ — 12.42

the KKT conditions, which the book gives only as a margin note
$\alpha_n = 0$	$y_nf(\mathbf{x}_n) \geq 1$
$0 < \alpha_n < C$	$y_nf(\mathbf{x}_n) = 1$
$\alpha_n = C$	$y_nf(\mathbf{x}_n) \leq 1$

Two things to correct in §12.3.1

The margin note runs only one way. It says examples on the margin are those with $0 < \alpha_i < C$. The third KKT row permits $y_nf(\mathbf{x}_n) = 1$ with $\alpha_n = C$, and at $C = 2$ on the running example three on-margin examples sit exactly at the bound. The optimum there is unique — the constraints force $4t - 3.5u = 1$ and maximising $\sum\alpha_n = 1 + 3.5u$ pushes $u$ to $C$.

The fallback rule for $b$ discards a sign. Taking the median of $\lvert y_n - \langle\mathbf{w}^*,\mathbf{x}_n\rangle\rvert$ returns $+2$ where the answer is $-2$. Drop the absolute value.

An identity the book does not state

At a hard-margin optimum,

$$\lVert\mathbf{w}\rVert^2 = \sum_{n=1}^{N}\alpha_n = \frac{1}{r^2}$$

The total dual mass is the inverse squared margin — verified to $4.782\times10^{-8}$ over $200$ random datasets. A wide margin means small multipliers, which is the dual saying what the primal says by minimising $\lVert\mathbf{w}\rVert^2$.

§12.3.2 The convex hull view

what	equation
the convex hull	$\mathrm{conv}(\mathcal{X}) = \{\sum_n\alpha_n\mathbf{x}_n\}$, $\sum_n\alpha_n = 1$, $\alpha_n \geq 0$ — 12.43
the difference vector	$\mathbf{w} := \mathbf{c} - \mathbf{d}$ — 12.44
the objective	$\arg\min\lVert\mathbf{w}\rVert = \arg\min\tfrac12\lVert\mathbf{w}\rVert^2$ — 12.45
the two points	$\mathbf{c} = \sum_{y_n=+1}\alpha_n^{+}\mathbf{x}_n$, $\mathbf{d} = \sum_{y_n=-1}\alpha_n^{-}\mathbf{x}_n$ — 12.46, 12.47
in hull coordinates	12.48
each hull sums to one	12.49, which multiplies out to $\sum_n y_n\alpha_n = 0$ — 12.50, 12.51
the soft margin’s geometry	the reduced hull, with every weight capped

The conversion §12.3.2 omits

The hull vector and the SVM’s weights are not the same vector — here $(2,0)$ against $(1,0)$:

$$\mathbf{w}^* = \frac{2(\mathbf{c}-\mathbf{d})}{\lVert\mathbf{c}-\mathbf{d}\rVert^2}, \qquad b^* = -\Big\langle\mathbf{w}^*, \tfrac{\mathbf{c}+\mathbf{d}}{2}\Big\rangle, \qquad r = \frac{\lVert\mathbf{c}-\mathbf{d}\rVert}{2}$$

Checked on $200$ random datasets: $9.185\times10^{-8}$ in $\mathbf{w}$, $4.282\times10^{-8}$ in $b$, $5.051\times10^{-11}$ in the margin. The margin is half the distance between the two convex hulls — the shortest true statement of what an SVM computes, and one the chapter never makes.

The hull weights are the multipliers renormalised: each class carries dual mass $\lVert\mathbf{w}\rVert^2/2$, and dividing by it converts one to the other, to $5.780\times10^{-8}$.

§12.4 Kernels

what	equation
a kernel	$k(\mathbf{x}_i,\mathbf{x}_j) = \langle\boldsymbol\phi(\mathbf{x}_i),\boldsymbol\phi(\mathbf{x}_j)\rangle_{\mathcal{H}}$ — 12.52
the requirement	$\forall\mathbf{z} : \mathbf{z}^\top\mathbf{K}\mathbf{z} \geq 0$ — 12.53
the canonical feature map	$\boldsymbol\phi(\mathbf{x}) = k(\cdot, \mathbf{x})$
the substitution	replace $\langle\mathbf{x}_i,\mathbf{x}_j\rangle$ in 12.41 by $k(\mathbf{x}_i,\mathbf{x}_j)$

kernel	feature dimension	Gram rank at $N = 50 \dots 800$
polynomial, degree $2$	$\binom{D+2}{2} = 6$	$6, 6, 6, 6, 6$
polynomial, degree $3$	$10$	$10, 10, 10, 10, 10$
polynomial, degree $5$	$21$	$21, 21, 21, 21, 21$
RBF, $\gamma = 0.5$	infinite	$50, 93, 125, 154, 171$
RBF, $\gamma = 5.0$	infinite	$50, 100, 200, 392, 597$

The polynomial ranks saturate exactly and never move again; the RBF’s never level off. That is what having no finite feature map looks like from outside, and $\gamma$ controls how fast the space fills up.

Equation 12.53 is a requirement, not a convention

function	smallest eigenvalue of $\mathbf{K}$
linear	$-2.910\times10^{-14}$
polynomial, degree $3$	$-5.336\times10^{-13}$
RBF, $\gamma = 0.5$	$-1.049\times10^{-15}$
$\tanh$	$\mathbf{-5.544\times10^{1}}$, with $10$ of $120$ negative

With a negative eigenvalue the dual’s quadratic form is not convex, page 1206’s duality guarantee does not apply, and the solver is not solving Equation 12.41.

§12.5 Numerical solution

what	equation
the subgradient	$g(t) = -1$ for $t<1$; any value in $[-1,0]$ at $t=1$; $0$ for $t>1$ — 12.54
the primal, standard form	$D + 1 + N$ variables, $2N$ constraints — 12.55, 12.56
the dual, standard form	$N$ variables, $2N + 2$ constraint rows — 12.57
an equality as two inequalities	$\mathbf{A}\mathbf{x} = \mathbf{b} \Rightarrow \mathbf{A}\mathbf{x}\leq\mathbf{b}$ and $\geq\mathbf{b}$ — 12.58

measured	value
subgradient set at $t = 1$	exactly $[-1, 0]$; unique elsewhere
subgradient descent, $10^5$ iterations	gap $4.091\times10^{-4}$ — the $O(1/\sqrt{k})$ rate
12.56 solved against the reference	$7.105\times10^{-15}$
12.57 solved against the reference	$2.132\times10^{-14}$
generic SLSQP against LIBSVM	$89\times$ at $N=200$, $\mathbf{49{,}548\times}$ at $N=2000$

With an RBF kernel the primal has infinitely many variables and the dual has $N$. The dual is not merely smaller there — it is the only one of the two that exists.

Every measured constant in this chapter

quantity	value	page
$\langle\mathbf{w},\mathbf{x}_a-\mathbf{x}_b\rangle$ on the hyperplane	$0.000\times10^{0}$, $200{,}000$ pairs	1201
separating hyperplanes sampled	$9{,}628$ of $400{,}000$	1201
their held-out accuracy	worst $0.8757$, best $0.9877$, spread $0.1119$	1201
correlation, margin against accuracy	$0.590999$	1201
max-margin accuracy, and its rank	$0.9853$; beats $91.76\%$	1201
the Bayes rate for that generator	$0.9876$ at $x = 2.25$	1201
worst accuracy per margin bin	$0.8757 \to 0.9777$	1201
$r = 1/\lVert\mathbf{w}\rVert$	$3.553\times10^{-15}$, $20{,}000$ draws	1202, 1203
isotropic rescale: boundary	$2.000000$ at every $c$	1202
margin as an intruder enters	$\min\{1, (3-t)/2\}$; infeasible at $t = 3$	1202
12.10 vs 12.21, convergence failures	$251/2000$ against $0/2000$	1202
squaring the norm: change in argmin	$4.441\times10^{-16}$	1203
Theorem 12.1 over $300$ datasets	$7.492\times10^{-6}$ degrees; $1$ non-convergence	1203
Equation 12.24	$1.137\times10^{-13}$, $50{,}000$ draws	1203
$\lVert\mathbf{w}\rVert$ vs $\tfrac12\lVert\mathbf{w}\rVert^2$, $500$ starts	$3$ failures, $29$ iterations against $0$ and $5$	1203
soft margin recovers hard margin	exactly by $C = 1$; $\lvert b-b^*\rvert = 0$	1204
$C \to 0$	$\lVert\mathbf{w}\rVert \propto C$; margin $800$ at $C = 10^{-4}$	1204
translation invariance, $b$ free	$1.993\times10^{-15}$	1204
translation invariance, $b$ penalised	objective moves $\mathbf{10.48}$	1204
the knife edge at small $C$	labels decided by $f = \pm1.2\times10^{-15}$	1204
the exact zero-one optimum	$1$ error at $\mathbf{w} = (1,0)$, $b = -3$	1205
12.31 against 12.26	$4.45\times10^{-13}$ or better	1205
hinge boundary with a distant outlier	$2.000000$, unchanged at every distance	1205
squared-loss boundary, same outlier	$2.33 \to 3.97$; $2$ examples misclassified	1205
the dual multipliers	$(\tfrac14,\tfrac14,0,0,\tfrac12,0,0,0)$ to $1.075\times10^{-8}$	1206
$\lVert\mathbf{w}\rVert^2 = \sum\alpha_n$	$4.782\times10^{-8}$, $200$ datasets	1206
adding $500$ easy examples	still $3$ support vectors; $8.289\times10^{-12}$ of mass	1206
duality gap	$\leq 1.8\times10^{-13}$ across five $C$	1206
the margin note at $C = 2$	on-margin examples have $\alpha_n = C$	1206
closest hull points	$\mathbf{c} = (3,0)$, $\mathbf{d} = (1,0)$, distance $2$	1207
hull-to-SVM conversion, $200$ datasets	$9.185\times10^{-8}$, $4.282\times10^{-8}$, $5.051\times10^{-11}$	1207
hull weights vs multipliers	$5.780\times10^{-8}$	1207
the reduced hull	$\lVert\mathbf{c}-\mathbf{d}\rVert$ $2.00 \to 4.40$; class means $4.5$ apart	1207
polynomial feature dimension at $D=1000$, $p=5$	$8{,}459{,}043{,}543{,}951$	1208
Gram rank saturation	$6$, $10$, $21$ at every $N$	1208
RBF Gram rank	$50 \to 171$ ($\gamma=0.5$); $50 \to 597$ ($\gamma=5$)	1208
$\tanh$ smallest eigenvalue	$-55.44$, $10$ of $120$ negative	1208
four kernels on two rings	$0.6417$, $1.0000$, $1.0000$, $1.0000$	1208
support vectors, linear against degree $2$	$120$ against $\mathbf{6}$	1208
subgradient descent, $10^5$ steps	gap $4.091\times10^{-4}$	1209
both standard-form QPs	$7.105\times10^{-15}$, $2.132\times10^{-14}$	1209
generic solver against LIBSVM	$89\times$, $12{,}349\times$, $49{,}548\times$	1209
max-margin percentile over $192$ datasets	$84.11\%$; best on $6$	1210
a change of units	$0.2638$ of held-out accuracy	1210
standardising first	spread falls to $0.0029$	1210
leave-one-out bound	$0.0333$ against $0.0000$; $0.5500$ against $0.2333$	1210
$C$‘s good plateau	four orders of magnitude	1210
$\gamma = 0.01$ across $C$	$0.7143 \to 0.9965$	1210
$\gamma = 100$ across $C$	never above $0.8375$	1210
SVM scores outside $[-1, 1]$	$74.40\%$	1210
deleting non-support vectors	SVM $0.000000$; logistic offset $0.537167$	1210
$10$ positives against $200$ negatives	recall $\mathbf{0.0000}$	1210

The chapter in twelve lines

1. Chapter 12 reasons geometrically, not probabilistically — closer to Chapter 10’s derivation of PCA than to Chapter 9’s likelihood — and prints no numbers at all.
2. A hyperplane is a set, and a set does not fix its parameters. Distance has no meaning until a scale is chosen, which is what §12.2.1 and §12.2.2 each do differently.
3. Zero training error picks nothing. Thousands of separators fit perfectly and disagree by more than ten points of held-out accuracy.
4. The margin raises the floor rather than the ceiling. It lands at the 84th percentile every time and is almost never the best available.
5. Theorem 12.1’s two formulations agree to seven millionths of a degree, and only one of them is convex — which is why nobody solves Equation 12.10.
6. Slack makes the problem always solvable, and C is the price of a violation, running backwards from the usual regularisation convention.
7. Leaving b unregularised is what makes the answer independent of where the origin sits. Penalising it moves the objective by 10.48 under a shift.
8. The hinge is a convex upper bound on the zero-one loss that reaches exactly zero, and that is the property from which everything else follows.
9. Because the loss reaches zero, most multipliers are zero. Five of eight examples are deletable and five hundred more are addable, both without changing the answer.
10. The dual’s size depends on N and never on D, which is the only reason an infinite-dimensional feature map is usable at all.
11. The same problem read geometrically is: find the two closest points of the two convex hulls, and bisect the segment. The margin is half its length.
12. Scaling a feature is pricing it, and the chapter never mentions standardising — a quarter of a point of accuracy rests on a decision it does not discuss.

Back to the start: Classification Overview