Algorithms as math assemblies

Modules 01–07 handed you the parts: matrices, derivatives, probability, information, optimisation. This module is the assembly line. Eight algorithms, each stripped down to the objective it minimises, the assumption it makes, and the exact piece of math that holds it up — because once you can name the parts, you can predict how each one breaks.

Model answers

1 · Ordinary least squares — the one with a closed form

What it assumes. The target is a linear function of the features, $f(x) = x^\top w$, plus noise that is independent, mean-zero and constant-variance. That noise story is not decoration: Module 04 showed that Gaussian noise + maximum likelihood is squared-error loss, so minimising $\|Xw-y\|^2$ is not a convention — it is the maximum-likelihood estimate of $w$ under that noise model.

The math. Stack the data in $X \in \mathbb{R}^{n\times d}$ and minimise the squared error. Expand the derivative, using the fact that $X^\top X$ is symmetric:

The same result has a picture, and the picture is the part worth keeping. $Xw$ is a combination of the columns of $X$, so the predictions live in the column space of $X$; least squares asks for the point of that space closest to $y$, which is its orthogonal projection (Module 02). Closest means the error vector $e = y - Xw$ is perpendicular to every column of $X$ — and "perpendicular to every column" written with dot products is exactly the normal equation again:

When it wins. Small and medium $d$ (up to a few thousand), features that are genuinely independent, and any time you need the answer in one pass with no hyperparameters to tune. When it breaks — four distinct ways, each with its own fix:

The gradient-descent version, as a preview. When $n$ and $d$ are in the millions, $X^\top X$ is too big to form, so you minimise the same objective by stepping downhill (Module 07):

2 · Ridge and Lasso — the closed form gets a constraint

What they assume. The same linear model, plus a belief that no single feature should carry the whole prediction: the weights should be small. That belief has a name — it is the bias you add to trade a little training error for a lot less variance (Module 05's bias–variance lever).

Ridge: the math. Add an $\ell_2$ penalty and differentiate as before — the only change is one extra term in the gradient:

Why this survives a singular $X^\top X$ is a two-line argument you already own from Module 02 (positive definiteness) — for any $\lambda \gt 0$ and any $x \ne 0$:

Module 07's Lagrangian view says the same thing from the other side: the penalised problem is the constrained one, $\min \|Xw-y\|^2$ subject to $\|w\|_2^2 \le t$, with $\lambda$ playing the role of the multiplier that enforces the budget. You choose $\lambda$; it tells you how big a weight ball the solution must live in.

Lasso: the $\ell_1$ version. Same model, different penalty — and the closed form disappears:

What you get instead is sparsity. The geometric reason is worth one picture: at the optimum, the ellipse of the loss surface touches the constraint region. For ridge that region is a sphere, and an ellipse touches a sphere at a generic point — every coordinate nonzero. For lasso it is a diamond ($\ell_1$ ball) with sharp corners on the axes, and ellipses like to catch corners: at a corner, some $w_j$ is exactly zero. Those zeros are why lasso doubles as feature selection, and why it is the default weapon for genomics-style data where $d \gg n$ — thousands of features, a handful of samples, and you want the three genes that matter.

The coefficient path, as $\lambda$ grows. Ridge shrinks every weight smoothly toward zero (all of them, none ever exactly zero); lasso zeroes features out one at a time, in order of usefulness. Elastic net splits the difference, $\lambda_1\|w\|_1 + \lambda_2\|w\|_2^2$, and fixes a real lasso weakness: when features are correlated, lasso picks one arbitrarily and discards its twins, while the $\ell_2$ part keeps correlated groups together.

3 · Logistic regression — the closed form disappears, the gradient does the work

What it assumes. A binary label generated from a probability that is a linear function of the features, pushed into $(0,1)$ by a link function. The link is the sigmoid:

Invert it and the model reads in log-odds — the linear model is not on the probability, it is on the log-odds $\log\frac{p}{1-p} = w^\top x$. That gives every coefficient a unit you can quote in a meeting: one extra unit of feature $j$ multiplies the odds of class 1 by $e^{w_j}$. A coefficient of 0.7 means the odds roughly double ($e^{0.7} \approx 2.0$); a coefficient of $-1$ divides them by $e$.

The math. Labels are Bernoulli given $x$, so the likelihood is the product of $p_i^{y_i}(1-p_i)^{1-y_i}$ over samples (Module 04). Maximise its logarithm, negate, and you have the loss:

Differentiate it, and here is the lovely structural fact of this whole module. Using $\sigma'(z) = \sigma(z)(1-\sigma(z))$, the $n$ per-sample terms collapse into one matrix expression — identical in shape to the least-squares gradient, with the residuals swapped:

Why is there no closed form then? Set that gradient to zero and you get $X^\top(\sigma(Xw)-y) = 0$, a system that is non-linear in $w$ — the sigmoid has no inverse that isolates $w$ from a sum. There is nothing to solve for. What remains is the good news from Module 07: the loss is convex, so plain gradient descent converges to the global optimum, and you will run it by hand below.

Multiclass: softmax regression. One weight vector per class, and the link becomes the softmax, which is the sigmoid's many-class sibling:

When it wins. This is the everyday production classifier for a reason: convex (no seed lottery), one row per feature of interpretation, cheap to train, and — its genuine strength over trees and boosting — its output probabilities are usually calibrated, meaning "0.8" really means about 80%. When it breaks: the boundary is a hyperplane. Anything a straight line cannot separate — XOR, concentric circles — it cannot learn, however much data you give it. Fix: add features (kernels, splines, interactions) or change model.

4 · Naive Bayes — Bayes plus an independence assumption

What it assumes. A generative story: first draw the class from its prior, then draw each feature independently from the class's distribution. Logistic regression (previous section) is discriminative — it models $p(y\mid x)$ directly and says nothing about how $x$ was produced. Naive Bayes models $p(x,y)$ and gets $p(y\mid x)$ by Bayes' rule (Module 04), paying one assumption for everything:

Why the assumption is wrong but the classifier still works. Features are never independent (height and weight, word counts in a sentence). But the product only has to get the ranking right, and correlated features mostly double-count the same evidence in both classes — the inflation cancels when you compare class 1 to class 2. Module 04's own block demonstrated it: Gaussian NB scored 0.832 against logistic regression's 0.844 on data whose features were correlated. The ranking survives; the numbers do not (see the overconfidence pitfall below).

The variants differ only in what "$p(x_j\mid y)$" means:

Laplace smoothing, and the one line of math that forces it. The product form has a knife edge: if the training data contains a single class $c$ in which feature $j$ never appeared, then $\hat p(x_j\mid c) = 0$, and

The fix is to refuse exact zeros: add a pseudo-count $\alpha$ before normalising, $\hat p(x_j\mid c) = \frac{n_{jc} + \alpha}{N_c + \alpha V}$ (usually $\alpha=1$, "add-one"). It is the counting version of the prior from Module 04 — a small belief inserted where the data was silent.

When it wins: tiny data, many features, embarrassingly parallel counting (training is one pass over the data — no optimiser at all), $O(d)$ prediction. When it breaks: anywhere you need the probabilities themselves. Because correlated evidence is counted repeatedly, the product of many terms pushes posteriors to 0 or 1 — Naive Bayes is notoriously overconfident. Rank with it; do not quote its 0.9999.

5 · k-means — alternating optimisation

What it assumes. Nothing probabilistic at all: the data is $K$ clumps, each well described by a centre, and "a good clustering" means small within-cluster squared distance:

The math is two alternating half-solutions. You cannot minimise over assignments and centres at once — but each half alone is trivial, so k-means alternates them.

1. Assignment step. Fix the centres, move each point to its nearest one. The set of points assigned to centre $k$ is exactly the Voronoi cell of $\mu_k$ — the region of space closer to $\mu_k$ than to any other centre — so the optimal assignment is a geometric fact, not a search.
2. Update step. Fix the assignments, move each centre to its cluster mean. The mean is not a convention either: it is the minimiser, one gradient away. For one cluster, $\nabla_\mu \sum_{i\in C}\|x_i-\mu\|^2 = -2\sum_{i\in C}(x_i-\mu) = 0 \Rightarrow \mu = \bar{x}_C$.

Each step leaves the objective unchanged or smaller, and the objective cannot go below zero — so the process terminates. What it terminates at is a local optimum: a partition no single point move or centre move can improve, possibly far from the best one. That is why k-means needs restarts, and why k-means++ (spread the initial centres by sampling proportionally to squared distance) is the default initialisation in every library — better starts, better local optima, same iterations.

Choosing $k$, and how it fails

Neither number falls out of the objective — inertia always prefers larger $k$. Two standard detectors: the elbow plots inertia against $k$ and looks for the knee where gains collapse (it measures only within-cluster compactness); the silhouette scores each point $s = (b-a)/\max(a,b)$, where $a$ is its distance to its own cluster and $b$ to the nearest other one — so it measures compactness against separation, in $[-1,1]$. Elbows lie when clusters have unequal variance; silhouettes are honest but $O(n^2)$.

6 · PCA — the algorithm you can now fully derive

Module 02 section 11 derived PCA's engine (eigenvectors of the covariance matrix); section 12 gave you the Eckart–Young theorem. This section is the assembly: one algorithm, three statements that turn out to be the same statement.

Why equivalent? The total variance of the data is fixed, and it splits exactly: variance kept along the $k$ directions + energy lost in the reconstruction error = total (Parseval's identity, applied to the SVD expansion). Maximise one term of a fixed sum and you minimise the other — so "directions that see the most" and "directions you can least afford to drop" are the same directions, and Eckart–Young says those directions are the top singular vectors.

The algorithm, in five steps (each one you have already run in Module 02's code):

Two details decide whether your PCA means anything. Standardise before you centre whenever features carry different units — a feature in euros varies 10⁴ times more than one in radians, so its variance, and therefore PC1, reflects your unit choice, not your data (Module 02's pitfall box). And select $k$ by explained variance: keep the components holding 90–95% of $\sum_i\lambda_i$ — the fraction is printed by PCA(n_components=...).explained_variance_ratio_.

One real use: feed the 30 retained components to a classifier instead of the original 2 000 features — you cut training time, remove directions that were pure noise, and often improve test accuracy (the denoising effect: the low-variance tail is where noise hides). One misuse: reading the components as features. PC1 is a weighted mix of all input features, its sign is arbitrary, and it is blind to the target — "PC7 predicts churn" is not a statement you can act on. For interpretable predictors, use the model; for compression and visualisation, use PCA.

7 · Decision trees, forests, boosting — information theory as a splitting rule

What it assumes. Almost nothing — which is the point. A tree is recursive binary splitting: at each node, pick the feature $j$ and threshold $t$ that make the two children as pure as possible, and repeat. No linear model, no distance metric, no distribution. The search is greedy, because the exact answer (the best tree over all subsets of features and thresholds) is NP-hard — one sentence, and it explains every overfitting symptom you will meet.

The math is Module 06's, wearing a decision hat. Impurity measures how mixed a node is:

Concrete numbers, so it is not a symbol: a 50/50 node has entropy 1 bit and Gini 0.5. Split it into two children that are each 90/10, and the weighted child entropy is 0.469 bits — the split removed $1 - 0.469 = 0.531$ bits, and that is the split a tree takes.

Overfitting and its three levers. A deep tree can memorise: limit it with max_depth, min_samples_leaf, or prune back after growing. The bias–variance story (Module 05 section 9) is textbook here: a shallow tree has near-zero variance and high bias (it cannot express much); a deep tree has near-zero bias on training data and enormous variance (one flipped label near a threshold reshapes a whole branch).

Forests fix the variance. Random forests average many deep trees, each fitted to a bootstrap resample and each seeing only a random subset of features at every split. Averaging reduces variance (Module 05) as long as the trees are not identical — hence the feature randomness, which decorrelates them. Bias barely moves; variance collapses.

Boosting fixes the bias. Trees are grown sequentially, each new one fitted to the mistakes of its predecessors. In one line each: AdaBoost reweights misclassified points and is exactly coordinate descent on the exponential loss; gradient boosting takes the loss $L(y, \hat y)$, computes the negative gradient $-\partial L / \partial \hat y$ per training point (the "pseudo-residuals"), and fits a regression tree to it. That second sentence is bigger than it looks: gradient descent from Module 07, generalised from weight space to function space, for any differentiable loss — square it and you get least-squares boosting, take logs and you get log-loss boosting, and XGBoost/LightGBM are this loop with cleverer trees and second-order terms.

8 · Support vector machines — geometry as the whole story

What it assumes. That the classes are separable by some boundary, and that among all separating hyperplanes the fattest one is the best. Maximise the margin; the constraints say every point sits at least one margin-width on the right side:

The "wider street is better" claim is not aesthetic: it is Module 05's variance argument. A boundary that threads between two close points is fitted to those points (high variance); a wide-street boundary barely moves when any single point moves (low variance), so it generalises. Small $\|w\|$, smooth boundary, low variance — three phrasings of one idea.

Soft margin. Real data is not separable, so slack variables $\xi_i$ let point $i$ violate its constraint by a price $C$ — written out with the Lagrangian (Module 07's KKT machinery):

Eliminating the slack variables gives the form libraries actually optimise — the hinge loss plus the same regulariser, unconstrained:

That zero-gradient region is why SVMs are robust to outliers that lie far on the correct side: they are already paying nothing. The KKT conditions mark exactly which points do pay: support vectors are the points with $\alpha_i \gt 0$ — those on or inside the margin. Delete every other point and the solution does not change: the entire model is defined by a handful of borderline cases.

The dual, and why it opens the door to kernels. Solving the Lagrangian for $w$ and substituting back gives the dual problem, where $w$ has vanished and the data survives only inside dot products:

This is the reason the dual matters: the algorithm never sees the features, only their pairwise $K$. Choose $K(x,z) = \phi(x)^\top\phi(z)$ for some enormous $\phi$ and you have implicitly moved to a space where the data might be linearly separable — without ever writing $\phi$ down. The standard choice is the RBF kernel $K(x,z) = \exp(-\gamma\|x-z\|_2^2)$, which corresponds to an infinite-dimensional feature space: nearby points get weight near 1, distant ones near 0, and the decision boundary becomes a smooth contour hugging the data. $\gamma$ and $C$ are the two knobs: $\gamma$ controls how far the influence of one point reaches.

Why SVMs faded for big data, and what survived. The dual's quadratic program scales $O(n^2)$ to $O(n^3)$ in the number of samples — with a million rows it simply stops, while a forest or a logistic model trains on a laptop. But the ideas did not fade: margins are the vocabulary of generalisation in deep learning (max-margin classifiers, large-margin softmax), kernels live on inside PCA (kernel PCA) and Gaussian processes, and dual methods with $\alpha$ weights are the backbone of support vector and attention-style reweightings you will meet in Module 09.

9 · The selection map

Everything above, compressed into the reference you will actually use: which backbone, which knob, which failure. When you meet a new algorithm, find its nearest row and ask what the row's backbone does to it.

If you remember only one thing, per algorithm

Block 1 · OLS from scratch — closed form vs gradient descent vs sklearn

Three routes to the same answer. If they disagree by more than machine precision, something upstream is broken — this is the cheapest sanity check in the whole notebook.

import numpy as np
from sklearn.linear_model import LinearRegression

rng = np.random.default_rng(0)
n, d = 200, 5
X = rng.normal(size=(n, d))
w_true = np.array([1.5, -2.0, 0.0, 3.0, 0.5])   # note the third coefficient is exactly zero
y = X @ w_true + rng.normal(scale=0.5, size=n)   # Gaussian noise: OLS is the MLE (Module 04)

# 1) the normal equation, one line
w_norm = np.linalg.solve(X.T @ X, X.T @ y)

# 2) the same objective by gradient descent (Module 07's engine)
w_gd = np.zeros(d)
for _ in range(2000):
    w_gd -= 0.1 * 2 * X.T @ (X @ w_gd - y) / n   # gradient of ||Xw - y||^2 / n

# 3) sklearn solves by SVD and never forms an inverse;
#    fit_intercept=False because we generated data with no intercept
w_sk = LinearRegression(fit_intercept=False).fit(X, y).coef_

print("normal eq :", np.round(w_norm, 4))   # [ 1.5386 -2.0429 -0.0157  3.0203  0.5539]
print("grad desc :", np.round(w_gd, 4))     # same to 4 decimals
print("sklearn   :", np.round(w_sk, 4))     # same to 4 decimals
print("max |norm - gd|      : %.2e" % np.abs(w_norm - w_gd).max())      # 4.00e-15
print("max |norm - sklearn| : %.2e" % np.abs(w_norm - w_sk).max())      # 3.55e-15

Two observations. The gradient descent answer agrees to $4\times10^{-15}$ — not because GD is magic, but because the loss is a convex quadratic, so 2 000 steps of a modest learning rate land in the same bowl. And the third coefficient came back as $-0.0157$ against a true $0$: least squares has no reason to produce an exact zero, it only shrinks noise. That gap is precisely the hole lasso fills.

Block 2 · Logistic regression from scratch — the gradient, literally

import numpy as np
from sklearn.datasets import make_classification
from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import train_test_split

X, y = make_classification(n_samples=500, n_features=2, n_redundant=0,
                           n_informative=2, class_sep=2.0, random_state=7)
X = (X - X.mean(0)) / X.std(0)                   # GD needs comparable axes
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.25, random_state=0)

def sigmoid(z): return 1 / (1 + np.exp(-z))

w = np.zeros(3)                                  # 2 weights + bias
for _ in range(10000):
    p = sigmoid(Xtr @ w[:2] + w[2])
    err = p - ytr                                # "residuals" -- exactly OLS's shape
    w[:2] -= 1.0 * (Xtr.T @ err) / len(ytr)      # grad_w = X^T (sigmoid(Xw) - y) / n
    w[2]  -= 1.0 * err.mean()                    # the bias is a column of ones

acc_tr = ((sigmoid(Xtr @ w[:2] + w[2]) > 0.5) == ytr).mean()
acc_te = ((sigmoid(Xte @ w[:2] + w[2]) > 0.5) == yte).mean()
print("scratch  train %.4f  test %.4f  w=%s" % (acc_tr, acc_te, np.round(w, 3)))
# scratch  train 0.9787  test 0.9600  w=[0.502 6.863 1.06 ]

clf = LogisticRegression(C=1e6, max_iter=5000).fit(Xtr, ytr)   # C huge ~ unpenalised
w_sk = np.r_[clf.coef_[0], clf.intercept_[0]]
print("sklearn  train %.4f  test %.4f  w=%s" % (clf.score(Xtr, ytr), clf.score(Xte, yte),
                                                np.round(w_sk, 3)))
# sklearn  train 0.9787  test 0.9600  w=[0.501 6.863 1.061]
print("max |w_scratch - w_sklearn|:", np.abs(w - w_sk).max())   # 8.2e-4

The gradient is the two-line formula from section 3, implemented literally: predictions minus targets, times the features, averaged. Note the honest touch — C=1e6 makes sklearn's default L2 regularisation negligible, so both are solving the same unpenalised problem; with sklearn's default $C=1$ the weights shrink noticeably (its $w_2$ lands near 4.6 instead of 6.9) while the accuracy barely moves. That gap between "coefficients" and "predictions" is regularisation in one screenshot.

Block 3 · k-means from scratch — watch the objective fall (and watch it get stuck)

import numpy as np
from itertools import permutations
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans

X, y = make_blobs(n_samples=400, centers=4, cluster_std=1.1, random_state=42)

def sq_dists(X, mu):                             # (k, n) squared distances
    return np.stack([((X - m) ** 2).sum(1) for m in mu])

def run(X, mu, iters=25):
    mu, hist = mu.copy(), []
    for _ in range(iters):
        sq = sq_dists(X, mu)
        assign = sq.argmin(0)                    # assignment step: nearest centre
        hist.append(float(sq.min(0).sum()))      # objective, recorded before the update
        mu = np.stack([X[assign == k].mean(0) for k in range(len(mu))])   # update: the mean
    return hist, assign

rng = np.random.default_rng(0)
runs = [run(X, X[rng.choice(len(X), 4, replace=False)]) for _ in range(10)]
finals = [h[-1] for h, _ in runs]
best_h, best_a = runs[int(np.argmin(finals))]
print("final inertia of 10 random starts:", sorted(round(v, 1) for v in finals))
# [927.5, 927.5, 927.5, 927.5, 927.5, 927.5, 927.5, 2960.2, 2960.4, 2961.4]
print("best run, inertia per iteration  :", [round(v, 1) for v in best_h[:6]], "...", round(best_h[-1], 1))
# [20790.8, 12187.4, 11678.6, 6027.0, 932.8, 927.5] ... 927.5
print("monotone decreasing:", bool(np.all(np.diff(best_h) <= 1e-9)))   # True

km = KMeans(n_clusters=4, n_init=10, random_state=0).fit(X)   # k-means++ initialisation
print("my best-of-10 : %.1f   sklearn (++): %.1f" % (best_h[-1], km.inertia_))
best = max(np.mean(best_a == np.array(p)[km.labels_]) for p in permutations(range(4)))
print("same partition up to relabelling: %.3f" % best)         # 1.000

Read the two printed lines together. The objective fell every single iteration — the alternating-minimisation guarantee, observed. But three of the ten random starts froze at ≈2960 instead of 927: same guarantee, worse local optimum, no warning. That is the entire argument for k-means++ and for n_init restarts — and the reason clustering answers deserve a second look before you believe them.

Block 4 · Trees and ensembles — the bias–variance pattern, on the same data

import numpy as np
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier, GradientBoostingClassifier

# features 0..5 informative, 6..7 linear copies of them, 8..9 pure noise
X, y = make_classification(n_samples=2000, n_features=10, n_informative=6, n_redundant=2,
                           n_clusters_per_class=1, class_sep=1.2, flip_y=0.01, random_state=3)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=3)

models = {
    "tree, depth 2 (high bias)":       DecisionTreeClassifier(max_depth=2, random_state=0),
    "tree, depth 12 (high variance)":  DecisionTreeClassifier(max_depth=12, random_state=0),
    "random forest, 300 trees":        RandomForestClassifier(n_estimators=300, random_state=0),
    "gradient boosting, 200 trees":    GradientBoostingClassifier(n_estimators=200, random_state=0),
}
for name, m in models.items():
    m.fit(Xtr, ytr)
    print("%-32s train %.3f   test %.3f" % (name, m.score(Xtr, ytr), m.score(Xte, yte)))
# tree, depth 2 (high bias)      train 0.929   test 0.937
# tree, depth 12 (high variance) train 1.000   test 0.973
# random forest, 300 trees       train 1.000   test 0.993
# gradient boosting, 200 trees   train 1.000   test 0.992

imp = models["random forest, 300 trees"].feature_importances_
print("importance on informative features 0-5 : %.2f" % imp[:6].sum())   # 0.94
print("importance on junk features 6-9        : %.2f" % imp[6:].sum())   # 0.06

The four rows are the bias–variance curve of Module 05, walked left to right: the depth-2 tree cannot fit the data even on training samples (0.929 — bias-limited); the depth-12 tree fits training perfectly and loses 2.7 points on test (variance); averaging 300 decorrelated trees recovers almost all of it (variance down, bias untouched); boosting chases the remaining bias and also lands at 0.992. The importance line is information gain's fingerprint: 94% of the forest's split gains sit on the six features that actually generate the labels.

Block 5 · SVM — the margin, and the points that define it

import numpy as np
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
from sklearn.svm import SVC
from sklearn.model_selection import train_test_split

X, y = make_moons(n_samples=400, noise=0.25, random_state=0)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0)

for C in (0.1, 1.0, 100.0):
    clf = SVC(kernel="rbf", C=C).fit(Xtr, ytr)
    print("C=%-6g test acc %.3f   support vectors %d of %d training points"
          % (C, clf.score(Xte, yte), clf.support_.size, len(Xtr)))
# C=0.1    test acc 0.925   support vectors 152 of 280
# C=1      test acc 0.942   support vectors 82 of 280
# C=100    test acc 0.942   support vectors 55 of 280

clf = SVC(kernel="rbf", C=1.0).fit(Xtr, ytr)
xx, yy = np.meshgrid(np.linspace(X[:, 0].min() - .5, X[:, 0].max() + .5, 300),
                     np.linspace(X[:, 1].min() - .5, X[:, 1].max() + .5, 300))
Z = clf.decision_function(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
plt.figure(figsize=(6, 4.5))
plt.contour(xx, yy, Z, levels=[-1, 0, 1], linestyles=["--", "-", "--"], alpha=.7)
plt.scatter(Xtr[:, 0], Xtr[:, 1], c=ytr, s=18, cmap="coolwarm")
sv = clf.support_vectors_
plt.scatter(sv[:, 0], sv[:, 1], s=90, facecolors="none", edgecolors="k",
            linewidths=1.6, label="%d support vectors" % len(sv))
plt.legend(); plt.title("SVM: boundary, margin lines, support vectors")
plt.savefig("svm_moons.png", dpi=110, bbox_inches="tight")

The moons are not linearly separable, and a linear boundary is not even close — the RBF kernel smuggles in the infinite-dimensional feature map and draws a curved boundary. The count line is the concept becoming concrete: at $C=1$, 82 of the 280 training points are the model; the other 198 could be deleted with no change to the boundary. And as $C$ grows, the margin tightens to obey more points, so the support vector count falls — exactly the slack-variable story from section 8.

Multiple choice — instant feedback

Open questions — answer aloud, without notes

Re-answer these in 1 day, 3 days, and 7 days from memory. Questions 1 and 2 are derivations — do them on paper with no peeking; a derivation you can rebuild is the only kind that survives. Questions 3 and 6 should eventually come out in under a minute each.