Support vector machines and kernels

The widest street

Take linearly separable data with labels $y_i\in\{-1,+1\}$ and a linear classifier $f(\mathbf{x}) = \mathbf{w}^\top\mathbf{x}+b$. Infinitely many hyperplanes separate the classes; which one should we trust? The SVM answer: the one with the largest margin, i.e. the widest empty street between the classes, because a wide street tolerates the most perturbation of future points.

The distance from a point $\mathbf{x}_i$ to the hyperplane is $|\mathbf{w}^\top\mathbf{x}_i+b|/\|\mathbf{w}\|$ (1.1 Vectors, dot products and norms). Since $(\mathbf{w},b)$ and $(c\mathbf{w},cb)$ describe the same hyperplane, fix the scale so that the closest points satisfy $y_i(\mathbf{w}^\top\mathbf{x}_i+b)=1$. Then the street has width $2/\|\mathbf{w}\|$, and maximizing it is

This is a convex quadratic program with a unique solution — no local minima, unlike neural networks.

Soft margins and the hinge loss

Real data overlap, so allow violations with slack variables $\xi_i\ge0$:

Eliminating $\xi_i = \max(0,\,1-y_i f(\mathbf{x}_i))$ turns this into an unconstrained regularized loss:

So an SVM is "hinge loss + L2 regularization" (3.6 Regularization and generalization), just as logistic regression is "log loss + L2". The hinge is zero for points beyond the margin, so they do not influence the solution at all; log loss $\log(1+e^{-yf})$ never reaches zero, so every point keeps pulling. $C$ is the inverse regularization strength: large $C$ approaches the hard margin (narrow street, high variance), small $C$ tolerates violations for a wider street (higher bias, lower variance).

The dual and the support vectors

Introduce multipliers $\alpha_i\ge0$ for the constraints (1.10 Optimization: from gradient descent to Adam). The Lagrangian of the hard-margin problem is $\mathcal{L}=\tfrac12\|\mathbf{w}\|^2-\sum_i\alpha_i[y_i(\mathbf{w}^\top\mathbf{x}_i+b)-1]$. Setting derivatives to zero gives

and substituting back yields the dual problem:

Complementary slackness says $\alpha_i>0$ only for points on or inside the margin — the support vectors. Everything else has $\alpha_i=0$ and could be deleted without changing the classifier. The decision function becomes

which depends on the data only through inner products $\mathbf{x}_i^\top\mathbf{x}$. That observation is the door to kernels.

The kernel trick

Replace every inner product by $k(\mathbf{x},\mathbf{z}) = \phi(\mathbf{x})^\top\phi(\mathbf{z})$ for some feature map $\phi$ — without ever computing $\phi$. The classifier becomes linear in feature space and curved in input space.

Worked example: the polynomial kernel $k(\mathbf{x},\mathbf{z})=(\mathbf{x}^\top\mathbf{z})^2$ in $\mathbb{R}^2$ expands as

so a single multiplication-and-square does the work of a 3-dimensional feature map; for degree $d$ in $n$ dimensions the implicit space has $\binom{n+d}{d}$ features. The RBF (Gaussian) kernel $k(\mathbf{x},\mathbf{z})=\exp(-\gamma\|\mathbf{x}-\mathbf{z}\|^2)$ corresponds to an infinite-dimensional $\phi$; $\gamma$ sets how local the similarity is — large $\gamma$ makes each support vector influence only its neighbourhood (wiggly boundary, overfitting), small $\gamma$ approaches a linear classifier. A valid kernel must give a positive semi-definite Gram matrix (Mercer's condition): a kernel is nothing more than a legitimate similarity function.

Intuition. A kernel SVM is a weighted kNN in disguise (3.4 k-Nearest Neighbors): the prediction is a weighted sum of similarities to a few remembered training points (the support vectors), with weights learned to maximize the margin.

In practice

Scale features first — SVMs are not scale-invariant. Grid-search $C\in\{10^{-2},\dots,10^{3}\}$ and $\gamma\in\{10^{-4},\dots,10^{1}\}$ on log scales with cross-validation; look at the number of support vectors (a very high fraction signals overfitting or a too-local $\gamma$). Kernel SVM training is $O(n^2)$–$O(n^3)$ in the number of samples, so beyond roughly $10^5$ rows use LinearSVC or SGD with hinge loss, or approximate kernels with random Fourier features. For probabilities, calibrate (Platt scaling or isotonic). On typical tabular data, GBDTs (3.9 Ensembles: bagging, random forests and gradient boosting) usually win; SVMs shine on small, high-dimensional, clean problems (text with TF-IDF features, bioinformatics) and as strong, fast baselines.

Kernels everywhere

The dual view generalizes far beyond SVMs (the representer theorem: regularized solutions live in the span of the training points). Kernel ridge regression and Gaussian processes replace the hinge with squared loss. And the pattern "compute a similarity between a query and stored keys, then weight stored values" is exactly scaled dot-product attention, whose similarity $\mathbf{q}^\top\mathbf{k}$ is a linear kernel (7.2 Scaled dot-product and multi-head attention, fully derived), and exactly embedding search, whose cosine similarity is a normalized linear kernel (9.2 Embeddings deep dive).

Where this shows up later

• Hinge loss in the loss catalog — 4.3 Loss functions catalog; regularization strength as bias–variance control — 3.6 Regularization and generalization, 3.5 Evaluating models: metrics, validation and the bias–variance trade-off.
• Attention as kernel-weighted retrieval — 7.2 Scaled dot-product and multi-head attention, fully derived; embedding similarity and vector search — 9.2 Embeddings deep dive, 9.3 Vector search and indexes; contrastive losses that learn similarity functions — 5.8 Self-supervised and contrastive learning.