41 SVM & Kernels

TL;DR

The support vector machine (Cortes & Vapnik, 1995) classifies by finding the hyperplane with the largest margin to the nearest points, and the kernel trick lets it draw non-linear boundaries by working in an implicit high-dimensional space without ever computing the coordinates. SVMs were the dominant classifier from 1995 until deep learning displaced them on perception around 2012.

41.1 The max-margin idea

Many hyperplanes separate two classes; the SVM picks the one that maximizes the margin — the distance to the closest training points (the support vectors). For separable data this is:

\[ \min_{w,b}\ \tfrac{1}{2}\|w\|^2 \quad\text{s.t.}\quad y_i(w^\top x_i + b)\ge 1\ \forall i. \]

A wide margin is a strong inductive bias toward generalization — only the support vectors matter, so the solution is sparse in the data. A soft-margin slack variant tolerates a few violations for non-separable data.

41.2 The kernel trick

Linear boundaries are limiting. The trick: the SVM only ever needs inner products \(x_i^\top x_j\), so replace them with a kernel \(K(x_i, x_j) = \phi(x_i)^\top \phi(x_j)\) that computes the inner product in a richer feature space \(\phi\) — without ever forming \(\phi(x)\):

\[ K_{\text{RBF}}(x, x') = \exp\!\big(-\gamma \|x - x'\|^2\big), \qquad K_{\text{poly}}(x, x') = (x^\top x' + c)^d. \]

The RBF kernel maps into an infinite-dimensional space, giving the SVM flexible non-linear boundaries at the cost of just a kernel evaluation per pair.

41.3 Timeline context

With good hand-engineered features (SIFT, HOG) plus an RBF SVM, this was the champion recipe for vision and many classification tasks for ~17 years. The 2012 AlexNet result ended that era: learned features beat engineered ones, and the SVM-on-top pipeline gave way to end-to-end deep nets. SVMs remain excellent on small/medium, low-dimensional problems where data is too scarce to train a deep model.

Key takeaway

The SVM combines a principled objective (max margin → good generalization) with the kernel trick (non-linearity for free via inner products). It was the pre-deep-learning default and is still strong when data is limited — but it relies on features supplied to it, which is exactly what deep learning learned to supply for itself.

← Back to: Classical ML Overview