SVMs and the kernel trick

Logistic regression ended with a structured failure: a linear boundary cannot cut a moon or a circle, no matter the threshold. This lesson keeps the linear machinery and fixes the problem twice over — first by asking for the best possible line (maximum margin), then by the kernel trick, which lets that same linear machinery draw boundaries of nearly arbitrary shape without ever materializing the nonlinear features it is implicitly using.

Maximum margin: which separating line?

On separable data, infinitely many hyperplanes achieve zero training error, and lesson 3 showed the MLE runs off to infinity trying to pick one. The SVM’s answer is geometric: choose the hyperplane that maximizes the margin — the distance to the nearest point of either class. A point’s signed distance to the plane $w^\top x + b = 0$ is $(w^\top x + b)/\lVert w \rVert$, so fixing the scale by $y_i(w^\top x_i + b) \ge 1$ makes the margin $1/\lVert w \rVert$, and the problem becomes

— a convex quadratic program. The margin is not aesthetics: fat-margin classifiers have generalization bounds that depend on the margin rather than the dimension, which is the theoretical license for what the kernel trick will shortly do (work in enormous, even infinite-dimensional, feature spaces without automatically overfitting).

Soft margins and the hinge loss

Real data overlap, so allow violations with slack $\xi_i \ge 0$, penalized at rate $C$:

Eliminate $\xi_i = \max(0,\, 1 - y_i(w^\top x_i + b))$ and the constrained program collapses into an unconstrained one that slots straight into this track’s standard template — average loss plus $\ell_2$ penalty:

The hinge is the third member of a family you now know well: 0–1 loss (what we care about, non-convex, unoptimizable), log loss (smooth convex surrogate, cares about probabilities everywhere), hinge (piecewise-linear convex surrogate, cares only until the margin is met, then exactly zero). That flat region is the SVM’s signature: points beyond the margin contribute nothing — remove them and the solution is unchanged. The solution is carried entirely by the support vectors: points on or inside the margin. Sparsity in samples, where lasso gave sparsity in features. The price of the flat region: hinge scores are not probabilities (Platt scaling from lesson 3 exists precisely to fix this). And $C$ is inverse regularization: large $C$ = violations expensive = narrow, hard margin (low bias, high variance); small $C$ = wide, tolerant margin.

The kernel trick

Here is the pivot. The dual form of the QP (and equally the representer theorem for the penalized form) shows the optimal $w$ is a combination of training points, $w = \sum_i \alpha_i y_i x_i$, so both training and prediction touch the data only through inner products $x_i^\top x_j$. Replace every inner product with a kernel function

and you are running the identical linear algorithm in the feature space $\varphi$ — without ever computing $\varphi$. The decision function becomes

Mercer’s condition (the kernel matrix is PSD for every data set) is what guarantees some $\varphi$ exists. The working vocabulary:

The RBF kernel deserves its own paragraph, because its one parameter is the most instructive dial in classical ML. $f(x)$ is a sum of Gaussian bumps of width $\sim 1/\sqrt{\gamma}$ centred on support vectors. Small $\gamma$: bumps overlap broadly, the boundary is nearly linear — high bias. Large $\gamma$: each bump shrinks toward its own point, the boundary becomes islands around individual training samples — memorization, in the most literal visual sense. $\gamma$ is the bias–variance trade-off from the regularization lesson, rendered as geometry, and $(C, \gamma)$ together form the grid every practical SVM tuning sweeps.

Where SVMs sit today

A fair status report for 2026: on tabular problems of moderate size, gradient-boosted trees (two lessons from now) usually win; on raw perception, deep nets ate the kernel lunch — a modern reading is that deep learning learns $\varphi$ instead of fixing it by choosing $K$. SVMs remain the right tool when: data are medium-sized ($n \lesssim 10^5$ — kernel matrices are $O(n^2)$), features are already meaningful, margins matter conceptually, or you need convexity guarantees. And the ideas outlive the tool: max-margin thinking reappears in modern interpolation/implicit-bias research, kernels return as Gaussian processes and as analysis tools for neural networks (NTK), and the hinge → surrogate-loss framework is how classification theory is organized, period.

from sklearn.svm import SVC
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

# ALWAYS scale before an RBF kernel: γ multiplies squared distances,
# so one big-range feature silently owns the kernel.
clf = make_pipeline(StandardScaler(), SVC(kernel="rbf", C=1.0, gamma=1.0))
clf.fit(X_tr, y_tr)
print(clf[-1].n_support_)     # the sample-sparsity: how many SVs carry the model

Exercises