Support-Vector Networks
Authors: Corinna Cortes, Vladimir Vapnik
Year: 1995 | Machine Learning
Source: cortes-1995-support-vector-networks
What it is
The paper that made SVMs practical — extending the hard-margin classifier to real, non-separable data via a soft margin and a kernel trick. From ~1995 to ~2012, SVMs were the dominant classification algorithm: theoretically grounded, computationally tractable, and reliably outperforming neural networks on the benchmarks of the era. Their eventual defeat by AlexNet (2012) marks the end of the symbolic/classical ML era and the beginning of the deep learning era.
The core idea
Map input x through φ(x) to a high-dimensional feature space Z, then find the maximum-margin hyperplane in Z:
Decision rule: f(x) = sign(w · φ(x) + b)
Maximize: margin = 2 / ||w||
Subject to: yᵢ(w · φ(xᵢ) + b) ≥ 1 − ξᵢ (soft margin)
ξᵢ ≥ 0, C·Σξᵢ bounded
The support vectors are the training points that lie on the margin boundaries — typically a small fraction of the data. The solution depends only on these points, not on the full dataset.
The kernel trick
Computing φ(x) explicitly for high-dimensional feature spaces is intractable. But the SVM optimization only requires inner products ⟨φ(xᵢ), φ(xⱼ)⟩, which can be evaluated implicitly via a kernel function:
Polynomial: K(x,y) = (x·y + c)^d
RBF: K(x,y) = exp(−||x−y||²/2σ²)
An RBF kernel implicitly maps to an infinite-dimensional space while remaining computationally tractable. The model expressiveness is determined by the kernel choice, not by the number of parameters.
Why SVMs dominated 1995–2012
Neural networks in the 1990s and 2000s were notoriously difficult to train:
- No good initialization strategy for deep networks
- Sigmoid/tanh activations → vanishing gradients
- Hyperparameter sensitivity (learning rate, architecture)
- No principled regularization
SVMs had none of these problems:
- Convex optimization → guaranteed global optimum
- Kernel trick → flexible representation without depth
- Statistical learning theory → generalization bounds based on margin
- Single key hyperparameter (C) with clear interpretation
On benchmark datasets (UCI, OCR, text classification), SVMs consistently beat neural networks through the 2000s. This is the “AI Winter II” from the connectionism timeline.
Why SVMs lost in 2012
| Factor | SVM | Deep CNN |
|---|---|---|
| Training cost | O(n²)–O(n³) | O(n) per epoch |
| Feature engineering | Required | Learned end-to-end |
| Scalability to millions of images | Impractical | Feasible (GPU) |
| Hierarchical features | Not learned | Learned layer by layer |
| ImageNet top-5 error (2012) | 26.2% | 15.3% (AlexNet) |
The SVM’s fatal limitation was that the kernel was fixed before training — it couldn’t adapt to the data structure the way deep networks can. On small, well-understood datasets with good features, SVMs are hard to beat. On large raw-input datasets (images, text, audio), deep networks learn better representations.
The theoretical contribution: margin and generalization
SVMs connect to Vapnik-Chervonenkis (VC) theory: the generalization error of a classifier is bounded by its VC dimension (a measure of complexity). Maximizing the margin provably minimizes the VC dimension of the classifier, independent of the dimension of the feature space.
This was a major theoretical result: you could build a classifier in infinite-dimensional space and still get finite generalization bounds, because the margin — not the dimension — controls complexity.
See also
- rosenblatt-1958-the-perceptron-a-probabilistic-model — The learning machine SVMs competed with and temporarily surpassed
- krizhevsky-2012-imagenet-classification-with-deep-convolutional — AlexNet: the paper that ended the SVM era
- hinton-2006-a-fast-learning-algorithm-for — The deep learning revival that set up AlexNet