Machine Learning
Topic 19 · Supervised algorithms · ⏱ about 4 h

Support Vector Machines

Find the boundary with the widest possible margin.

Show:
In this topic
Beginner

Maximum margin

Imagine two groups of points that can be separated by a straight line. There are usually infinitely many lines that do the job: some pass very close to one group, others very close to the other. Which one should we choose? A support vector machine (SVM) gives a clear answer: choose the line that stays as far as possible from both groups.

Picture the separating line as the middle of a road, with the two groups of points on either side. The SVM makes this road, called the margin, as wide as possible without any points on it. The reasoning is that a wide margin leaves room for error: new points that land a little away from their group are still likely to end up on the correct side. A line squeezed tight against one group would misclassify new points from that group at the slightest variation.

The training points that lie exactly on the edges of the road are called the support vectors, because they alone "hold up" the boundary. A remarkable consequence is that every other training point is irrelevant to the final answer: you could move or delete any point that is safely away from the margin, and the boundary would not change at all.

margin = 2/‖w‖ringed points = support vectors

Mathematically, the boundary is the set of points where w⊤x+b=0w^\top x + b = 0, and maximising the margin turns out to be the same as making the weight vector ww as short as possible (the Intermediate section derives this). Real data are rarely perfectly separable, though, so practical SVMs use a soft margin, which allows some points to sit inside the road or even on the wrong side, at a cost. The training problem becomes

min⁡w,b,ξ 12∥w∥2+C∑iξisubject toyi(w⊤xi+b)≥1−ξi,  ξi≥0. \min_{w,b,\xi}\ \tfrac12\lVert w\rVert^2 + C\sum_i\xi_i \quad\text{subject to}\quad y_i(w^\top x_i + b) \ge 1 - \xi_i,\ \ \xi_i\ge 0.

Each ξi\xi_i (the Greek letter xi), called a slack variable, measures how far point ii intrudes into the margin, and CC sets the price of each unit of intrusion. A large CC makes violations very expensive, so the SVM fits the training data tightly with a narrow margin, which risks overfitting. A small CC makes violations cheap, so the SVM accepts more of them in exchange for a wider margin, which is stronger regularisation. The penalty in this formulation is called the hinge loss.

Beginner

Watch it: Support vector machines: the widest street, and the kernel trick

A short narrated animation. Press ▶ Play, or step through it with ⏮ ⏭. Tick 🔊 narrate to hear each step.

Interactive: this part runs in your browser.

Try it

Try it: the soft-margin SVM and the C parameter

The solid line is the decision boundary and the dashed lines are the edges of the margin. Ringed points are support vectors. Slide C and increase the overlap between the classes.

Interactive: this part runs in your browser.

Beginner

The kernel trick

A straight boundary can't separate every dataset. Consider points of one class forming a ring around points of the other class: no straight line can separate the inside from the outside. The SVM's solution to this problem is one of the most elegant ideas in machine learning.

original 2-D: no straight line worksadd z = x₁² + x₂²lifted to 3-D: a flat plane separates
The kernel idea: map data into a richer space where a linear boundary works, without ever computing that space explicitly.

The first step is to notice that data which aren't separable in their original space may become separable if we add new features. For the ring, add the feature x12+x22x_1^2 + x_2^2, the squared distance from the centre. In the new three-dimensional space, the inner points have small values of this feature and the outer points have large values, so a flat plane at the right height separates them perfectly. Mapping the data into a richer space, with some transformation ϕ(x)\phi(x), can turn a curved problem into a linear one.

The difficulty is that a rich enough space might have a huge number of dimensions, perhaps even infinitely many, so computing ϕ(x)\phi(x) directly would be impossibly expensive. This is where the kernel trick comes in. When the SVM's optimisation problem is written in its "dual" form (see the Advanced section), the data appear only through dot products between pairs of points, xi⊤xjx_i^\top x_j. So we never need the transformed points themselves, only the dot products between them, ϕ(xi)⊤ϕ(xj)\phi(x_i)^\top\phi(x_j). A kernel is a function K(a,b)K(a, b) that computes this dot product directly from the original points, cheaply, without ever constructing ϕ\phi.

KernelFormula K(a,b)K(a,b)When to use it
Lineara⊤ba^\top bvery high-dimensional data such as text, where a linear boundary is usually enough
Polynomial(a⊤b+c)d(a^\top b + c)^dwhen interactions between features matter
RBF (Gaussian)exp⁡(−γ∥a−b∥2)\exp(-\gamma\lVert a - b\rVert^2)the default for non-linear problems

The RBF kernel measures similarity by distance: it is close to 1 for nearby points and close to 0 for distant ones. Its parameter γ\gamma sets how quickly similarity falls off with distance. A large γ\gamma means each training point influences only its immediate neighbourhood, producing a very wiggly boundary that can overfit; a small γ\gamma produces a smoother boundary. In practice, CC and γ\gamma are tuned together with cross-validation.

SVMs work particularly well on small and medium-sized datasets with many features, such as text classification or bioinformatics, where they were state of the art for many years. They have three practical limitations. Training time grows roughly with the square or cube of the number of examples, so they become slow beyond tens or hundreds of thousands of examples. They require feature scaling, because the kernels depend on distances or dot products. And they produce scores rather than probabilities; probabilities can be obtained by calibrating the scores afterwards, at extra cost.

Interactive: this part runs in your browser.

Interactive. Lift one-dimensional data into two dimensions and a straight line separates it.
Intermediate · Maths

Deriving the margin and the hinge loss

📐 Maths you'll need: m-vectors · m-optim
💡 The idea in plain words

Many lines separate the classes; the SVM picks the one with the widest safety margin, because a wide street tolerates noise in new data. A short calculation shows the street width is 2/‖w‖, so "widest street" becomes "smallest weights", and allowing a few points into the street gives the hinge loss.

🔤 Symbols in this section
w, bw,\ bnormal vector and offset of the boundary
yi∈{−1,+1}y_i\in\{-1,+1\}labels
∥w∥\lVert w\rVertlength of w
ξi\xi_islack: how far point i violates the margin
CCcost of violations (inverse regularisation)
max⁡(0,1−yf)\max(0, 1 - yf)hinge loss

This section derives the SVM from geometry, showing why "maximise the margin" becomes "minimise ∥w∥\lVert w\rVert", and how the soft-margin version turns into the hinge loss.

Step 1: distance to the boundary. The boundary is the set of points where w⊤x+b=0w^\top x + b = 0. The vector ww is perpendicular to this boundary, and a standard result from geometry gives the distance from any point xix_i to it as ∣w⊤xi+b∣∥w∥\dfrac{|w^\top x_i + b|}{\lVert w\rVert}.
Step 2: fix the scale. Multiplying both ww and bb by the same positive number describes exactly the same boundary, so we are free to choose a convenient scale. We choose it so that the points closest to the boundary satisfy ∣w⊤xi+b∣=1|w^\top x_i + b| = 1. With labels yi∈{−1,+1}y_i\in\{-1, +1\}, the requirement that every point is on the correct side and at least this far away is yi(w⊤xi+b)≥1y_i(w^\top x_i + b) \ge 1.
Step 3: compute the margin. By Step 1, the closest points are at distance 1/∥w∥1/\lVert w\rVert on each side, so the full width of the road is 2/∥w∥2/\lVert w\rVert.
Step 4: turn it into a minimisation. Making 2/∥w∥2/\lVert w\rVert as large as possible is the same as making ∥w∥\lVert w\rVert as small as possible, and for mathematical convenience we minimise 12∥w∥2\tfrac12\lVert w\rVert^2, which has the same minimiser and a simpler derivative.

This gives the hard-margin SVM:

min⁡w,b 12∥w∥2subject toyi(w⊤xi+b)≥1  for every i. \min_{w,b}\ \tfrac12\lVert w\rVert^2 \quad\text{subject to}\quad y_i(w^\top x_i + b) \ge 1\ \text{ for every } i.

To allow violations, the soft-margin SVM introduces a slack ξi≥0\xi_i \ge 0 for each point, relaxes each constraint to yi(w⊤xi+b)≥1−ξiy_i(w^\top x_i + b) \ge 1 - \xi_i, and charges CC per unit of slack:

min⁡w,b,ξ 12∥w∥2+C∑iξisubject toyi(w⊤xi+b)≥1−ξi,  ξi≥0. \min_{w,b,\xi}\ \tfrac12\lVert w\rVert^2 + C\sum_i\xi_i \quad\text{subject to}\quad y_i(w^\top x_i + b) \ge 1 - \xi_i,\ \ \xi_i\ge 0.

Now consider what the best slack is for each point. If a point already satisfies yif(xi)≥1y_i f(x_i) \ge 1, where f(x)=w⊤x+bf(x) = w^\top x + b, it needs no slack, so ξi=0\xi_i = 0. Otherwise, the smallest slack that satisfies the constraint is ξi=1−yif(xi)\xi_i = 1 - y_i f(x_i). Both cases are captured by ξi=max⁡(0, 1−yif(xi))\xi_i = \max\big(0,\ 1 - y_i f(x_i)\big). Substituting this back removes the constraints entirely:

min⁡w,b ∑imax⁡(0, 1−yi(w⊤xi+b))⏟hinge loss+12C∥w∥2. \min_{w,b}\ \underbrace{\sum_i \max\big(0,\ 1 - y_i(w^\top x_i + b)\big)}_{\text{hinge loss}} + \frac{1}{2C}\lVert w\rVert^2 .

(We divided the whole objective by CC, which doesn't change the answer.) So the soft-margin SVM is simply regularised empirical risk minimisation with the hinge loss, the same structure as ridge or regularised logistic regression, just with a different loss. The hinge loss is exactly zero for points that are correctly classified with room to spare (yif(xi)≥1y_i f(x_i) \ge 1) and grows linearly for points inside the margin or on the wrong side.

It is illuminating to compare it with logistic regression's loss, log⁡(1+e−yf(x))\log(1 + e^{-y f(x)}). That loss is a smooth curve that gets very close to zero for well-classified points but never quite reaches it, so every training point retains a small influence. The hinge loss reaches exactly zero, so well-classified points have no influence at all. This is precisely why the SVM's solution depends only on a few points, the support vectors, while logistic regression depends on all of them.

Key takeaway. Maximising the margin 2/‖w‖ = minimising ½‖w‖²; with slack this is exactly hinge loss + an L2 penalty.
Advanced

The dual problem, KKT conditions and kernels

📐 Maths you'll need: m-optim · m-vectors · m-eigen
💡 The idea in plain words

Rewriting the problem with Lagrange multipliers reveals two surprises. First, only the points on or inside the margin (the support vectors) affect the answer. Second, the data only ever appears as dot products between pairs of points, so you can swap in a kernel that computes dot products in a much richer feature space, without ever building that space.

🔤 Symbols in this section
αi\alpha_iLagrange multiplier for point i
SV\text{SV}set of support vectors (α > 0)
ϕ(x)\phi(x)feature map
K(a,b)=ϕ(a)⊤ϕ(b)K(a,b) = \phi(a)^\top\phi(b)kernel
γ\gammaRBF width parameter
ε\varepsilontube width in SVR

The SVM problem can be rewritten in an equivalent "dual" form using Lagrange multipliers (see the optimisation topic). The dual form reveals two important facts: which points actually matter, and why kernels can be used.

We attach a multiplier αi≥0\alpha_i \ge 0 to each margin constraint and form the Lagrangian. Setting its derivatives with respect to ww and bb to zero gives two conditions:

w=∑iαiyixiand∑iαiyi=0. w = \sum_i \alpha_i y_i x_i \qquad\text{and}\qquad \sum_i\alpha_i y_i = 0.

The first says that the optimal weight vector is a weighted combination of the training points. Substituting both conditions back into the Lagrangian eliminates ww and bb and leaves an optimisation problem in the α\alphas alone, the dual problem:

max⁡α ∑iαi−12∑i,jαiαjyiyj xi⊤xjsubject to0≤αi≤C,  ∑iαiyi=0. \max_{\alpha}\ \sum_i \alpha_i - \frac12\sum_{i,j}\alpha_i\alpha_j y_i y_j\, x_i^\top x_j \quad\text{subject to}\quad 0 \le \alpha_i \le C,\ \ \sum_i\alpha_i y_i = 0.

Which points matter. The Karush–Kuhn–Tucker (KKT) conditions, which characterise the solution, include complementary slackness: αi[yif(xi)−1+ξi]=0\alpha_i\big[y_i f(x_i) - 1 + \xi_i\big] = 0 for every point. In words, either a point's multiplier is zero, or its constraint holds with equality. A point safely outside the margin has a strictly satisfied constraint, so its αi\alpha_i must be zero, and it drops out of w=∑iαiyixiw = \sum_i\alpha_i y_i x_i completely. Only points on the margin (with 0<αi<C0 < \alpha_i < C) or inside it or misclassified (with αi=C\alpha_i = C) have non-zero multipliers. These are the support vectors, and the classifier depends on them alone:

f(x)=∑i∈SVαiyi xi⊤x+b. f(x) = \sum_{i\in SV}\alpha_i y_i\, x_i^\top x + b.

Why kernels work. Look closely at the dual problem and at this prediction formula: the training data appear only through dot products xi⊤xjx_i^\top x_j and xi⊤xx_i^\top x. If we first map every point through a feature transformation ϕ\phi, every dot product becomes ϕ(xi)⊤ϕ(xj)\phi(x_i)^\top\phi(x_j), and we can replace it by a kernel K(xi,xj)K(x_i, x_j) that computes this value directly. Mercer's theorem tells us which functions are valid kernels: any symmetric function for which every kernel matrix [K(xi,xj)][K(x_i, x_j)] is positive semi-definite corresponds to a dot product in some feature space.

A small example makes this concrete. In two dimensions, take K(a,b)=(a⊤b)2K(a, b) = (a^\top b)^2. Expanding, (a1b1+a2b2)2=a12b12+2a1a2b1b2+a22b22(a_1b_1 + a_2b_2)^2 = a_1^2b_1^2 + 2a_1a_2b_1b_2 + a_2^2b_2^2, which is exactly the dot product of ϕ(a)=(a12, 2 a1a2, a22)\phi(a) = (a_1^2,\ \sqrt2\,a_1a_2,\ a_2^2) with ϕ(b)\phi(b). So this kernel computes a dot product in a three-dimensional space of squared and cross-product features, while only ever doing arithmetic on the original two coordinates. The RBF kernel e−γ∥a−b∥2e^{-\gamma\lVert a-b\rVert^2} goes much further: its feature space is infinite-dimensional, yet the kernel is a single cheap formula.

Cost and variants. Solving the dual (usually with an algorithm called SMO) takes roughly between n2n^2 and n3n^3 operations, and storing the kernel matrix needs memory proportional to n2n^2. For large datasets, practitioners therefore use linear SVMs trained directly on the hinge loss (scikit-learn's LinearSVC, or SGD), or approximate the kernel with a finite set of random features (random Fourier features) or a sample of the data (the Nyström method). The same ideas also give support vector regression, which uses an "ε\varepsilon-insensitive" loss, max⁡(0,∣y−f(x)∣−ε)\max(0, |y - f(x)| - \varepsilon), that ignores errors smaller than ε\varepsilon and so also depends on only a subset of the training points.

Key takeaway. The dual depends on data only via dot products: support vectors have α > 0, and kernels give non-linear boundaries for the cost of an n × n kernel matrix.
Code

Code: linear SVM by subgradient descent, and kernel SVMs in scikit-learn

The scratch version minimises the hinge-loss form directly (the Pegasos algorithm).

Python · NumPy from scratch (Pegasos)
import numpy as np
from sklearn.datasets import make_blobs

X, y = make_blobs(n_samples=300, centers=2, cluster_std=1.5, random_state=3)
y = np.where(y == 0, -1, 1)                       # labels must be -1 / +1
X = (X - X.mean(0)) / X.std(0)

def pegasos(X, y, lam=0.01, epochs=50, seed=0):
    rng = np.random.default_rng(seed)
    n, d = X.shape
    w, b, t = np.zeros(d), 0.0, 0
    for _ in range(epochs):
        for i in rng.permutation(n):
            t += 1
            eta = 1 / (lam * t)                   # decaying step size
            if y[i] * (X[i] @ w + b) < 1:         # inside margin: hinge is active
                w = (1 - eta * lam) * w + eta * y[i] * X[i]
                b += eta * y[i]
            else:                                 # only the regulariser acts
                w = (1 - eta * lam) * w
    return w, b

w, b = pegasos(X, y)
margins = y * (X @ w + b)
print("accuracy:", np.mean(margins > 0), " margin width:", round(2 / np.linalg.norm(w), 3))
print("points on/inside margin (support-vector candidates):", np.sum(margins <= 1 + 1e-6))
Open in playground ↗
Python · scikit-learn (RBF kernel, tune C and γ)
from sklearn.datasets import make_circles
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC
from sklearn.model_selection import GridSearchCV

X, y = make_circles(n_samples=400, factor=0.4, noise=0.1, random_state=0)
pipe = make_pipeline(StandardScaler(), SVC(kernel="rbf"))
grid = GridSearchCV(pipe, {"svc__C": np.logspace(-2, 3, 6),
                           "svc__gamma": np.logspace(-2, 2, 5)}, cv=5).fit(X, y)
best = grid.best_estimator_.named_steps["svc"]
print(grid.best_params_, "cv acc:", round(grid.best_score_, 3))
print("support vectors per class:", best.n_support_)
# A linear kernel fails on circles; the RBF kernel separates them easily.
print("linear kernel cv acc:", round(GridSearchCV(make_pipeline(StandardScaler(), SVC(kernel="linear")),
      {"svc__C": [0.1, 1, 10]}, cv=5).fit(X, y).best_score_, 3))
Open in playground ↗
Before it runs: import numpy as np.
Check yourself

Quiz

1. Support vectors are…

2. A very large C in an SVM gives…

3. The kernel trick lets SVMs…

4. The soft-margin SVM is equivalent to minimising…

5. In the dual solution, points strictly outside the margin have…

6. Kernels can replace xᵢᵀxⱼ because the dual depends on the data only through…

Go deeper

📚 Further reading

Trusted, mostly free sources: official documentation, well-known textbooks and courses. When you want to confirm or go deeper on anything here, start with these.

Ready