Source Summary: Cortes & Vapnik 1995 — Support-Vector Networks
Full title: Support-Vector Networks
Authors: Corinna Cortes, Vladimir Vapnik
Affiliation: AT&T Bell Labs
Venue: Machine Learning, 20, 273–297 (1995)
PDF: papers/cortes-1995-support-vector-networks.pdf
Contributions
- Support Vector Machine (SVM) — a learning machine that maps inputs to a high-dimensional feature space and finds the maximum-margin linear separator; the dominant classification algorithm from ~1995 to ~2012.
- Soft margin — extends the hard-margin SVM to non-separable data by allowing misclassifications penalized by a slack variable; makes SVM practical on real data.
- Kernel trick — implicit mapping to high-dimensional feature space via kernel functions (polynomial, RBF, etc.); avoids explicitly computing the feature map.
- Statistical learning theory foundation — SVMs maximize the margin, which is provably related to minimizing the VC dimension and thus controlling generalization error.
Core Idea
The SVM maps input x through a non-linear mapping φ: x → Z (feature space), then finds the hyperplane in Z that:
- Separates the two classes
- Maximizes the margin — the distance from the hyperplane to the nearest training point (support vector)
Decision function: f(x) = sign(w · φ(x) + b)
Optimization: maximize 2/||w|| (margin)
subject to: yᵢ(w · φ(xᵢ) + b) ≥ 1 for all i
The points that lie exactly on the margin boundaries are the support vectors — typically a small subset of the training 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. The kernel trick replaces inner products ⟨φ(xᵢ), φ(xⱼ)⟩ with a kernel function K(xᵢ, xⱼ):
K(xᵢ, xⱼ) = ⟨φ(xᵢ), φ(xⱼ)⟩
Common kernels:
- Polynomial: K(x, y) = (x·y + c)
- RBF (Gaussian): K(x, y) = exp(-||x−y||²/2σ²)
- Sigmoid: K(x, y) = tanh(αx·y + c)
This lets SVMs implicitly work in infinite-dimensional spaces without computational overhead.
Soft Margin SVM
For non-separable data, introduce slack variables ξᵢ ≥ 0:
Minimize: ½||w||² + C·Σξᵢ
Subject to: yᵢ(w·φ(xᵢ) + b) ≥ 1 − ξᵢ, ξᵢ ≥ 0
C controls the trade-off between margin width and misclassification penalty. Small C = wide margin, more errors tolerated; large C = narrow margin, fewer errors tolerated.
Why SVMs Dominated (1995–2012)
At their peak, SVMs were the best general-purpose classifier on most tasks:
- Strong theoretical guarantees (VC theory, structural risk minimization)
- Worked well with small-to-medium datasets
- The kernel trick gave them flexibility without overfitting
- No need for hyperparameter tuning beyond C and the kernel parameters
- Convex optimization → global optimum guaranteed
Neural networks in the 1990s–2000s required careful initialization, regularization, and tuning, and often underperformed SVMs on benchmark tasks. This is why “AI Winter II” effectively froze neural network research until ~2006.
Why SVMs Lost to Deep Learning
SVMs failed at scale:
- Kernel computation: O(n²) to O(n³) training cost with n training samples
- ImageNet: 1.2M images made SVM training impractical
- Feature engineering: SVMs still required hand-crafted input features; deep learning learned features end-to-end
- Expressive capacity: fixed kernel limits representation power; deep networks can learn hierarchical features
AlexNet (2012) won ILSVRC with 15.3% error vs. the SVM-based runner-up’s 26.2% — a gap large enough to end the SVM era.
Key Results (from paper)
- Evaluated on OCR (handwritten digit recognition) and face detection
- Polynomial SVM: 1.4% error on MNIST, competitive with contemporary neural networks
- Key finding: SVM generalizes well even in very high-dimensional feature spaces — the margin, not the dimension, controls generalization
Key References (from paper)
- Vapnik & Chervonenkis 1974 — VC theory (statistical learning theory foundation)
- Boser, Guyon & Vapnik 1992 — original hard-margin SVM with kernels
- Rumelhart et al. 1986 — backpropagation (the competing approach)