Skip to content
LearnMLByDoing
Free

2.5 Support vector machines and the kernel trick

34 minProintermediateHOMLISLRESL

A support vector machine draws the widest possible street between two classes, lets C decide how many points may stand in it, and uses a kernel to draw that street in a feature space it never has to build.

01The widest street

A linear classifier scores a point with f(x)=w⊤x+bf(x)=w^\top x+b and predicts its sign. The set f(x)=0f(x)=0 is a line in 2D and a hyperplane in dd dimensions; ww is its normal and bb shifts it. Many lines separate the cyan (y=+1y=+1) and amber (y=−1y=-1) blobs in the viewport. The support vector machine picks the one that stays as far as possible from the closest points of both classes.

f(x)=w⊤x+b,dist⁡(x, {f=0})=∣f(x)∣∥w∥\tok{decision}{f(x)}=\tok{weights}{w}^{\top}x+\tok{bias}{b},\qquad \operatorname{dist}\big(x,\ \{f=0\}\big)=\frac{|f(x)|}{\|\tok{weights}{w}\|}
Distance from a point to the boundary: its score divided by the length of the normal.

(w,b)(w,b) and (cw,cb)(cw,cb) describe the same line for any c>0c>0, so the scale is free: w=(2, 4), b=−2w=(2,\ 4),\ b=-2 draws exactly the same line as w=(1, 2), b=−1w=(1,\ 2),\ b=-1, with every score doubled. Fix it by asking yif(xi)≥1y_i f(x_i)\ge1 for every training point, with equality for the closest ones. Those points then sit at distance 1/∥w∥1/\|w\| on either side, and the street between the lines f=−1f=-1 and f=+1f=+1 is 2/∥w∥\tok{margin}{2/\|w\|} wide.

From the widest street to a quadratic program1/4
  1. 1
    max⁡w,b min⁡i yi (w⊤xi+b)∥w∥\max_{w,b}\ \min_i\ \frac{y_i\,(w^{\top}x_i+b)}{\|w\|}

    Maximise the distance of the closest point, signed so that correct predictions count as positive.

The viewport is at C=100C=100 (the next step introduces CC), which here gives exactly the hard-margin solution: w=(1.99, 4.87)w=(1.99,\ 4.87), ∥w∥=5.26\|w\|=5.26, 2/∥w∥=0.3802/\|w\|=0.380. Three points touch the emerald band, ringed in emerald. One of them is the cyan outlier at (−0.55, 0.35)(-0.55,\ 0.35), deep in amber territory: it turns the normal ww to 68°68° (it is 44°44° once CC is lowered to 1 in step 3) and squeezes the street. Each cycle replays the solver on the floor, then lifts every point to a height that grows with its score f(x)f(x). For the linear and RBF kernels the height is this score (squashed by a tanh so it fits the box), not a new feature; only the polynomial kernel in step 4 lifts the points into real feature-space coordinates. The score surface crosses the floor along the boundary, and the street is where it passes between the faint planes at f=±1f=\pm1: the larger ∥w∥\|w\|, the steeper the surface and the narrower the street.

Loading figure
Twelve of the lab's blobs plus the cyan outlier, refitted with the same SMO solver on every drag. At C=100C=100 only two points are ringed: the outlier and the amber point closest to it, and the street is 0.8290.829 wide. Remove the outlier (switch to remove, click it) and the street nearly doubles to 1.5971.597, held by three support vectors.

Lower the penalty to C=1C=1 in the 3D scene and hold it on the floor.

Hands-On Machine Learning, Aurélien Géron, Ch. 5, Linear SVM classification

An Introduction to Statistical Learning, James, Witten, Hastie & Tibshirani, Sec. 9.1, Maximal margin classifier

02Soft margin: slack, hinge loss and C

Real classes overlap, and even separable data has outliers. The hard margin then has no solution at all, or, as in step 1, lets one point dictate a narrow street. The soft margin gives each point a slack ξi≥0\xi_i\ge0, how far it sits on the wrong side of its own margin line, and charges CC per unit of slack:

min⁡w,b,ξ 12∥w∥2+C∑iξis.t.yi (w⊤xi+b)≥1−ξi,  ξi≥0\min_{w,b,\xi}\ \tfrac12\|\tok{weights}{w}\|^2+\tok{penalty}{C}\sum_i\tok{slack}{\xi_i}\quad\text{s.t.}\quad y_i\,(w^{\top}x_i+b)\ge1-\tok{slack}{\xi_i},\ \ \tok{slack}{\xi_i}\ge0
ξᵢ = 0 beyond the margin, 0 < ξᵢ < 1 inside the street, ξᵢ > 1 for a misclassified point.
From constraints to the hinge loss1/4
  1. 1
    ξi≥1−yif(xi),ξi≥0\xi_i\ge1-y_if(x_i),\qquad \xi_i\ge0

    Both constraints bound ξᵢ from below, and no other constraint involves it.

The hinge loss max⁡(0, 1−m)\tok{hinge}{\max(0,\,1-m)} of the margin m=y f(x)m=y\,f(x) is zero for points beyond their margin line, grows linearly inside the street, and keeps growing for misclassified points. The panel at the bottom right plots it, with every training point placed at its own mm.

The viewport is at C=0.1C=0.1. The street widens from 0.3800.380 to 2/∥w∥=1.7762/\|w\|=1.776; 18 points now stand inside it, ringed in rose, and one of them is on the wrong side. Training accuracy falls to 98.6%98.6\%, yet on 200 fresh points from the same blobs accuracy rises from 99.0%99.0\% for the hard margin to 100%100\%. Drag log⁡10C\log_{10}C: every step up buys training-set purity with margin.

Loading figure
The same 13 points at C=1C=1: the street is 1.6611.661 wide, three points sit on the margin (emerald) and two pay slack at αi=C\alpha_i=C (rose), ∑ξi=1.03\sum\xi_i=1.03. Slide CC up and the rose rings disappear as the street narrows to 0.8290.829; slide it to 0.10.1 and ten points are ringed rose. Drag a point into the street to watch it start paying slack.

An Introduction to Statistical Learning, James, Witten, Hastie & Tibshirani, Sec. 9.2, Support vector classifiers

The Elements of Statistical Learning, Hastie, Tibshirani & Friedman, Sec. 12.2, The support vector classifier

03The dual: only support vectors carry weight

Optional depth: this step uses Lagrange multipliers (lesson 1.4, Convexity, Lagrange multipliers and duality). The result in plain words comes first: the trained SVM puts a weight αi\alpha_i on every training point, and that weight is zero for every point safely outside the street. Only the points on the edge of the street or inside it get a weight, and ww is a weighted sum of those points. The derivation below shows why. Attach a multiplier αi≥0\alpha_i\ge0 to each margin constraint, form the Lagrangian, and minimise it over ww, bb and ξ\xi. Setting the derivatives to zero gives the facts the rest of the lesson rests on:

From the Lagrangian to the dual1/4
  1. 1
    L=12∥w∥2+C∑iξi−∑iαi[yi(w⊤xi+b)−1+ξi]−∑iμiξi\mathcal{L}=\tfrac12\|w\|^2+C\sum_i\xi_i-\sum_i\alpha_i\big[y_i(w^{\top}x_i+b)-1+\xi_i\big]-\sum_i\mu_i\xi_i

    One multiplier αᵢ ≥ 0 per margin constraint and one μᵢ ≥ 0 per constraint ξᵢ ≥ 0.

Every training point therefore falls into one of three groups. yif(xi)>1y_if(x_i)>1: beyond its margin line, αi=0\tok{alpha}{\alpha_i}=0, and the model does not depend on it. yif(xi)=1y_if(x_i)=1: on the margin, with 0≤αi≤C0\le\alpha_i\le C; conversely, 0<αi<C0<\alpha_i<C forces the point to sit exactly on the margin. yif(xi)<1y_if(x_i)<1: inside the street or misclassified, αi=C\alpha_i=\tok{penalty}{C} and ξi>0\tok{slack}{\xi_i}>0. The last two groups are the xSV\tok{support}{x_{\mathrm{SV}}}.

α (dual variables)[]74 values

One multiplier per training point. At C = 1 only 8 of the 74 entries are non-zero.

Q (dual Hessian)[,]5,476 values

Qᵢⱼ = yᵢyⱼ xᵢᵀxⱼ. Its size grows with n², not with the number of features.

At C=1C=1 the fit has 8 support vectors: two on the margin with αi=0.435\alpha_i=0.435 (emerald rings) and six with αi=C=1\alpha_i=C=1 inside the street (rose rings), among them both outliers, which are now misclassified. The other 66 points have αi=0\alpha_i=0; hover αi\alpha_i to size every point by its multiplier. Each cycle replays the solver, sequential minimal optimisation (SMO): every iteration picks the pair of points that violates the optimality conditions most, solves the two-variable problem in closed form, and keeps ∑iαiyi=0\sum_i\alpha_iy_i=0. Here it converges in 6 iterations.

The Elements of Statistical Learning, Hastie, Tibshirani & Friedman, Sec. 12.2.1, Computing the support vector classifier

Hands-On Machine Learning, Aurélien Géron, Ch. 5, Under the hood: the dual problem

The rest of this lesson is in Pro

  • 04Feature maps and the kernel trick
  • 05The RBF kernel: a bump around every support vector
  • 06γ and C: two knobs on one bias–variance trade-off
  • 07SVMs today: where they still win
  • Python challenge: RBF kernel, hinge loss and a linear SVM from scratch
  • Knowledge check, 4 questions

Pro opens all 45 lessons, every graded Python challenge and the full 3D labs.

Compiling scene

The Python challenge and knowledge check for this lesson are part of Pro.

Questions learners ask

What is the difference between a support vector machine and logistic regression?
Both learn a linear decision boundary, usually with an L2 penalty, and often reach similar accuracy. Logistic regression minimises the log loss, outputs probabilities and lets every training point influence the fit. A support vector machine minimises the hinge loss, so points beyond the margin have no influence at all and the solution depends only on the support vectors. Its output is a score rather than a probability, and it extends naturally to non-linear boundaries through kernels.
How do I choose C and gamma for an RBF SVM?
Standardise the features first, then run a cross-validated grid or random search over both parameters on a logarithmic scale, for example powers of ten from 0.001 to 1000. Large values of gamma and C fit the training data more closely and risk overfitting; small values give smoother, simpler boundaries that may underfit. A model in which nearly every training point is a support vector is usually overfitting.
What is the kernel trick?
Many algorithms, including the SVM dual, use the data only through inner products between pairs of points. A kernel function computes the inner product of two points after a feature map without constructing the mapped features. The polynomial kernel (x·z + 1) squared equals the inner product of six quadratic features in two dimensions, and the RBF kernel corresponds to infinitely many features, yet each costs about as much as one ordinary inner product to evaluate.

Next in Classical Machine Learning

2.6k-means, Gaussian mixtures and EMUnsupervised structure: Lloyd's algorithm, k-means++ seeding, and soft clustering with expectation-maximisation.

Sources

  • Hands-On Machine Learning, Aurélien Géron
  • An Introduction to Statistical Learning, James, Witten, Hastie & Tibshirani
  • The Elements of Statistical Learning, Hastie, Tibshirani & Friedman