Cortes-Vapnik (1995) Support-Vector Networks

Summary

Cortes and Vapnik present the "support-vector network," a learning machine for two-group classification in which input vectors are nonlinearly mapped to a very high-dimensional feature space where a linear decision surface (the maximum-margin hyperplane) is constructed. Their key contribution over the earlier maximum-margin work is to extend the method from the error-free-separable case to non-separable training data via a soft margin, and they demonstrate strong generalization with polynomial feature maps on an optical-character-recognition benchmark against classical algorithms.

Key Claims

• Feature-space linear surface. Map inputs nonlinearly into a high-dimensional feature space and build a linear maximum-margin decision surface there; special properties of that surface (the margin) ensure high generalization.
• Soft margin for non-separable data. Where the 1992 algorithm required perfect separation, this paper introduces slack variables and minimizes $\tfrac12\lVert w\rVert^2 + C\sum_i\xi_i$, tolerating some misclassifications and trading margin against training error through the penalty parameter $C$.
• Strong empirical performance. Polynomial-kernel support-vector networks match or beat the classical learning algorithms in an OCR benchmark study.

Concepts Introduced or Extended

• Support Vector Machine

Entities Mentioned

• Corinna Cortes
• Vladimir N. Vapnik

Quotes

"The idea behind the support-vector network was previously implemented for the restricted case where the training data can be separated without errors. We here extend this result to non-separable training data."

My Take

This is the paper that made support vector machines practical: real data are never perfectly separable, and the soft margin — a single penalty $C$ balancing margin width against training errors — is what turned an elegant but brittle idea into the default classifier of the next decade. It is the natural completion of Boser-Guyon-Vapnik (1992) on the SVM page (hard margin → soft margin), and the $C$-hyperparameter it introduces is exactly the regularization knob that cross-validation tunes in every modern SVM implementation. That the same $\tfrac12\lVert w\rVert^2 + C\sum\xi_i$ objective can be read as hinge-loss-plus-ridge-penalty is what later connected SVMs to the broader regularized-empirical-risk view of machine learning.