A support vector machine (SVM) is a classifier that draws a linear boundary between two classes, but not just any boundary: the one that leaves the widest possible margin between them. Combined with the kernel trick, that boundary can live in a feature space of huge, even infinite, dimension without anyone having to build it. The name is misleading: it is not a machine but an algorithm (Witten et al., 2017, p. 252); its authors called it a support-vector network (Cortes & Vapnik, 1995).
How it works
Maximum margin. If two classes are linearly separable, infinitely many hyperplanes separate them. The SVM picks the one that stays as far as possible from both: geometrically, the perpendicular bisector of the shortest segment joining the convex hulls of the two classes. The examples lying on the margin are called support vectors, and they are the only ones that matter: all the others could be deleted without moving the decision boundary. Finding them is a constrained quadratic optimization problem (Witten et al., 2017, pp. 253–254).
Kernel. A linear boundary is too poor for almost anything. The idea is to transform the input with a nonlinear function and draw the hyperplane in the new space, where a flat plane can correspond to a curved surface in the original one (Witten et al., 2017, p. 252). The cost explodes: a polynomial of degree 4 or 5 over 200 variables requires a space of about a billion dimensions (Cortes & Vapnik, 1995, p. 275). The trick is that the algorithm only ever uses dot products between examples, and certain kernels compute the dot product of the big space by operating in the small one (Witten et al., 2017, p. 255); Boser et al. (1992) had shown this swap of operations (Cortes & Vapnik, 1995, p. 276). A kernel is, at bottom, a similarity measure, and it can be defined over strings, trees or sets (Witten et al., 2017, p. 273). With a Gaussian kernel, the SVM amounts to a radial basis function network with a center on every example; with a sigmoid kernel, to a multilayer perceptron with one hidden layer (Witten et al., 2017, pp. 256, 270).
Soft margin. Real data overlap. The distinctive contribution of Cortes & Vapnik (1995) was to extend the method to non-separable data, tolerating some training errors in exchange for a wide margin (1995, p. 273); a parameter C, tuned by trial and error, governs the trade-off (Witten et al., 2017, p. 256).
What changed
The Perceptron finds some separating hyperplane, which depends on the order in which it saw the data (Witten et al., 2017, p. 261); the SVM finds the best one in a precise sense. That choice brings stability: since the boundary only moves if the support vectors change, the method resists overfitting even in very high-dimensional spaces (Witten et al., 2017, p. 255). And it brings theory: if the optimal hyperplane separates the data, the expected error is bounded by the ratio of support vectors to training examples, a bound that does not depend on the dimension of the space (Cortes & Vapnik, 1995, pp. 275–276).
On 60,000 handwritten NIST digits, a degree-4 polynomial kernel made 1.1% errors without any knowledge of the geometry of images (Cortes & Vapnik, 1995, pp. 289–290). According to Chollet, kernel methods sent neural networks back into oblivion: they performed very well, had theoretical backing and lent themselves to mathematical analysis (Chollet, 2021, secs. 1.2.2–1.2.3).
How many parameters does it have? What is learned is one coefficient per support vector (in the NIST experiment, between roughly 1,000 and 2,800 for each of the ten classifiers), but the model must store those vectors in full: part of the training set is the model, as in k-nearest neighbors. The implicit polynomial, by contrast, would have more than 10⁸ free parameters (Cortes & Vapnik, 1995, p. 289). The data sheet reflects a point in between.
Limits
With nonlinear kernels, training is slow compared with other methods such as decision trees (Witten et al., 2017, p. 256), and it scales poorly to large datasets. Moreover, the SVM is a shallow method: the kernel is chosen by hand, not learned, so on perceptual problems it needs features designed by experts (Chollet, 2021, sec. 1.2.3). When massive data and GPUs arrived, deep learning displaced it; it remains an excellent choice when data are few and variables many.