Era 2 · Foundations · 1995

10 SVM

Support-Vector Networks · Cortes & Vapnik · Machine Learning

🟧 read selectively~2 horiginal ↗

The gist in 20 seconds. A classifier that maximizes the margin to the nearest points (the "support vectors"). A soft margin tolerates mistakes, the kernel trick builds nonlinear boundaries in an implicit high-dimensional space, and the problem is convex — a unique optimum. It dominated classification for some 15 years.

Context

The 1990s, neural networks out of fashion. Vapnik and Cortes (Bell Labs) deliver a powerful, theoretically grounded classifier with convex optimization and strong generalization.

The idea and the mechanism

Among all separating hyperplanes we take the one that maximizes the margin — the distance to the nearest points of both classes. A large margin → better generalization. Soft margin: slack variables let points violate the margin, and the parameter C balances its width against the number of violations. Kernel trick: the algorithm depends on the data only through inner products, and by replacing them with a kernel K(x, x′) we build a linear boundary in an implicit high-dimensional space = a nonlinear one in the original.

convex optimization The dual problem: why only the support vectors decide

The primal problem. Maximizing the margin = minimizing the norm subject to separability:

min_w,b 12‖w‖² subject to y_i(w·x_i + b) ≥ 1

The Lagrangian introduces multipliers α_i ≥ 0; the stationarity conditions give w = Σ α_i y_i x_i and Σ α_i y_i = 0. Substituting them back yields the dual problem (which depends only on inner products → this is where the kernel goes in):

max_α Σ_i α_i − 12 Σ_i,j α_i α_j y_i y_j K(x_i, x_j) subject to 0 ≤ α_i ≤ C, Σ_i α_i y_i = 0

Soft margin = a "box" constraint. It is the soft margin that turns the plain α_i ≥ 0 into the box constraint 0 ≤ α_i ≤ C: the upper bound C caps the influence of any single point, letting it violate the margin for a finite penalty (that is the slack). As C → ∞ we are back to the hard margin, where violations are forbidden.

The KKT condition (complementary slackness): α_i [y_i(w·x_i+b) − 1] = 0. So α_i > 0 only for the points sitting on the margin — those are the support vectors; the rest have no influence. The decision function:

f(x) = Σ_{i ∈ SV} α_i y_i K(x_i, x) + b

scikit-learn An SVM with an RBF kernel

from sklearn.svm import SVC

clf = SVC(kernel='rbf', C=1.0).fit(X, y)   # convex problem → unique optimum
print(clf.support_vectors_.shape)          # only the support vectors decide
# f(x) = Σ αᵢ yᵢ K(xᵢ, x) + b,  where αᵢ > 0 only for support vectors

The maximum-margin boundary (blue) and the "street" of the margin (dashed). The points outlined in bold at the edge of the margin are the support vectors; they alone determine the solution.

Analogy. Between two neighbourhoods you lay the widest street you can, so that the houses of neither side stick out onto the roadway. The position of the street is fixed only by the houses right on the edge (the support vectors) — what sits deeper in the neighbourhood is irrelevant. The wider the street, the more robust the boundary is to new houses.

Why it matters

For ~15 years the SVM was the default strong classifier; it is still good on small and medium data. "Margin maximization" and "the kernel trick" are general mathematical ideas that reach far beyond SVMs. Vapnik's famous bet (1995): by 2000 "nobody in their right mind will use neural networks" — he nearly got it right, but deep learning took its revenge in 2012.

Connections

↔ echoes3. Perceptron

Both are linear separators tied to the margin γ. The perceptron merely uses the margin (to guarantee convergence), the SVM maximizes it — it picks the most robust plane rather than any separating one.

↔ rival16. AlexNet

The SVM was the king of classification that Vapnik backed against neural networks. AlexNet (2012) won ImageNet by a landslide and ended the era of kernel methods dominating vision — a direct historical answer to that bet.

↔ another classic12. Random Forests

The two pillars of "classical ML" in the 2000s. The SVM is convex optimization + kernels, strong in high dimensions; the random forest is an ensemble of trees, strong on tabular data with heterogeneous features. Both are still solid baselines outside deep learning.

Questions worth asking

The kernel trick works in an "infinite-dimensional" space (RBF) — why does that not lead to overfitting?

Because complexity is controlled not by the dimension of the space but by the margin. Vapnik's theory ties generalization to the margin, not to the number of features (just like the (R/γ)² bound for the perceptron). A large margin plus regularization through C limits the effective capacity, even if the implicit space is infinite-dimensional.

If only the support vectors decide, why keep all the data during training?

You do not know in advance which points will become support vectors — the optimization works that out. After training most α are zero, and prediction needs only the SVs (often a small fraction of the data) — hence the compact model. But the training problem itself looks at all pairs (hence its ~O(n²–n³) cost, which is what limits SVMs on large data).

Why did SVMs lose ground, beautiful as they are in theory?

Three reasons: (1) they scale badly to millions of examples (quadratic in the number of points); (2) the kernel has to be chosen by hand, whereas neural networks learn the representation themselves; (3) on large data, learned features beat fixed kernels. The beauty of the theory did not save it from the fact that deep learning scales better.

What to read in the original

Read selectively: the max-margin formulation, support vectors, the kernel trick. The derivation of the dual (the math box) is worth it — it is a model of how a convex problem is rewritten into a form where a kernel slots in naturally.