Textbook of AI

Also known as: SVM, support-vector network

A support vector machine (SVM) is a maximum-margin classifier introduced in its modern soft-margin form by Cortes and Vapnik in 1995. Given training data {(x_i, y_i)} with labels y_i ∈ {±1}, the SVM finds the hyperplane w·x + b = 0 that maximises the margin, the distance from the hyperplane to the nearest training point on either side, subject to all points being correctly classified (in the hard-margin case) or to a small number of margin violations being penalised (in the soft-margin case).

The optimisation is a convex quadratic program with a unique global solution, in contrast to neural-network optimisation. Its dual formulation depends only on inner products x_i · x_j of training points, allowing the kernel trick: replace x_i · x_j with a kernel K(x_i, x_j) corresponding to an inner product in some implicit feature space. Standard kernels include the polynomial K(x, y) = (x·y + 1)^d, the RBF (Gaussian) K(x, y) = exp(−γ ‖x − y‖²) and string kernels for sequence data. The kernel trick lets SVMs operate in arbitrarily high (even infinite) dimensional feature spaces without ever materialising those features.

The points whose dual variables are non-zero, the support vectors, are the only training points that affect the decision boundary. Their number is typically a small fraction of the training set, and provides an efficient sparse representation.

SVMs were the dominant supervised-learning method from roughly 1995 to 2012, displacing neural networks for most applications. AlexNet's 2012 ImageNet result triggered the deep-learning revival and SVMs receded from the spotlight. They remain useful for small-to-medium-sized datasets, for problems with strong margin structure, and as theoretical objects with clean generalisation guarantees through VC theory.