Support Vector Machines (SVM)

SVMs were the dominant supervised classifier from roughly 1995 to 2012 — the period between the perceptron's revival and the AlexNet moment. They are still the right answer for many small-data, structured problems, and the kernel trick they popularized is reborn in modern attention mechanisms.

The geometric idea

Given linearly separable data $\{(x_i,y_i){\}}_{i=1}^n$ with $y_i\in \{-1,+1\}$, find the hyperplane $w^{\mathrm{\top }}x+b=0$ that maximizes the margin — the distance to the nearest training point.

This gives the hard-margin primal:

$$\underset{w,b}{min}\frac{1}{2}\Vert w{\Vert }^2\text{s.t.}{y}_i(w^{\mathrm{\top }}{x}_i+b)\ge 1,\mathrm{\forall }i.$$

Soft margin (Cortes & Vapnik, 1995)

Real data is rarely separable. Introduce slack ${\xi }_i\ge 0$:

$$\underset{w,b,\xi }{min}\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^n{\xi }_i\text{s.t.}{y}_i(w^{\mathrm{\top }}{x}_i+b)\ge 1-{\xi }_i.$$

The hyperparameter $C$ trades off margin width against training error.

The dual & support vectors

The Lagrangian dual is

$$\underset{\alpha }{max}\sum _i{\alpha }_i-\frac{1}{2}\sum _{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^{\mathrm{\top }}{x}_j\text{s.t.}0\le {\alpha }_i\le C,\sum _i{\alpha }_i{y}_i=0.$$

Only points with ${\alpha }_i>0$ matter — these are the support vectors. The dual depends on $x_i$ only through inner products $x_i^{\mathrm{\top }}{x}_j$, which is exactly what enables the kernel trick.

The kernel trick

Replace $x_i^{\mathrm{\top }}{x}_j$ with a positive-definite kernel $k(x_i,x_j)=⟨\varphi (x_i),\varphi (x_j)⟩$ that implicitly maps inputs to a high-dimensional feature space. Common choices:

• Linear: $k(x,x^{\prime })=x^{\mathrm{\top }}{x}^{\prime }$
• Polynomial: $k(x,x^{\prime })=(x^{\mathrm{\top }}{x}^{\prime }+c{)}^d$
• RBF / Gaussian: $k(x,x^{\prime })=\exp (-\gamma \Vert x-x^{\prime }{\Vert }^2)$

The RBF kernel makes SVMs universal approximators on bounded inputs.

Why SVMs still matter

1. They give a principled large-margin classifier for tabular and small-sample problems.
2. The dual / kernel formulation generalises to many other tasks (kernel PCA, Gaussian processes, kernel ridge regression).
3. Modern self-attention is, viewed at one angle, a learned kernel similarity between tokens — see Transformer Era · 2017.

What to read next

• Kernel Methods & The Kernel Trick
• The Perceptron — the SVM's ancestor.
• The Kernel Era (1995–2010) — historical context.

Stub status

Seed introduction. Expand with hinge loss / sub-gradient view, SMO solver, multi-class extensions, and structural SVMs.