Support Vector Machines

A support vector machine (SVM) is a supervised learning algorithm that separates two classes by finding the maximum-margin hyperplane: the decision boundary that sits as far as possible from the closest examples of each class. That distance, the margin, is the heart of the method; the wider it is, the more robust the classification of new data tends to be.

Two primary publications place the modern formulation in the 1990s: Boser, Guyon and Vapnik presented a training algorithm for optimal-margin classifiers in 1992, and Cortes and Vapnik published “Support-Vector Networks” in 1995. SVMs are used for classification and also have a regression formulation.

The maximum-margin hyperplane and support vectors

Among the infinitely many boundaries that could separate two classes, an SVM picks just one: the boundary that maximizes the margin. When that optimization problem is solved, most of the training examples turn out to be irrelevant. The boundary is determined entirely by a handful of points sitting right at the edge of the margin: the support vectors. Move any distant point and the solution stays put; move a support vector and the boundary shifts. This economy —deciding with the borderline cases rather than the bulk of the data— is what gives the method its name and its elegance.

Soft margin and the C parameter

Real data rarely separates without errors. In 1995, Corinna Cortes and Vapnik published “Support-Vector Networks” in the journal Machine Learning, introducing the soft margin: the boundary may tolerate some examples falling on the wrong side or inside the margin, at the cost of a penalty. The trade-off is governed by the regularization parameter C. A high C punishes every error harshly and narrows the margin, risking overfitting; a low C tolerates more errors and widens the margin, favoring generalization. Tuning C is one of the most important practical decisions when training an SVM.

The kernel trick and non-linearity

Many problems cannot be split by a straight line or a flat plane. The solution, proposed by Bernhard Boser, Isabelle Guyon and Vapnik in 1992, is the kernel trick: implicitly project the data into a higher-dimensional space where a separating hyperplane does exist, without ever computing that projection. It suffices to replace the dot products with a kernel function. The most common kernels are the linear, the polynomial and the RBF or Gaussian kernel; the choice of kernel and its parameters sets the shape of the boundary in the original space, which can be sharply curved even though it remains a flat plane in the projected space.