Support vector machine

What it is

A support vector machine (SVM) is a supervised maximum-margin model used for classification and regression analysis ^[1]. The scikit-learn documentation describes support vector machines as a set of supervised learning methods used for classification, regression and outliers detection ^[2]. What distinguishes the model from many others is the principle behind its decision boundary: instead of fitting a curve through the data and stopping when the error is small enough, it looks for the widest clean gap that can be placed between the classes.

How it works

Given two classes of points, many straight lines or surfaces can separate them. The SVM picks the maximum-margin hyperplane, the one that maximises the distance to the nearest points of either class ^[1]. That distance, the margin, is 2 divided by the norm of the weight vector, so minimising the norm of the weight vector maximises the margin ^[1]. The nearest points, the ones that touch the edge of the margin, are called support vectors ^[1]. Only these points enter the decision function, which is what makes the method memory efficient ^[2].

A small example makes the idea concrete. Imagine two classes of points on a plane, with many straight lines that separate them cleanly. The SVM does not take just any of those lines; it takes the one whose surrounding empty band is as wide as possible. Nudging that line slightly in either direction then leaves the classification of nearby points unchanged, which is part of why the model copes with noise in the training data.

Kernels

Real data is rarely separable by a straight line. A kernel function computes the inner product of mapped feature vectors implicitly, so data can be separated linearly in a higher-dimensional space ^[1]. In practice the algorithm works with similarities between pairs of points rather than with explicit coordinates in the larger space. Common kernels are linear, polynomial, Gaussian radial basis function and sigmoid ^[1], and different kernel functions can be specified for the decision function ^[2].

Where it came from

Vladimir Vapnik and Alexey Chervonenkis introduced the original linear support vector machine in 1964 ^[1]. The step from linear to non-linear came in 1992, when Bernhard Boser, Isabelle Guyon and Vladimir Vapnik introduced the kernel trick for non-linear classification ^[1]. Data is often not cleanly separable at all, and the soft margin, proposed by Corinna Cortes and Vapnik in 1993 and published in 1995, let the model accept some misclassification instead of demanding a perfect separation ^[1].

Why it mattered

SVMs dominated before deep learning ^[1]. Part of the reason is that they could be analysed theoretically through VC theory ^[1]. They were also flexible: the same framework was applied to text, image and biological data ^[1]. They were robust to noisy data and had low generalisation error ^[1]. The margin also gives an account of why a wide gap between classes should help on unseen data, which is the argument VC theory formalises.

Limitations

The limitations are practical. SVMs need fully labelled data, and they support only binary classification directly, so multi-class problems are split into several binary ones ^[1]. Kernel, gamma and penalty parameters are hard to interpret and are usually chosen by grid search with cross-validation ^[1], which turns training into a search over configurations rather than a single fit. Computing the kernel matrix is expensive in time and memory on large sparse data sets ^[1]. The scikit-learn documentation adds a warning of its own: when the number of features greatly exceeds the number of samples, avoiding overfitting in kernel choice and in the regularization term is crucial ^[2].