Support Vector Machines

The widest street

Before deep learning took over, the support vector machine was the method to beat. In the late 1990s and 2000s SVMs were the go-to choice for text categorisation, handwritten digits, gene-expression data and protein classification, and kernel SVMs with built-in invariances held the lowest reported error on the MNIST digits for a time. They are still a strong default when you have hundreds or a few thousand labelled examples, and the ideas behind them, margins and kernels, run all through modern machine learning.

What is it?

A support vector machine is a classifier that separates two classes with the widest possible gap. Picture the data as two groups of points. Many straight lines separate them. An SVM picks the one that sits in the middle of the widest empty street you can drive between the groups, and it measures that street using only the points on its kerbs.

How does it work?

A linear classifier scores a point with f(x) = w·x + b and predicts the class from the sign. The line f(x) = 0 is the boundary. The SVM adds two more lines, f(x) = +1 and f(x) = −1, and insists that every training point lies on the correct side of its own line. The gap between them is the margin, and its width turns out to be 2 / ‖w‖. So making the street wide means making w small.

Why does it matter?

A boundary that hugs one class will misclassify the next slightly unusual example from that class. A boundary with room to spare on both sides is more robust to noise in new data. Vapnik’s statistical learning theory makes this precise: a larger margin means a simpler classifier, with tighter guarantees on test error, whatever the number of dimensions.

Key takeaways

• An SVM is a linear classifier that separates two classes with the widest possible margin.
• The margin is the gap between the lines f(x) = +1 and f(x) = −1, and its width is 2 / ‖w‖.
• A wide margin leaves room for noise in new data, which is why SVMs generalise well from few examples.

Support vectors

Write the widest-street idea as an optimisation problem and something surprising falls out: the answer depends on only a handful of points.

What is it?

Support vectors are the training points that sit exactly on the edge of the margin (or, later, inside it). They are the points that hold the street in place, like tent poles. Every other point could be deleted and the boundary would not move.

How does it work?

With labels y = +1 or −1, “every point on the right side of its line” is the constraint y·(w·x + b) ≥ 1. Maximising the margin 2 / ‖w‖ is the same as minimising ‖w‖², so the hard-margin SVM is:

The hard-margin SVM. A convex quadratic problem: it has one global minimum and no bad local minima.

Solving it with Lagrange multipliers gives one multiplier αᵢ ≥ 0 per training point, and the solution is a weighted sum of training points: w = Σ αᵢ yᵢ xᵢ. At the optimum, αᵢ is zero for every point safely beyond its kerb. Only points touching the margin get αᵢ > 0. Those are the support vectors.

The demo solves this problem live with Platt’s sequential minimal optimisation (SMO), the algorithm behind LIBSVM and scikit-learn’s SVC: it repeatedly picks two multipliers that break the optimality conditions and solves for them exactly, until none do.

Why does it matter?

Because only support vectors count, an SVM is a compact summary of its training set, and predictions need only those points. It also tells you which examples are hard: the support vectors are exactly the borderline cases.

This demo uses a very large C (1,000), which behaves like a hard margin. If you drag a point across to the other side, no street can be empty any more, and the next section explains what the SVM does then.

Key takeaways

• The hard-margin SVM minimises ½‖w‖² subject to every point being on the right side of its margin line.
• The solution is w = Σ αᵢ yᵢ xᵢ, and αᵢ is non-zero only for support vectors.
• Moving or deleting a non-support vector changes nothing; moving a support vector moves the boundary.

Soft margins and C

Real data overlaps. One mislabelled email or unusual patient makes a perfectly empty street impossible, and even when one exists it may be a silly, narrow street that bends to accommodate a single outlier.

What is it?

A soft-margin SVM lets some points into the street, or even onto the wrong side, at a price. The penalty C sets that price. Cortes and Vapnik introduced it in 1995, and it is what everyone means by an SVM today.

How does it work?

Each point gets a hinge loss: zero if it is safely outside the street (y·f(x) ≥ 1), and growing in a straight line the further it intrudes. A point exactly on the boundary pays 1; a point on the wrong side pays more than 1.

The soft-margin SVM. The first term wants a wide street; the second wants few, small intrusions. C decides the balance.

Large C makes intrusions expensive: the SVM narrows the street to keep points out, approaching the hard margin. Small C makes them cheap: the street widens, more points fall inside it, and every point inside the street becomes a support vector. In the dual problem C is simply an upper limit on each αᵢ.

Why does it matter?

C is the SVM’s regularisation knob, the same bias-variance trade-off you meet everywhere in machine learning. Too large and the boundary chases noise; too small and it ignores real structure. Seen this way, an SVM is “hinge loss plus a ridge penalty”, a close cousin of regularised logistic regression.

Key takeaways

• The soft-margin SVM minimises ½‖w‖² plus C times the total hinge loss max(0, 1 − y·f(x)).
• Large C means a narrow, strict street; small C means a wide, tolerant one with more support vectors.
• C is a regularisation strength, chosen by validation, never by training accuracy.

The kernel trick

Some data cannot be split by any straight line: a disc of one class surrounded by a ring of the other. The kernel trick lets the same linear machinery draw curved boundaries, without ever computing the curved features.

What is it?

A kernel is a function K(x, z) that equals a dot product of x and z after some feature transformation φ: K(x, z) = φ(x)·φ(z). Swap every dot product in the SVM for a kernel and you get a maximum-margin linear classifier in φ’s feature space, which can be a curved classifier back in the original space.

How does it work?

Start with the honest version, an explicit transformation. These points on a line cannot be split by any single threshold. Add x² as a second feature and they can:

The catch is cost: all degree-2 products of 1,000 features is half a million features. The trick is that the SVM never needs φ(x) itself, only dot products between pairs of training points, because the solution is w = Σ αᵢ yᵢ φ(xᵢ) and so f(x) = Σ αᵢ yᵢ K(xᵢ, x) + b. A kernel computes those dot products directly and cheaply:

Two common kernels. The polynomial kernel equals a dot product over all products of up to d features. The RBF (Gaussian) kernel corresponds to an infinite-dimensional feature space.

The RBF kernel has a more useful intuition than “infinite dimensions”. K(x, z) is a similarity: 1 when x and z coincide, falling towards 0 as they move apart. So an RBF SVM predicts by asking how similar a new point is to each support vector, weighted by αᵢ and the vector’s class. γ sets how fast similarity fades: small γ means every support vector influences a wide area and the boundary is smooth; large γ means tiny bumps around individual points.

Why does it matter?

Kernels let one well-understood convex optimiser handle curved boundaries, strings, graphs and anything else for which you can define a valid similarity. They are the reason SVMs worked so well on text and biology. The same idea, a model built from similarities to stored examples, reappears in Gaussian processes and, loosely, in attention.

Key takeaways

• A kernel K(x, z) is a dot product in a transformed feature space, computed without building the features.
• Replacing dot products with a kernel turns the linear SVM into a curved classifier: f(x) = Σ αᵢ yᵢ K(xᵢ, x) + b.
• The RBF kernel is a similarity; γ sets its reach, with large γ and C risking overfitting.

SVMs in practice

SVMs are easy to run and easy to run badly. A short checklist covers most of the difference.

How do you use one well?

1. Scale the features. Margins and RBF distances are measured in raw units, so a feature in thousands swamps one in single digits.
2. Start with RBF (or linear when you have very many features, as in text), and choose C and γ by cross-validated grid search on a log scale, for example C and γ in 2⁻⁵ … 2¹⁵, as the LIBSVM authors recommend.
3. More than two classes: train one SVM per pair of classes (one-vs-one) or one per class against the rest, and vote.
4. Probabilities: f(x) is a signed distance, not a probability. Libraries fit an extra sigmoid on top (Platt scaling) when you ask for probabilities.

Key takeaways

• Always scale features, then tune C and γ together by cross-validated grid search on a log scale.
• SVM scores are distances, not probabilities; calibrate them if you need probabilities.
• Kernel SVMs suit small and medium datasets; at very large scale, linear SVMs, boosted trees or neural networks take over.

Check your understanding

Six situations where the ideas in this lesson decide what to do next.

You train a linear SVM on 10,000 labelled emails and it ends up with 140 support vectors. A colleague deletes 5,000 emails that are not support vectors and retrains. What happens to the boundary?

Next, meet a classifier built on probability instead of geometry in Naive Bayes, or compare with trees in Random Forests and Boosting.

References

The papers and guides behind this lesson.

Sources

References

1. [1]

   Training Invariant Support Vector Machines(opens in a new tab)

   Dennis DeCoste & Bernhard Schölkopf, 2002

   Machine Learning 46, 161–190. Kernel SVMs with built-in invariances reached the lowest reported error on the MNIST digits at the time.

2. [2]

   Support-Vector Networks(opens in a new tab)

   Corinna Cortes & Vladimir Vapnik, 1995

   Machine Learning 20(3), 273–297. Introduced the soft-margin SVM with slack variables and the penalty C.

3. [3]

   A Training Algorithm for Optimal Margin Classifiers(opens in a new tab)

   Bernhard Boser, Isabelle Guyon & Vladimir Vapnik, 1992

   COLT 1992. The maximum-margin classifier combined with kernels, so the boundary can be non-linear.

4. [4]

   Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines(opens in a new tab)

   John C. Platt, 1998

   Microsoft Research MSR-TR-98-14. The SMO algorithm used by the demos on this page: optimise two multipliers at a time, in closed form.

5. [5]

   The Elements of Statistical Learning (2nd edition), chapter 12(opens in a new tab)

   Trevor Hastie, Robert Tibshirani & Jerome Friedman, 2009

   Springer. Support vector machines as hinge loss plus a ridge penalty, and their relation to logistic regression. Free PDF.

6. [6]

   A Practical Guide to Support Vector Classification(opens in a new tab)

   Chih-Wei Hsu, Chih-Chung Chang & Chih-Jen Lin, 2003

   From the authors of LIBSVM: scale the features, start with the RBF kernel, pick C and γ by cross-validated grid search.

7. [7]

   Support Vector Machines (user guide)(opens in a new tab)

   scikit-learn developers, 2024

   Practical notes on kernels, C and γ, scaling with dataset size, and probability estimates via Platt scaling.