SVM (Support Vector Machine), explained in 5 lines

Module 01 · Machine Learning · 55 concepts

In depth / 15 lines

SVM (Support Vector Machine), in more detail

Picture two groups of points and a line drawn between them.

Many lines would separate them, and an SVM looks for the roomiest one.

It wants the widest empty corridor between the two groups.

Only the points at the edge of that corridor affect the answer.

Those are the support vectors, and the rest could be deleted with no effect.

That makes it steady, because distant points cannot drag the boundary around.

Real data is rarely separable, so a setting called C allows some mistakes.

A small C accepts more errors in exchange for a wider corridor.

A large C insists on getting training points right and overfits more easily.

When no straight line works, the kernel trick reshapes the space instead.

It behaves as if the data were lifted into more dimensions, without paying for them.

The RBF kernel is the usual default and draws smooth curved boundaries.

Features must be scaled first, since the corridor is measured by distance.

It slows down badly once you have hundreds of thousands of examples.

It gives you a decision rather than a probability, unless you add another step.

Want the full technical article? Wikipedia ↗

Deep dive

What is underneath SVM (Support Vector Machine)

The margin it maximises

Many lines separate two classes. An SVM picks the one that stands furthest from both.

\text{margin} = \frac{2}{\|\mathbf{w}\|}

$\mathbf{w}$ : the weight vector, perpendicular to the boundary.
$\|\mathbf{w}\|$ : its length.

The boundary is $\mathbf{w}^\top \mathbf{x} + b = 0$ , and the two edges of the margin are where that expression equals $+1$ and $-1$ .

Maximising $2 / \|\mathbf{w}\|$ is the same as minimising $\|\mathbf{w}\|^2$ , which is where the optimisation problem comes from.

The problem, written out

\min_{\mathbf{w}, b} \; \frac{1}{2} \|\mathbf{w}\|^2 \quad \text{subject to} \quad y_i (\mathbf{w}^\top \mathbf{x}_i + b) \geq 1

$y_i$ : the label, written as $+1$ or $-1$ rather than 1 or 0.

That constraint says every point sits on the correct side of its own margin edge, which is only possible if the classes are perfectly separable.

\min_{\mathbf{w}, b} \; \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^{n} \xi_i

Real data is not, so a slack variable $\xi_i$ lets a point violate its margin and $C$ sets the price of doing so.

Large $C$ buys a narrow margin that misclassifies little. Small $C$ buys a wide margin that tolerates errors, which usually generalises better.

Hinge loss is the same thing unconstrained

\mathcal{L} = \frac{1}{n} \sum_{i=1}^{n} \max\big(0, \; 1 - y_i f(\mathbf{x}_i)\big) + \lambda \|\mathbf{w}\|^2

A point that is correct and past the margin costs exactly zero, which is what makes the solution depend on so few points.

Those points, the ones sitting on or inside the margin, are the support vectors. Move any other point and the boundary does not shift.

The kernel trick

f(\mathbf{x}) = \sum_{i=1}^{n} \alpha_i y_i \, k(\mathbf{x}_i, \mathbf{x}) + b

Solved in its dual form the problem never needs the coordinates of a point, only inner products between pairs of points.

k(\mathbf{x}, \mathbf{z}) = \exp\left( -\gamma \|\mathbf{x} - \mathbf{z}\|^2 \right)

So an inner product in a higher dimensional space can be substituted directly, and the RBF kernel above corresponds to a space with infinitely many dimensions.

The features are never computed. Only the kernel values are, which is why a curved boundary costs no more than a straight one.

$\gamma$ sets how far one training point's influence reaches: large $\gamma$ makes each point a narrow island and overfits.

One fit, in order

Choose a kernel and the values of $C$ and $\gamma$ .
Solve the dual problem for the coefficients $\alpha_i$ .
Keep the points whose $\alpha_i$ is greater than zero, which are the support vectors.
Predict the sign of $f(\mathbf{x})$ for a new point.

What it costs

Training is between $O(n^2)$ and $O(n^3)$ in the number of samples, so an SVM is the wrong tool above a few hundred thousand rows.

Distances sit inside the kernel, so unscaled features break it the same way they break k-NN.

It outputs a distance from a boundary and not a probability, so anything calibrated has to be fitted afterwards.

Test yourself

One question on this card. Every option explains itself once you pick, right or wrong.

Question 1

What are the support vectors?

Machine Learning

55 concepts in this module, then a graded test with every answer explained.

Study this module →