Support vector machines: The widest margin wins

The event and the narrow claim

In September 1995 the journal Machine Learning published "Support-Vector Networks" by Corinna Cortes and Vladimir Vapnik of AT&T Bell Labs in Holmdel, New Jersey, a paper first received in May 1993 and accepted in February 1995 ( Cortes and Vapnik's paper). Its conclusion names the three ideas it combines: the optimal hyperplane, which expresses the solution through a small set of training points called support vectors; a "convolution of the dot-product" that lets a linear method draw curved boundaries; and soft margins, which tolerate errors on the training set. Only the third was new in this paper. The first two had been joined three years earlier by Bernhard Boser, Isabelle Guyon and Vapnik in a training algorithm for optimal margin classifiers, presented at the 1992 Workshop on Computational Learning Theory in Pittsburgh.

The narrow claim is therefore specific. Cortes and Vapnik showed how to keep the maximal-margin machinery when no clean separating boundary exists, which is the normal condition of real data, and they demonstrated it on handwritten digits, where a polynomial machine with no built-in knowledge of images matched Bell Labs' best purpose-built neural network. The broader judgment, that this method became the default classifier of machine learning for roughly fifteen years, rests on what others built after 1995: the solvers, the free software, the applications and the habits of practice. This report keeps the two levels apart. The paper itself called its machine a support-vector network and drew it as a two-layer network; the name that stuck, support vector machine, is the one Joachims and others were using by 1998.

A theory built in Moscow, tested in New Jersey

The theory behind the method predates the machine by two decades. At Moscow's Institute of Control Sciences, Vapnik and Alexey Chervonenkis developed what became Vapnik-Chervonenkis theory, a landmark statement of which is their 1971 paper on the uniform convergence of relative frequencies of events to their probabilities. The theory asks when a rule that fits a finite sample will also fit new data, and it answers with a capacity measure, now called the VC dimension, rather than with a raw count of parameters. According to the Franklin Institute's laureate profile, the importance of this work was not widely recognized until Vapnik made an extended visit to the United States in 1989; he emigrated in 1991 to join AT&T Bell Labs.

Cortes and Vapnik open their paper by placing the method in a lineage of linear decision rules. Fisher's 1936 discriminant was linear. Rosenblatt's perceptrons combined many linear units into piecewise linear surfaces, and backpropagation in the 1980s trained such networks by gradient descent. Vapnik's own contribution, which the paper dates to 1965, was the optimal hyperplane: among all straight boundaries that separate two classes without error, choose the one with the widest margin to the nearest points of each class. The paper restates the bound that made this attractive. For separable data, the expected test error of an optimal hyperplane is bounded by the expected number of support vectors divided by the number of training examples, and the bound does not mention the dimension of the space. A boundary pinned by a few dozen points out of thousands should generalize, however many coordinates it lives in. For readers of this archive, the idea completes a story begun by the perceptron: Rosenblatt's rule found some separating line, while Vapnik's asked which one.

The 1992 step: margins meet kernels

The obstacle to using optimal hyperplanes on hard problems was that real classes are rarely separated by a straight boundary in their raw inputs. The classical remedy was to map each input into a larger set of features, such as all products of pairs of pixels, and separate the classes linearly there. Cortes and Vapnik spell out the cost with a concrete example: a polynomial decision surface of degree 4 or 5 on a 200-dimensional input may require a hyperplane in a space of about a billion dimensions. Storing such vectors is impractical, and fitting so many free parameters invites overfitting.

Boser, Guyon and Vapnik removed the storage problem by reversing the order of operations. Because the optimal hyperplane can be written entirely in terms of dot products between training points, one never needs the giant feature vectors themselves, only a function that returns their dot product directly from the original inputs. For polynomial features that function is the ordinary dot product of two inputs, plus one, raised to the chosen degree. Their 1992 abstract states that the algorithm applies to perceptrons, polynomials and radial basis functions, expresses its solution as a combination of the supporting patterns closest to the boundary, and gives generalization bounds from leave-one-out estimates and the VC dimension. The 1995 paper credits the device of computing feature-space dot products through a function to Aizerman, Braverman and Rozonoer's 1964 work on potential functions, and identifies Mercer's theorem as the condition a function must meet to play that role. What was new in 1992 was the pairing: a margin criterion with guarantees, made computable in feature spaces far too large to write down. This combination is what later textbooks call the kernel trick.

What the soft margin added

The 1992 machine had one serious restriction: it assumed the training data could be separated without a single error. Real data contains mislabeled examples, overlapping classes and noise, and for such problems no hard margin exists at all. Cortes and Vapnik attached a non-negative slack variable to every training point, measuring how far it falls on the wrong side of its margin, and minimized a combination of the margin term and the slack, weighted by a constant C. A large C punishes errors heavily; a small C tolerates more of them in exchange for a wider margin. Points that sit on the margin or violate it become the support vectors, and only they determine the final classifier.

Two properties survived the change, and they explain much of the method's later appeal. First, the problem remained a quadratic program, which is convex: it has a single optimum, and a competent solver reaches it from any starting point. A backpropagation network, by contrast, could land in different solutions depending on its initialization and learning rate. Second, in the dual form the data still enters only through dot products, so the kernel trick carries over unchanged. AT&T treated the idea as commercially valuable. A patent application titled Soft margin classifier, naming Cortes and Vapnik, was filed on 30 June 1994 and granted in June 1997, and a related pattern recognition patent using support vectors, naming Boser, Guyon and Vapnik, was granted the following month. Both have since expired.

The evidence on handwritten digits

The experiments used handwritten digits, the same problem on which Bell Labs colleagues had built LeNet. On a US Postal Service set of 7,300 training and 2,000 test images at 16 by 16 pixels, a linear machine erred on 12.0 percent of test digits. Polynomial machines of degree 2 to 7 reached 4.2 to 4.7 percent while each digit classifier kept only about 127 to 190 support vectors, even as the implicit feature space grew from roughly 33,000 dimensions to about 10 to the 16th. Raising the dimension by many orders of magnitude barely moved the error, as the theory predicted. For comparison the paper lists human error at 2.5 percent, two decision tree methods at 16 and 17 percent, the best two-layer neural network at 6.6 percent and a specialized five-layer network at 5.1 percent.

The headline came from a larger set: 60,000 training and 10,000 test digits at 28 by 28 pixels, mixed from NIST's collections, the configuration LeCun and colleagues later documented as MNIST. With two weeks for a benchmark study, the authors built one type of classifier, a degree-4 polynomial with no preprocessing, and the ten classifiers combined reached 1.1 percent test error. In the same benchmark a linear classifier scored 8.4 percent, three-nearest-neighbor 2.4 percent, LeNet-1 1.7 percent, and LeNet-4, a convolutional network engineered for the task, 1.1 percent. The authors quote their colleagues' observation that the result was remarkable because the machine encodes nothing about image geometry: it would have done as well if every image's pixels were scrambled by one fixed random permutation.

LeCun's 1998 survey added the cost side. A regular SVM reached 1.4 percent on the standard test set, and Schölkopf's virtual support vector variants reached 1.0 and then 0.8 percent, but recognition with the original SVM took about 14 million multiply-adds per character, against roughly 401,000 for LeNet-5. Burges's reduced-set SVM cut that to 650,000 at 1.1 percent error. The best result in the survey, 0.7 percent, belonged to boosted LeNet-4. On digits, kernels and convolutional networks finished close to a tie, with the networks far cheaper to run.

From a laboratory result to the default classifier

What turned a strong benchmark into a standard tool was a run of results in domains far from digit reading. In 1998 Thorsten Joachims applied SVMs to text categorization. On the Reuters-21578 collection, with 9,603 training and 3,299 test news stories, 90 topic categories and 9,962 distinct terms, the best conventional method, k-nearest neighbors, reached a microaveraged precision and recall breakeven of 82.3; polynomial and radial basis SVMs reached 86.0 and 86.4 while using every feature, with no feature selection and no sign of overfitting. Text suited the method well: thousands of sparse features, few of them irrelevant.

Training speed was the next barrier, because a quadratic program over tens of thousands of examples was heavy for 1990s hardware. John Platt's Sequential Minimal Optimization, a Microsoft Research report of April 1998, broke the problem into the smallest possible subproblems, each solved analytically, with memory linear in the training set, and reported speedups of more than 1,000 times over the standard chunking method on sparse real-world data. Joachims released SVMlight, free for scientific use. Chih-Chung Chang and Chih-Jen Lin at National Taiwan University began LIBSVM in 2000; their documentation reports more than 250,000 downloads from 2000 to 2010 and representative uses in computer vision, language parsing, neuroimaging and bioinformatics. Their practical guide, first issued in 2003, reduced the method to a recipe: scale the data, start with a radial basis kernel, and choose C and the kernel width by a cross-validated grid search.

The applications followed. In 2000 Brown and colleagues used SVMs to classify yeast genes by function from microarray data, 2,467 genes measured across 79 experiments, and found that SVMs outperformed Parzen windows, Fisher's linear discriminant and two decision tree learners. In the first two ImageNet challenges, before deep networks arrived, the winning entries classified engineered image features with SVMs: a stochastic SVM for NEC in 2010 and one-versus-all linear SVMs for XRCE in 2011 (see ImageNet). Writing in 2009 about the ACM Paris Kanellakis award to Cortes and Vapnik, Google research director Fernando Pereira called the soft-margin SVM the supervised method of choice for tasks from image analysis to document classification to bioinformatics.

Why practitioners trusted it

The trust SVMs earned had a specific basis. Training was repeatable: the same data and settings produced the same model. The convex objective meant no local minima, no learning-rate schedules and no initialization folklore. There were few knobs, typically C and one kernel parameter, which a grid search could cover. And the method came with a theory explaining, at least in outline, why a model in an enormous feature space need not overfit. Joachims went further and showed that a VC-dimension estimate could pick good settings for his text classifiers automatically, so that no manual tuning was needed.

Even critics granted the point. Bengio and LeCun, arguing for deep networks in 2007, wrote that the trade-off between convex and non-convex learning had for years favored research on convex methods. The kernel approach meanwhile spread beyond two-class classification, to regression, to one-class SVMs for estimating where data lies, and to learning rankings, which LIBSVM and SVMlight implemented for anyone who downloaded them. Formal recognition followed: the 2008 Kanellakis award, which honors theory with practical impact, and the Franklin Institute's 2012 Benjamin Franklin Medal to Vapnik, whose profile credits his work, and the SVM in particular, with practical uses ranging from fraud detection and handwriting recognition to medical diagnosis and DNA analysis.

The case against shallow templates

The criticism that eventually carried the day was sharpest in Bengio and LeCun's chapter on scaling learning algorithms towards AI. They called kernel machines shallow: one wide layer of template matchers, comparing each new input with stored training examples, followed by one trainable linear combination. Such machines can approximate any function in principle, they argued, but may need impractically many templates and examples to do so, and kernels that measure only local similarity suffer from the curse of dimensionality. Their evidence was NORB, a dataset of photographed toy objects. On its jittered and cluttered version, a Gaussian-kernel SVM on raw pixels had a test error of 43.3 percent, the convolutional network LeNet-7 reached 7.2 percent, and a hybrid that fed the network's learned features into an SVM reached 5.9 percent. The authors were advocates, so the comparison is partisan, but the numbers are reported in full, and the hybrid result locates the real issue: the kernel was a fixed, hand-chosen similarity, while the network learned its representation.

Cost was the second weakness. Training needs a kernel value for pairs of examples, so the kernel matrix grows with the square of the training set; the LIBSVM documentation notes that this dense matrix may be too large to store and must be computed on demand and cached. Recognition cost grows with the number of support vectors. Rahimi and Recht's random features of 2007 attacked the problem by approximating a kernel with a randomized, low-dimensional feature map, so that fast linear methods could stand in for the kernel machine. The fix worked, but it conceded that exact kernel machines did not scale to the data volumes arriving in the late 2000s.

Displacement after 2012

AlexNet's 2012 ImageNet victory did not end SVMs at once. For a time they survived as the final layer on top of learned features. The R-CNN object detector, first posted in November 2013, computed convolutional features for about 2,000 region proposals per image and then classified each region with class-specific linear SVMs, reaching 53.7 percent mean average precision on PASCAL VOC 2010 against 35.1 percent for a bag-of-visual-words system using the same proposals. In 2015 Fast R-CNN dropped the separately trained SVMs in favor of a softmax classifier fine-tuned together with the network, and found softmax slightly ahead, by 0.1 to 0.8 points of mean average precision. The SVM stage, which had required writing features to disk and training in separate passes, no longer earned its place.

That sequence shows why deep learning displaced kernel methods rather than merely beating them on one benchmark. Once networks could learn the representation end to end on GPUs from millions of labeled images, a convex classifier on top added little, and the method's guarantees covered only that last step. Cortes and Vapnik had pointed to the opening themselves: in 1995 they wrote that further gains should come from dot-product functions that encode prior knowledge of the problem. Choosing kernels was a form of feature engineering, and learned features won that contest. Bengio and LeCun had already named the 2006 deep belief network work as a sign that deep architectures could be trained after all.

The honest limits

Several cautions apply to the original claim and to the legend that grew around it. The 1995 benchmark was small by later standards, run in two weeks with one classifier type, and its 1.1 percent tied rather than beat LeNet-4; on digits the better networks eventually pulled ahead. The guarantees were real but loose: the support vector bound covers the separable case and holds only in expectation, and in practice C and the kernel width were chosen by cross-validation rather than by theory, as the LIBSVM guide itself recommends. The theory also failed to travel. Zhang and colleagues showed in 2016 that standard image networks can fit completely random labels, so capacity arguments of the VC type cannot by themselves explain why those networks generalize. The framework that made SVMs trustworthy says little about the models that replaced them.

The displacement story has limits too. A 2014 study by Fernández-Delgado and colleagues tested 179 classifiers on 121 datasets, largely from the UCI repository, and found the Gaussian-kernel SVM in LIBSVM statistically indistinguishable from the best random forest, at 92.3 versus 94.1 percent of the maximum accuracy ( their JMLR paper). On small and tabular problems SVMs stayed competitive long after vision moved on, so "displaced" describes perception and large-scale learning, not every use.

How to place support vector machines in AI history

Support vector machines are best read as the high point of a statistical, theory-first approach to learning that ran from the late 1990s to the early 2010s, between the first neural network revival and the second. The 1995 paper supplied the missing piece, tolerance for errors, that turned an elegant 1992 construction into a method for real data. Fast solvers, free software and a decade of applications did the rest. Its rivalry with convolutional networks began inside one laboratory on one problem, handwritten digits, and the later argument for depth was in large part an argument against the shallow architecture it represented.

The connection did not end with displacement. In 2018 Jacot, Gabriel and Hongler showed that a very wide network trained by gradient descent behaves like a kernel method governed by a neural tangent kernel, giving deep learning theorists a route back to the mathematics SVMs had made familiar. The lasting contributions are the margin as a principle of generalization, convex formulations where they fit, and the discipline of asking why a model should work on data it has not seen. The lasting lesson of its decline is equally clear: a fixed similarity measure, however principled, is no substitute for representations learned from data.

References

• Cortes and Vapnik (1995). Support-Vector Networks.
• Boser, Guyon and Vapnik (1992). A Training Algorithm for Optimal Margin Classifiers.
• Vapnik and Chervonenkis (1971). On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities.
• The Franklin Institute (2012). Vladimir Vapnik, Benjamin Franklin Medal in Computer and Cognitive Science.
• Google Patents (1997). US5640492A: Soft margin classifier.
• Google Patents (1997). US5649068A: Pattern recognition system using support vectors.
• LeCun, Bottou, Bengio and Haffner (1998). Gradient-Based Learning Applied to Document Recognition.
• Joachims (1998). Text Categorization with Support Vector Machines: Learning with Many Relevant Features.
• Platt, Microsoft Research (1998). Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines.
• Joachims (2008). SVMlight: Support Vector Machine.
• Chang and Lin (2011). LIBSVM: A Library for Support Vector Machines.
• Hsu, Chang and Lin (2003). A Practical Guide to Support Vector Classification.
• Brown et al. (2000). Knowledge-based analysis of microarray gene expression data by using support vector machines.
• Russakovsky et al. (2015). ImageNet Large Scale Visual Recognition Challenge.
• Pereira, Google Research (2009). And the award goes to.
• Bengio and LeCun (2007). Scaling Learning Algorithms towards AI.
• Rahimi and Recht (2007). Random Features for Large-Scale Kernel Machines.
• Girshick, Donahue, Darrell and Malik (2014). Rich feature hierarchies for accurate object detection and semantic segmentation.
• Girshick (2015). Fast R-CNN.
• Zhang et al. (2017). Understanding deep learning requires rethinking generalization.
• Fernández-Delgado et al. (2014). Do we Need Hundreds of Classifiers to Solve Real World Classification Problems?.
• Jacot, Gabriel and Hongler (2018). Neural Tangent Kernel: Convergence and Generalization in Neural Networks.