Margins, Kernels and the Support Vector Machine

Two classes, linearly separable, infinitely many separating hyperplanes. Logistic regression picks one by maximising likelihood. The support vector machine picks the one that sits as far as possible from the nearest point of either class, and that single change in objective produces a solution determined by a handful of examples rather than by all of them.

For a hyperplane \(w^\top x + b = 0\) with labels \(y_i \in \{-1, +1\}\), scale \(w\) so the closest points satisfy \(y_i(w^\top x_i + b) = 1\). Their distance to the hyperplane is \(1/\|w\|\), so the margin is \(2/\|w\|\) and maximising it means minimising \(\|w\|^2\) subject to \(y_i(w^\top x_i + b) \geq 1\) for all \(i\). A convex quadratic program with linear constraints: one global optimum, no local minima.

Slack, and the hinge loss hiding inside

Real data are not separable, so slack variables \(\xi_i \geq 0\) relax the constraints to \(y_i(w^\top x_i + b) \geq 1 - \xi_i\), and the objective becomes \(\tfrac{1}{2}\|w\|^2 + C\sum_i \xi_i\). At the optimum \(\xi_i = \max(0,\, 1 - y_i(w^\top x_i + b))\), so the whole thing is regularised empirical risk with the hinge loss:

The hinge is zero once a point is correctly classified with margin at least 1 and linear in the violation after that. Compare it to logistic loss, which is never exactly zero: every point, however confidently classified, keeps contributing gradient. The hinge's flat region is what makes the solution sparse in examples, and \(C\) is an inverse regularisation strength, small \(C\) meaning a wider margin with more violations tolerated.

The dual, support vectors, and the kernel trick

Lagrangian duality turns the problem into

with \(w = \sum_i \alpha_i y_i x_i\). Complementary slackness forces \(\alpha_i = 0\) for every point strictly outside the margin, so only points on or inside it, the support vectors, have nonzero weight. Delete every other training point and refit and you get the identical classifier.

The data enter only as inner products \(x_i^\top x_j\). Replace them with \(k(x_i, x_j) = \langle \phi(x_i), \phi(x_j)\rangle\) for any positive semi-definite kernel and you are fitting a maximum-margin hyperplane in \(\phi\)'s feature space without computing \(\phi\). The RBF kernel \(k(x,x') = \exp(-\gamma\|x-x'\|^2)\) corresponds to an infinite-dimensional feature map, which is representable only because you never touch it directly. The representer theorem is the general statement: for any penalised loss over a reproducing kernel Hilbert space with a monotone penalty on the norm, the minimiser is a finite combination of kernels evaluated at the training points.

When it breaks

The kernel matrix is \(n \times n\). At \(n = 100{,}000\) that is 80 GB in double precision, and training is roughly \(O(n^2)\) to \(O(n^3)\). Kernel SVMs are excellent up to tens of thousands of examples and impractical far beyond without approximation: Nyström, random Fourier features, or dropping to a linear SVM where specialised solvers scale nearly linearly.

Prediction cost grows with the support set. Each prediction evaluates the kernel against every support vector. On noisy data with small \(C\), a large fraction of the training set becomes support vectors, and the "sparse" model is not sparse; inference cost degrades toward nearest-neighbour territory.

No probabilities. The output is a signed distance, not a calibrated probability. Platt scaling fits a sigmoid to that score on held-out data, which works but is a bolt-on with its own overfitting risk, and it is the reason logistic regression is usually preferred wherever a probability is needed downstream.

Everything hinges on the kernel and its scale. RBF requires tuning \(\gamma\) and \(C\) jointly over a two-dimensional grid, and the model is genuinely sensitive to both; features must be standardised because \(\|x - x'\|\) is scale-dependent. Choosing a kernel is choosing an inductive bias, and unlike a neural network, an SVM cannot learn the representation for you. That, more than any accuracy comparison, is why kernel methods gave ground to deep learning on perceptual data while remaining strong on small, well-featurised problems.