SVMs: The Kernel Trick, Maximum Margin, and When They Still Win

SVMs fell out of fashion when deep learning arrived, but they remain the right answer in several important regimes: small tabular datasets, high-dimensional text, and any setting where you need an interpretable margin guarantee. More importantly, the kernel trick is one of the most intellectually beautiful ideas in all of machine learning — every practitioner should understand it.

Support Vector Machines are linear classifiers that find the maximum-margin separating hyperplane. The margin is the distance between the hyperplane and the nearest training points from each class (the support vectors). Maximising the margin is a geometric intuition for why SVMs generalise: larger margin means less sensitivity to small perturbations in the data.

The primal formulation

Binary classification: find w, b such that y_i(w^T x_i + b) ≥ 1 for all i, minimising ||w||². The constraint says all points must be on the correct side of the hyperplane with at least unit margin. The decision boundary is w^T x + b = 0; the margin is 2/||w||, so minimising ||w||² maximises the margin.

Hard-margin SVM: only works when data is linearly separable. Soft-margin SVM (Cortes & Vapnik, 1995): allow some misclassification via slack variables ξ_i ≥ 0. Minimise ||w||² + C Σ ξ_i subject to y_i(w^T x_i + b) ≥ 1 - ξ_i. C is the regularisation parameter: large C = low tolerance for violations = tighter fit, small C = high tolerance = smoother boundary. This is the bias-variance trade-off in geometric form.

The dual formulation and why it matters

The SVM primal has d+1 parameters (w and b, where d is the feature dimension). The Lagrangian dual transforms this into an n-dimensional problem with one dual variable α_i per training point: maximise Σ α_i - (1/2) Σ_{i,j} α_i α_j y_i y_j x_i^T x_j. The critical insight: the optimisation only depends on dot products x_i^T x_j between training examples, not on the raw features themselves. This is the door through which the kernel trick walks.

The kernel trick

A kernel function k(x_i, x_j) = φ(x_i)^T φ(x_j) computes the dot product in a high-dimensional (possibly infinite-dimensional) feature space φ(·) without ever computing φ explicitly. Substitute k(x_i, x_j) for x_i^T x_j in the dual: the SVM now learns a decision boundary in an infinite-dimensional space, tractably. Common kernels: Polynomial k(x,z) = (x^T z + c)^d — captures degree-d feature interactions. RBF (Radial Basis Function / Gaussian): k(x,z) = exp(-γ ||x-z||²) — infinite-dimensional feature space, captures arbitrary smooth decision boundaries. The γ hyperparameter controls the reach of each training point. Sigmoid: k(x,z) = tanh(γ x^T z + r) — equivalent to a two-layer neural network in some parameter regimes.

Mercer's theorem: a function k is a valid kernel if and only if the kernel matrix K_{ij} = k(x_i, x_j) is positive semi-definite for any set of points. This is the mathematical guarantee that k corresponds to a valid dot product in some feature space.

Prediction and the support vectors

At test time, the prediction for a new point x is: f(x) = sign(Σ_i α_i y_i k(x_i, x) + b). The sum runs over all training points, but α_i > 0 only for support vectors — points on or inside the margin boundary. For well-separated data, most α_i = 0, making prediction sparse and fast. The number of support vectors relative to the training set size is an informal measure of problem difficulty.

Multi-class SVMs

SVMs are inherently binary. Extensions: One-vs-One (OvO): train C(C-1)/2 classifiers, each distinguishing one class pair; predict by majority vote. One-vs-Rest (OvR): train C classifiers, each distinguishing one class vs. all others; predict the class with highest margin score. OvO is slower to train but often more accurate; OvR is faster.

When SVMs still win

Text classification with TF-IDF features: the feature space is already sparse and high-dimensional; RBF kernels work well. Small datasets (n < 10k): XGBoost and neural nets need more data to outperform SVMs. Tabular data with clear geometric structure: the maximum margin guarantee is still meaningful. Anomaly detection (One-Class SVM): see Post 95. When SVMs lose: large n (O(n²) kernel matrix), image/audio data (deep learning dominates), when features need to be learned end-to-end.

SVM vs logistic regression

Both are linear classifiers. SVM maximises the geometric margin (loss is 0 outside the margin, grows linearly inside). Logistic regression maximises the log-likelihood (loss is smooth everywhere, all points contribute to the gradient). SVMs are sparser (only support vectors matter). Logistic regression gives calibrated probabilities. In practice, with proper regularisation, the two converge to similar performance on most problems.

Try on Colab: use the UCI Breast Cancer dataset. Train an SVM with RBF kernel, tuning C and γ via GridSearchCV with 5-fold cross-validation. Visualise the decision boundary in PCA-2D space and highlight the support vectors. Compare test accuracy, training time, and number of support vectors across C values from 0.01 to 100. Then repeat with a polynomial kernel of degree 2 and 3.