Machine Learning · Lecture 7

Lecture 7
Kernels and Support Vector Machines

Part II · Kernels and graphs  |  maximum-margin classifiers, Lagrange duality and the KKT conditions, the dual SVM and support vectors, soft margins and the hinge loss, feature maps and the kernel trick, positive semi-definite kernels, Mercer's theorem and reproducing kernel Hilbert spaces, the representer theorem, kernel ridge regression, Gaussian processes, random features and the neural tangent kernel, quantum kernels  |  reading: Schölkopf & Smola, Learning with Kernels, ch. 1–2 and 7; Rasmussen & Williams, Gaussian Processes for Machine Learning, ch. 2 and 5

Cartoon: the widest streetTwo groups of houses sit on either side of a road. A stick figure with a measuring tape says: I'll build the road as wide as the houses allow. A second stick figure points at the few houses touching the kerb and says: so only those houses decide where it goes? I'll make the road as wideas the houses allow. So only the houses on thekerb decide where it goes?
The support vector machine finds the widest street between two classes; only the points on its edges matter
In this lecture
  1. The widest street
  2. Constrained optimisation: Lagrange multipliers, duality and KKT
  3. The dual SVM, support vectors and soft margins
  4. Feature maps and the kernel trick
  5. Which functions are kernels?
  6. The representer theorem and kernel ridge regression
  7. Gaussian processes
  8. Kernels at scale, in deep learning and on quantum computers
  9. Summary, exercises, projects, reading

Lecture 6 ended with a margin bound: a linear classifier generalises well when it separates the data with a wide margin relative to the size of its weights, whatever the dimension. The support vector machine turns that into an algorithm: find the separating line with the widest margin. Solving that problem through its dual reveals two surprises. The answer depends only on a few training points, the support vectors. And the data enter only through inner products \(x_i^\top x_j\), so we can replace them by a kernel \(k(x_i,x_j)\), an inner product in a much richer feature space that we never compute directly. That one substitution turns linear methods into flexible nonlinear ones, and leads to kernel ridge regression and to Gaussian processes, the Bayesian version of the same idea.

By the end of this lecture you should be able to set up the hard- and soft-margin SVM, derive its dual with Lagrange multipliers, and read off the support vectors from the KKT conditions; relate the soft-margin SVM to hinge loss with a ridge penalty; explain the kernel trick and check whether a function is a valid kernel; state Mercer's theorem and the representer theorem and prove the latter; fit kernel ridge regression and Gaussian process regression, and explain why they give the same predictions; choose kernel hyperparameters by cross-validation or marginal likelihood; and say what random features, the neural tangent kernel and quantum kernels have to do with all this.

1 — The widest street

Take two classes that a line can separate. Infinitely many lines do it. The perceptron of Lecture 4 stops at the first one it finds; logistic regression keeps pushing until the probabilities saturate. The SVM picks the line that stays as far as possible from both classes, the middle of the widest street that fits between them. Points near the boundary are the hard cases, and a boundary that leaves them room is less likely to be wrong on nearby new points; Lecture 6's margin bound makes that precise.

proposition 7.1 — distance to a hyperplane

The distance from a point \(x\) to the hyperplane \(\{z:w^\top z+b=0\}\) is

$$|w^\top x+b|/\|w\|.$$

The closest point of the hyperplane to \(x\) is \(x-tw\) for the \(t\) with \(w^\top(x-tw)+b=0\), that is

$$t=(w^\top x+b)/\|w\|^2.$$

The distance is

$$\|tw\|=|w^\top x+b|/\|w\|.\ \square$$

With labels \(y_i\in\{-1,+1\}\), the hyperplane classifies \(x_i\) correctly with room to spare when \(y_i(w^\top x_i+b)>0\), and its distance from the boundary is \(y_i(w^\top x_i+b)/\|w\|\). Rescaling \(w\) and \(b\) together does not change the hyperplane, so we may fix the scale by requiring the closest points to satisfy \(y_i(w^\top x_i+b)=1\). Then the margin on each side is \(1/\|w\|\), the street has width \(2/\|w\|\), and maximising the width means minimising \(\|w\|\).

definition 7.1 — the hard-margin SVM

Given linearly separable data \((x_i,y_i)\), \(y_i\in\{\pm1\}\), the hard-margin support vector machine solves

$$\min_{w,b}\ \tfrac12\|w\|^2\quad\text{subject to}\quad y_i(w^\top x_i+b)\ge1,\quad i=1,\dots,n.$$

The lines \(w^\top x+b=\pm1\) are the edges of the street, and the classifier is \(\operatorname{sign}(w^\top x+b)\).

The widest street

Drag the points. The black line is the SVM boundary and the dashed lines are the edges of the street; amber rings mark the support vectors. With a large \(C\) the SVM insists on a clean separation (hard margin); lower \(C\) to let points inside the street in exchange for a wider one (Section 3).

Move a point that is not ringed, anywhere outside the street, and nothing changes. Move a ringed one and the whole street moves. With the default points and \(C=100\) there are exactly two support vectors, one from each class; drop \(C\) to 1 and the street widens to swallow two more.

spot check 7.1

An SVM in the plane has \(w=(3,4)\). How wide is its street?

The width is \(2/\|w\|\).
\(\|w\|=5\), so the width is \(2/5=0.4\): each support vector is \(0.2\) from the boundary.

2 — Constrained optimisation: Lagrange multipliers, duality and KKT

The SVM is a minimisation with inequality constraints. Gradient descent alone does not handle constraints, so we need the standard toolkit, which is worth learning once because it appears all over machine learning papers.

Start with the picture. Minimise a convex function \(f\) over a region cut out by constraints \(g_i(x)\le0\). If the minimum is inside the region, \(\nabla f=0\) there. If it is on the boundary, the downhill direction \(-\nabla f\) must point out of the region (otherwise we could keep going), and that means \(-\nabla f\) is a nonnegative combination of the outward normals \(\nabla g_i\) of the constraints that are active, those holding with equality. Think of a ball rolling downhill until it rests against walls: the walls push back with forces \(\mu_i\ge0\), and only the walls it touches can push.

theorem 7.2 — Karush–Kuhn–Tucker conditions

Consider \(\min_xf(x)\) subject to \(g_i(x)\le0\), \(i=1,\dots,m\), with \(f\) and the \(g_i\) convex and differentiable, and suppose some \(x\) satisfies every constraint strictly (Slater's condition).

Then \(x^*\) is optimal if and only if there are multipliers \(\mu_1,\dots,\mu_m\) with

$$\nabla f(x^*)+\sum_i\mu_i\nabla g_i(x^*)=0,\qquad g_i(x^*)\le0,\qquad \mu_i\ge0,\qquad \mu_ig_i(x^*)=0.$$

These are stationarity, primal feasibility, dual feasibility and complementary slackness: a multiplier can be nonzero only if its constraint is active.

Suppose the conditions hold and \(x\) is any feasible point. The Lagrangian

$$\mathcal L(x,\mu)=f(x)+\sum_i\mu_ig_i(x)$$

is convex in \(x\) (a sum of convex functions with nonnegative weights), and stationarity says \(\nabla_x\mathcal L(x^*,\mu)=0\), so \(x^*\) minimises \(\mathcal L(\cdot,\mu)\). Then

$$f(x)\ \ge\ f(x)+\sum_i\mu_ig_i(x)=\mathcal L(x,\mu)\ \ge\ \mathcal L(x^*,\mu)=f(x^*)+\sum_i\mu_ig_i(x^*)=f(x^*),$$

using \(\mu_i\ge0\) and \(g_i(x)\le0\) in the first step and complementary slackness in the last.

Necessity, which needs Slater's condition, is the harder direction; see Boyd and Vandenberghe (2004), Section 5.5. \(\square\)

The multipliers also define a second optimisation problem. The dual function \(q(\mu)=\min_x\mathcal L(x,\mu)\) is a lower bound on the optimum for every \(\mu\ge0\), and the dual problem is to find the best lower bound.

proposition 7.3 — weak and strong duality

For every \(\mu\ge0\), \(q(\mu)\le f(x)\) for every feasible \(x\) (weak duality), so

$$\max_{\mu\ge0}q(\mu)\le\min_{x\text{ feasible}}f(x).$$

Under the conditions of Theorem 7.2 the two are equal (strong duality), and the KKT multipliers solve the dual problem.

For feasible \(x\) and \(\mu\ge0\):

$$q(\mu)\le\mathcal L(x,\mu)=f(x)+\sum\mu_ig_i(x)\le f(x).$$

For strong duality, the chain in the proof of Theorem 7.2 with \(x=x^*\) shows \(q(\mu)=\mathcal L(x^*,\mu)=f(x^*)\) for the KKT multipliers. \(\square\)

spot check 7.2

At the optimum, a constraint that holds with strict inequality, \(g_i(x^*)<0\), has multiplier , and removing that constraint would .

Which walls push on the resting ball?
Complementary slackness forces \(\mu_i=0\) for inactive constraints, and the KKT conditions without that constraint are still satisfied by \(x^*\). In the SVM this will say that points strictly outside the street have no influence.

3 — The dual SVM, support vectors and soft margins

theorem 7.4 — the dual of the hard-margin SVM

The hard-margin SVM (Definition 7.1) has the dual problem

$$\max_{\alpha\ge0}\ \sum_{i=1}^n\alpha_i-\frac12\sum_{i,j}\alpha_i\alpha_jy_iy_j\,x_i^\top x_j\qquad\text{subject to}\qquad\sum_i\alpha_iy_i=0.$$

At the optimum,

$$w=\sum_i\alpha_iy_ix_i,$$

and \(\alpha_i>0\) only for points on the edges of the street, \(y_i(w^\top x_i+b)=1\): the support vectors.

The offset is \(b=y_s-w^\top x_s\) for any support vector \(x_s\), and the classifier is

$$f(x)=\operatorname{sign}\Big(\sum_{i}\alpha_iy_i\,x_i^\top x+b\Big).$$

Write the constraints as \(g_i=1-y_i(w^\top x_i+b)\le0\). The Lagrangian is

$$\mathcal L(w,b,\alpha)=\tfrac12\|w\|^2-\sum_i\alpha_i\big[y_i(w^\top x_i+b)-1\big].$$

For fixed \(\alpha\ge0\), minimise over \(w\) and \(b\). Setting

$$\nabla_w\mathcal L=w-\sum_i\alpha_iy_ix_i=0$$

gives \(w=\sum_i\alpha_iy_ix_i\). The Lagrangian is linear in \(b\) with slope \(-\sum_i\alpha_iy_i\); unless that is zero the minimum over \(b\) is \(-\infty\), so the dual is only interesting when \(\sum\alpha_iy_i=0\). Substituting,

$$\mathcal L=\tfrac12\Big\|\sum_i\alpha_iy_ix_i\Big\|^2-\sum_{i,j}\alpha_i\alpha_jy_iy_jx_i^\top x_j+\sum_i\alpha_i=\sum_i\alpha_i-\tfrac12\sum_{i,j}\alpha_i\alpha_jy_iy_jx_i^\top x_j.$$

The problem is convex with affine constraints, so strong duality holds whenever the data are separable.

Complementary slackness,

$$\alpha_i\big[y_i(w^\top x_i+b)-1\big]=0,$$

says \(\alpha_i>0\) only when the constraint is tight, which gives the support vectors and the formula for \(b\). \(\square\)

The dual has two features that matter more than the derivation. The solution is a weighted combination of the support vectors alone, often a small fraction of the data. And the data appear only through the inner products \(x_i^\top x_j\) and \(x_i^\top x\). Hold on to the second point; it is the door to Section 4.

Real data are rarely separable. The soft-margin SVM (Cortes and Vapnik, 1995) lets point \(i\) violate its constraint by a slack \(\xi_i\ge0\), at a price \(C\) per unit:

$$\min_{w,b,\xi}\ \tfrac12\|w\|^2+C\sum_i\xi_i\qquad\text{subject to}\qquad y_i(w^\top x_i+b)\ge1-\xi_i,\quad\xi_i\ge0.$$
proposition 7.5 — the soft margin is hinge loss plus a ridge penalty

The soft-margin SVM is equivalent to the unconstrained problem

$$\min_{w,b}\ \sum_i\max\big(0,1-y_i(w^\top x_i+b)\big)+\frac1{2C}\|w\|^2,$$

hinge loss (Lecture 5) with an \(\ell_2\) penalty.

Its dual is the hard-margin dual with the extra box constraint \(0\le\alpha_i\le C\). At the optimum,

For fixed \(w,b\), the best slack is the smallest allowed,

$$\xi_i=\max(0,1-y_i(w^\top x_i+b));$$

substituting and dividing by \(C\) gives the hinge form.

For the dual, the Lagrangian gains terms

$$C\sum\xi_i-\sum\alpha_i\xi_i-\sum\nu_i\xi_i$$

with \(\nu_i\ge0\) for the constraints \(\xi_i\ge0\). Setting its derivative in \(\xi_i\) to zero gives \(\alpha_i=C-\nu_i\le C\), and the \(\xi\) terms then vanish, leaving the same dual objective.

Complementary slackness on the two families of constraints gives the three cases: \(\alpha_i<C\) forces \(\nu_i>0\), so \(\xi_i=0\); \(\alpha_i>0\) forces the margin constraint to be tight. \(\square\)

So \(C\) is an inverse regularisation strength. Small \(C\) means a wide street and many points allowed inside it (high bias, low variance); large \(C\) approaches the hard margin. Here is the breast-cancer data of Lectures 4–6 with standardised features.

data — Wisconsin diagnostic breast cancer

569 breast-mass biopsies, 212 malignant, with 30 features of the cell nuclei (Street, Wolberg and Mangasarian, 1993; UCI, via scikit-learn). Same 398/171 stratified split as Lectures 4–6, features standardised on the training set.

code — linear SVMs on the breast-cancer data
import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

bc = load_breast_cancer()
X, y = bc.data, 1 - bc.target                          # malignant = 1, as in Lectures 4-6
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, stratify=y, random_state=0)
sc = StandardScaler().fit(Xtr)
Ztr, Zte = sc.transform(Xtr), sc.transform(Xte)

print('     C   support vectors   margin width 2/||w||   train acc.   test acc.')
for C in [0.001, 0.01, 0.1, 1, 10, 100]:
    svm = SVC(kernel='linear', C=C).fit(Ztr, ytr)
    w = svm.coef_[0]
    print(f'{C:6g}   {svm.n_support_.sum():15d}   {2 / np.linalg.norm(w):20.3f}'
          f'   {svm.score(Ztr, ytr):10.3f}   {svm.score(Zte, yte):9.3f}')

# The weights are a combination of the support vectors only: w = sum_i alpha_i y_i x_i
svm = SVC(kernel='linear', C=0.1).fit(Ztr, ytr)
w_from_sv = svm.dual_coef_[0] @ svm.support_vectors_     # dual_coef_ holds alpha_i * y_i (y = +-1)
print('max |w - sum alpha_i y_i x_i| =', np.abs(w_from_sv - svm.coef_[0]).max())
alpha = np.abs(svm.dual_coef_[0])
print(f'C = 0.1: {np.sum(alpha < 0.1 - 1e-8)} support vectors on the margin (0 < alpha < C),'
      f' {np.sum(alpha >= 0.1 - 1e-8)} inside it or misclassified (alpha = C)')
     C   support vectors   margin width 2/||w||   train acc.   test acc.
 0.001               194                  6.367        0.932       0.953
  0.01                91                  3.033        0.975       0.965
   0.1                49                  1.385        0.990       0.959
     1                31                  0.619        0.995       0.942
    10                22                  0.324        0.995       0.953
   100                21                  0.114        1.000       0.942
max |w - sum alpha_i y_i x_i| = 0.0
C = 0.1: 12 support vectors on the margin (0 < alpha < C), 37 inside it or misclassified (alpha = C)

As \(C\) grows the street narrows (from 6.4 to 0.11 in standardised units), the number of support vectors falls from 194 to 21, and training accuracy rises to 100%. Test accuracy peaks at \(C=0.01\) and then wobbles between 94% and 96%, differences of two or three patients. The identity \(w=\sum\alpha_iy_ix_i\) holds to machine precision, and the split of support vectors into "on the edge" and "inside the street" follows Proposition 7.5.

spot check 7.3

A training point has \(y_i(w^\top x_i+b)=2.5\) at the soft-margin optimum. What is its \(\alpha_i\), and what happens to the classifier if the point is deleted and the SVM refitted?

Proposition 7.5 lists three cases by where the point sits relative to the street.
Margin above 1 means strictly outside the street, so \(\alpha_i=0\) by complementary slackness. Deleting it leaves the KKT conditions satisfied by the same \(w,b\).
history — from the generalised portrait to the kernel era

Vapnik and Lerner's "generalised portrait" algorithm (1963) already found the maximum-margin hyperplane. The kernel idea appeared separately in 1964, when Aizerman, Braverman and Rozonoer, at the same Moscow Institute of Control Sciences, interpreted "potential functions" as inner products in a feature space. The two were combined only in 1992, when Bernhard Boser, Isabelle Guyon and Vapnik at AT&T Bell Labs applied the kernel trick to maximum-margin classifiers; Corinna Cortes and Vapnik added the soft margin in 1995. SVMs then matched hand-engineered systems on digit recognition with no image-specific design, and the 2000s became the "kernel era" of machine learning, until deep networks overtook them on images and speech around 2012. Platt's SMO algorithm (1998), which solves the dual two multipliers at a time, made them practical; LIBSVM, still behind scikit-learn's SVC, uses a refined version, as do this lecture's widgets.

4 — Feature maps and the kernel trick

A line cannot separate points that are positive far from the origin and negative near it. But give each point a second coordinate, its square, and the classes become separable by a horizontal line in the new plane. A linear classifier on the lifted features \(\varphi(x)=(x,x^2)\) is a quadratic classifier on \(x\).

Lifting a line into a parabola

Slide the lift from 0 (the points on the line) to 1 (each point raised to \((x,x^2)\)). Then move the amber line. A horizontal line in the lifted plane is a pair of thresholds back on the axis.

Any feature map \(\varphi:\mathcal X\to\mathbb R^D\) can be fed to the SVM by replacing \(x\) with \(\varphi(x)\). The catch is that rich feature maps are huge: all monomials of degree at most 3 in 30 variables already number 5,456. Theorem 7.4 shows the way out. The dual and the classifier use the data only through inner products, so all we ever need is the function

$$k(x,z)=\varphi(x)^\top\varphi(z),$$

and if \(k\) can be computed without forming \(\varphi\), the dimension never matters. This is the kernel trick. The kernel SVM solves the dual with \(x_i^\top x_j\) replaced by \(k(x_i,x_j)\) and predicts with \(\operatorname{sign}\big(\sum_i\alpha_iy_ik(x_i,x)+b\big)\).

proposition 7.6 — the polynomial kernel

For \(x,z\in\mathbb R^p\) and an integer \(d\ge1\),

$$k(x,z)=(x^\top z+1)^d$$

equals \(\varphi(x)^\top\varphi(z)\) for a feature map \(\varphi\) whose coordinates are all monomials of degree at most \(d\) in \(x\), each multiplied by the square root of a multinomial coefficient.

For \(p=2\), \(d=2\):

$$\varphi(x)=\big(1,\ \sqrt2x_1,\ \sqrt2x_2,\ x_1^2,\ x_2^2,\ \sqrt2x_1x_2\big).$$

Write \(x^\top z+1=\sum_{j=0}^px_jz_j\) with \(x_0=z_0=1\). By the multinomial theorem,

$$(\sum_jx_jz_j)^d=\sum_{|m|=d}\binom d{m}\prod_j(x_jz_j)^{m_j}=\sum_{|m|=d}\Big(\sqrt{\tbinom dm}\prod_jx_j^{m_j}\Big)\Big(\sqrt{\tbinom dm}\prod_jz_j^{m_j}\Big),$$

a sum of products of matching features. Dropping \(x_0=1\), each \(m\) gives a monomial of degree at most \(d\) in \(x_1,\dots,x_p\). \(\square\)

Computing \((x^\top z+1)^3\) on 30 features costs about 30 multiplications instead of 5,456. The most widely used kernel goes further. The Gaussian or RBF kernel

$$k(x,z)=\exp\big(-\gamma\|x-z\|^2\big)$$

corresponds to an infinite-dimensional feature map: in one dimension, \(e^{-\gamma(x-z)^2}=e^{-\gamma x^2}e^{-\gamma z^2}\sum_{m\ge0}\frac{(2\gamma)^m}{m!}x^mz^m\), an inner product of the features \(e^{-\gamma x^2}\sqrt{(2\gamma)^m/m!}\,x^m\), \(m=0,1,2,\dots\). The RBF classifier \(\sum\alpha_iy_ie^{-\gamma\|x_i-x\|^2}+b\) is a sum of bumps centred on the support vectors, and \(\gamma\) sets their width. Small \(\gamma\) gives wide bumps and a smooth, nearly linear boundary; large \(\gamma\) gives narrow bumps that can wrap around individual points. It is a bias–variance dial, like \(k\) in nearest neighbours.

An RBF SVM on two moons

100 training points from scikit-learn's two-moons generator (noise 0.25). The shading is the sign of the SVM's decision function, darker where it is more confident; amber rings are support vectors. Test accuracy is on 400 fresh points from the same generator.

With \(\gamma=5\) and \(C=10\) the boundary follows the moons, uses 30 support vectors, and gets 92.75% of new points right. Push to \(\gamma=50\), \(C=100\): every training point is classified correctly, 93 of the 100 are support vectors, and test accuracy falls to 91.5%. A large fraction of support vectors is a warning sign of overfitting. On the breast-cancer data, the kernel buys little:

code — choosing C and γ by cross-validation
from sklearn.model_selection import GridSearchCV

grid = {'C': [0.1, 1, 10, 100], 'gamma': [0.001, 0.01, 0.1, 1]}
cv = GridSearchCV(SVC(kernel='rbf'), grid, cv=5).fit(Ztr, ytr)
res = cv.cv_results_['mean_test_score'].reshape(4, 4)
print('5-fold CV accuracy (rows C, columns gamma = 0.001, 0.01, 0.1, 1)')
for C, row in zip(grid['C'], res):
    print(f'C = {C:5g}: ' + '  '.join(f'{v:.3f}' for v in row))
best = cv.best_estimator_
print('best:', cv.best_params_, ' support vectors:', best.n_support_.sum(), ' test accuracy:', round(best.score(Zte, yte), 3))
lin = GridSearchCV(SVC(kernel='linear'), {'C': [0.001, 0.01, 0.1, 1, 10]}, cv=5).fit(Ztr, ytr)
print('linear SVM, C chosen by CV:', lin.best_params_, ' test accuracy:', round(lin.score(Zte, yte), 3))
print('\ngamma    train acc.   test acc.   (C = 10)')
for g in [0.0001, 0.01, 1, 100]:
    m = SVC(kernel='rbf', C=10, gamma=g).fit(Ztr, ytr)
    print(f'{g:<7g}   {m.score(Ztr, ytr):9.3f}   {m.score(Zte, yte):9.3f}')
5-fold CV accuracy (rows C, columns gamma = 0.001, 0.01, 0.1, 1)
C =   0.1: 0.688  0.937  0.940  0.628
C =     1: 0.940  0.972  0.970  0.628
C =    10: 0.970  0.982  0.967  0.628
C =   100: 0.980  0.975  0.967  0.628
best: {'C': 10, 'gamma': 0.01}  support vectors: 48  test accuracy: 0.953
linear SVM, C chosen by CV: {'C': 1}  test accuracy: 0.942

gamma    train acc.   test acc.   (C = 10)
0.0001        0.947       0.953
0.01          0.995       0.953
1             1.000       0.626
100           1.000       0.626

Cross-validation picks \(C=10\), \(\gamma=0.01\), a wide bump (in 30 standardised dimensions, typical squared distances between patients are 40 to 60, so \(\gamma\|x-z\|^2\) is of order 1). Test accuracy 95.3% against 94.2% for the linear SVM: two patients, well within noise. The last table shows the dial at its extremes. With \(\gamma=1\) each bump is so narrow that the classifier memorises the training set and predicts "benign" for every new patient, which is right 62.6% of the time only because 107 of the 171 test patients are benign.

spot check 7.4

How many monomials of degree at most 3 are there in 30 variables? (This is the dimension of the feature space of \((x^\top z+1)^3\) on the breast-cancer data.)

Monomials of degree at most \(d\) in \(p\) variables correspond to multisets of size \(d\) from \(p+1\) symbols (one symbol for "1"): \(\binom{p+d}d\).
\(\binom{33}3=\frac{33\cdot32\cdot31}6=5456\). For degree 10 it would be \(\binom{40}{10}\approx8.5\times10^8\); the kernel still costs 30 multiplications and one power.

5 — Which functions are kernels?

We can now design \(k\) directly, as a similarity between objects: strings, graphs, molecules, images. But not every similarity is an inner product in some feature space, and the SVM's optimisation is only convex if it is.

definition 7.2 — positive semi-definite kernel

A symmetric function \(k:\mathcal X\times\mathcal X\to\mathbb R\) is a (positive semi-definite) kernel if for every \(n\) and every \(x_1,\dots,x_n\in\mathcal X\), the Gram matrix \(K_{ij}=k(x_i,x_j)\) is positive semi-definite:

$$c^\top Kc=\sum_{i,j}c_ic_jk(x_i,x_j)\ge0$$

for all \(c\in\mathbb R^n\).

theorem 7.7 — kernels are exactly inner products of feature maps

\(k\) is a positive semi-definite kernel if and only if there is a Hilbert space \(\mathcal H\) and a map \(\varphi:\mathcal X\to\mathcal H\) with

$$k(x,z)=\langle\varphi(x),\varphi(z)\rangle_{\mathcal H}.$$

(\(\Leftarrow\))

$$\sum_{i,j}c_ic_j\langle\varphi(x_i),\varphi(x_j)\rangle=\big\|\sum_ic_i\varphi(x_i)\big\|^2\ge0.$$

(\(\Rightarrow\), sketch; Aronszajn, 1950.) Take \(\varphi(x)=k(x,\cdot)\), the function "similarity to \(x\)". On finite combinations \(f=\sum_ia_ik(x_i,\cdot)\) and \(g=\sum_jb_jk(z_j,\cdot)\) define

$$\langle f,g\rangle=\sum_{i,j}a_ib_jk(x_i,z_j).$$

Positive semi-definiteness makes this a valid inner product (the Cauchy–Schwarz inequality shows \(\langle f,f\rangle=0\) forces \(f=0\)), and by construction

$$\langle k(x,\cdot),k(z,\cdot)\rangle=k(x,z).$$

Completing the space gives \(\mathcal H\). \(\square\)

The space built in the proof deserves a name, because papers use it constantly.

definition 7.3 — reproducing kernel Hilbert space

The RKHS \(\mathcal H_k\) of a kernel \(k\) is the completion of the span of the functions \(k(x,\cdot)\), with the inner product above.

Its defining property is the reproducing property: for every \(f\in\mathcal H_k\) and \(x\in\mathcal X\),

$$f(x)=\langle f,k(x,\cdot)\rangle_{\mathcal H_k}.$$

The norm \(\|f\|_{\mathcal H_k}\) measures how "rough" \(f\) is relative to the kernel: for the RBF kernel, functions with small RKHS norm are smooth on the length scale \(1/\sqrt\gamma\).

Proving a function is a kernel from the definition is tedious. In practice one builds kernels from simpler ones.

proposition 7.8 — building kernels

If \(k_1,k_2\) are kernels, \(c\ge0\) and \(f:\mathcal X\to\mathbb R\), then these are kernels: \(ck_1\), \(k_1+k_2\), \(k_1k_2\), \(f(x)k_1(x,z)f(z)\), any limit of kernels, and \(\exp(k_1)\).

Consequently \(x^\top z\), \((x^\top z+1)^d\) and \(\exp(-\gamma\|x-z\|^2)\) are kernels.

Scaling and sums:

$$c^\top(aK_1+K_2)c=ac^\top K_1c+c^\top K_2c\ge0.$$

Products: the Gram matrix of \(k_1k_2\) is the elementwise (Schur) product \(K_1\circ K_2\). Writing \(K_2=\sum_\ell\lambda_\ell u_\ell u_\ell^\top\) with \(\lambda_\ell\ge0\),

$$c^\top(K_1\circ K_2)c=\sum_\ell\lambda_\ell(c\circ u_\ell)^\top K_1(c\circ u_\ell)\ge0.$$

The \(f\) rule: \(c^\top Kc\) with \(c_i\) replaced by \(c_if(x_i)\). Limits preserve \(\ge0\). \(\exp(k_1)=\sum_m k_1^m/m!\) is a limit of sums of products.

Finally,

$$e^{-\gamma\|x-z\|^2}=e^{-\gamma\|x\|^2}\,e^{2\gamma x^\top z}\,e^{-\gamma\|z\|^2},$$

the \(f\) rule applied to \(\exp(2\gamma x^\top z)\). \(\square\)

code — checking feature maps and Gram matrices
# The polynomial kernel (x.z + 1)^2 is an inner product of explicit 6-dimensional features
def phi(v):
    a, b = v
    return np.array([1, np.sqrt(2) * a, np.sqrt(2) * b, a * a, b * b, np.sqrt(2) * a * b])
x, z = np.array([1.0, 2.0]), np.array([-0.5, 3.0])
print('phi(x).phi(z) =', phi(x) @ phi(z), '   (x.z + 1)^2 =', (x @ z + 1) ** 2)

# Gram matrices of valid kernels are positive semi-definite; the "sigmoid kernel" is not always a kernel
S = Ztr[:200]
sq = ((S[:, None, :] - S[None, :, :]) ** 2).sum(-1)
grams = {'RBF exp(-||x-z||^2 / 30)': np.exp(-sq / 30),
         'polynomial (x.z/30 + 1)^3': (S @ S.T / 30 + 1) ** 3,
         'sigmoid tanh(x.z/30 - 1)': np.tanh(S @ S.T / 30 - 1)}
for name, K in grams.items():
    ev = np.linalg.eigvalsh(K)
    print(f'{name:28s} smallest eigenvalue {ev[0]: .3e}   largest {ev[-1]:.3e}')
phi(x).phi(z) = 42.25    (x.z + 1)^2 = 42.25
RBF exp(-||x-z||^2 / 30)     smallest eigenvalue  2.872e-03   largest 7.222e+01
polynomial (x.z/30 + 1)^3    smallest eigenvalue  3.332e-03   largest 2.741e+03
sigmoid tanh(x.z/30 - 1)     smallest eigenvalue -1.398e+02   largest 4.672e+01

The explicit six features reproduce the polynomial kernel exactly. On 200 patients, the RBF and polynomial Gram matrices have all eigenvalues positive. The "sigmoid kernel" \(\tanh(a\,x^\top z+c)\), offered by many libraries because it mimics a neural network unit, has an eigenvalue of \(-140\): it is not a kernel for these parameters, and an SVM trained with it solves a non-convex problem.

theorem 7.9 — Mercer's theorem

Let \(\mathcal X\) be a compact set with a finite measure \(\mu\) and \(k\) a continuous kernel. Then there are nonnegative eigenvalues \(\lambda_1\ge\lambda_2\ge\cdots\to0\) and orthonormal eigenfunctions \(e_j\) of the integral operator

$$(T_kf)(x)=\int k(x,z)f(z)\,d\mu(z)$$

such that

$$k(x,z)=\sum_{j\ge1}\lambda_j\,e_j(x)\,e_j(z),$$

with absolute and uniform convergence.

So \(\varphi(x)=(\sqrt{\lambda_j}\,e_j(x))_{j\ge1}\) is an explicit feature map (Mercer, 1909).

Mercer's theorem is the spectral theorem of Lecture 2 for an infinite matrix. It also explains what the RKHS norm penalises: writing \(f=\sum_ja_je_j\), one has \(\|f\|_{\mathcal H_k}^2=\sum_ja_j^2/\lambda_j\), so components along eigenfunctions with small eigenvalues (for the RBF kernel, the wiggly ones) are expensive.

spot check 7.5

Which of these is not a positive semi-definite kernel on \(\mathbb R\)?

A Gram matrix of a kernel has nonnegative diagonal entries \(k(x,x)\).
\(k(x,x)=0\) for every \(x\), and for two points the Gram matrix \(\begin{pmatrix}0&-d\\-d&0\end{pmatrix}\) has eigenvalue \(-d<0\). (Minus a distance is only "conditionally" positive definite, a weaker property.)

6 — The representer theorem and kernel ridge regression

Why should the solution of a learning problem in an infinite-dimensional space be a combination of kernels centred at the training points? It was for the SVM by duality, and the same holds for a whole family of problems.

theorem 7.10 — the representer theorem

Let \(L\) be any loss of the predictions on the training points and \(\Omega\) a strictly increasing function. Every minimiser over \(f\in\mathcal H_k\) of

$$L\big(f(x_1),\dots,f(x_n)\big)+\Omega\big(\|f\|_{\mathcal H_k}\big)$$

has the form

$$f(x)=\sum_{i=1}^n\alpha_ik(x_i,x)$$

(Kimeldorf and Wahba, 1971; Schölkopf, Herbrich and Smola, 2001).

Split any \(f\in\mathcal H_k\) as \(f=f_\parallel+f_\perp\), where \(f_\parallel\) lies in the span of \(k(x_1,\cdot),\dots,k(x_n,\cdot)\) and \(f_\perp\) is orthogonal to it.

By the reproducing property,

$$f(x_i)=\langle f_\parallel+f_\perp,k(x_i,\cdot)\rangle=f_\parallel(x_i),$$

so the loss does not see \(f_\perp\). But

$$\|f\|^2=\|f_\parallel\|^2+\|f_\perp\|^2,$$

so \(\Omega\) strictly prefers \(f_\perp=0\). Hence every minimiser has \(f_\perp=0\). \(\square\)

An infinite-dimensional problem becomes an \(n\)-dimensional one. With squared loss it can be solved in closed form.

proposition 7.11 — kernel ridge regression

The minimiser of

$$\sum_i\big(y_i-f(x_i)\big)^2+\lambda\|f\|_{\mathcal H_k}^2$$

is

$$\hat f(x)=\sum_i\alpha_ik(x_i,x)=k(x)^\top\alpha,$$

with

$$\alpha=(K+\lambda I)^{-1}y,$$

where \(K\) is the Gram matrix and \(k(x)=(k(x_1,x),\dots,k(x_n,x))^\top\).

With the linear kernel \(k(x,z)=x^\top z\) this is exactly the ridge regression of Lecture 3.

By Theorem 7.10, \(f=\sum_j\alpha_jk(x_j,\cdot)\), so \(f(x_i)=(K\alpha)_i\) and \(\|f\|^2=\alpha^\top K\alpha\). The objective \(\|y-K\alpha\|^2+\lambda\alpha^\top K\alpha\) has gradient

$$-2K(y-K\alpha)+2\lambda K\alpha=-2K\big(y-(K+\lambda I)\alpha\big),$$

which vanishes at \(\alpha=(K+\lambda I)^{-1}y\).

For the linear kernel, \(K=XX^\top\) and

$$\hat f(x)=x^\top X^\top(XX^\top+\lambda I)^{-1}y=x^\top(X^\top X+\lambda I)^{-1}X^\top y$$

by the identity of Exercise 6. \(\square\)

Back to Lecture 1's crash-helmet data: 133 measurements of head acceleration after a simulated motorcycle crash. Kernel ridge regression with an RBF kernel \(\exp(-(t-t')^2/(2\ell^2))\) has a length scale \(\ell\) (in milliseconds) and a penalty \(\lambda\).

code — kernel ridge regression on the crash-helmet data
import pandas as pd
from sklearn.model_selection import KFold

mc = pd.read_csv('data/mcycle.csv')                       # the crash-helmet data of Lecture 1
t, acc = mc['times'].to_numpy(), mc['accel'].to_numpy()

def krr_fit_predict(t_tr, y_tr, t_new, ell, lam):
    K = np.exp(-(t_tr[:, None] - t_tr[None, :]) ** 2 / (2 * ell**2))
    alpha = np.linalg.solve(K + lam * np.eye(len(t_tr)), y_tr - y_tr.mean())   # (K + lambda I) alpha = y
    return y_tr.mean() + np.exp(-(t_new[:, None] - t_tr[None, :]) ** 2 / (2 * ell**2)) @ alpha

folds = list(KFold(5, shuffle=True, random_state=0).split(t))
print('length-scale   lambda   5-fold CV RMSE')
scores = {}
for ell in [0.5, 1, 2, 4, 8]:
    for lam in [0.1, 1, 10]:
        err = [np.mean((krr_fit_predict(t[a], acc[a], t[b], ell, lam) - acc[b]) ** 2) for a, b in folds]
        scores[ell, lam] = np.sqrt(np.mean(err))
for (ell, lam), s in scores.items():
    if lam == 1 or s == min(scores.values()):
        print(f'{ell:12g}   {lam:6g}   {s:14.2f}' + ('   <- best' if s == min(scores.values()) else ''))
length-scale   lambda   5-fold CV RMSE
         0.5        1            32.32
           1        1            26.89
           2        1            24.27
           4        1            23.38   <- best
           8        1            27.01

A length scale of 4 ms gives a cross-validated error of 23.4 (in units of g), about as good as Lecture 3's penalised spline. Too short (0.5 ms) chases the noise; too long (8 ms) smooths away the sharp dip after impact. The fit is ten lines of linear algebra, and the same code works for any kernel and any input type.

The margin theory of Lecture 6 carries over directly, with the RKHS in place of \(\mathbb R^p\).

proposition 7.12 — complexity of a kernel class

For \(\mathcal F_B=\{f\in\mathcal H_k:\|f\|_{\mathcal H_k}\le B\}\) and a sample \(x_1,\dots,x_n\),

$$\widehat{\mathfrak R}_S(\mathcal F_B)\le\frac Bn\sqrt{\operatorname{tr}K}=\frac Bn\sqrt{\sum_ik(x_i,x_i)}.$$

For the RBF kernel \(k(x,x)=1\), so the bound is \(B/\sqrt n\) in any dimension, and the margin bound (Theorem 6.13) applies to kernel SVMs with \(\|w\|\) replaced by \(\|f\|_{\mathcal H_k}\).

The proof of Proposition 6.11 with \(x_i\) replaced by \(\varphi(x_i)=k(x_i,\cdot)\):

$$\sup_{\|f\|\le B}\frac1n\sum\sigma_if(x_i)=\sup\frac1n\langle f,\sum\sigma_ik(x_i,\cdot)\rangle=\frac Bn\|\sum_i\sigma_ik(x_i,\cdot)\|,$$

and

$$\mathbb E\|\sum\sigma_ik(x_i,\cdot)\|^2=\sum_ik(x_i,x_i).\ \square$$
spot check 7.6

Kernel ridge regression with an RBF kernel is fitted to all 133 crash-helmet measurements. The RBF feature space is infinite-dimensional; how many numbers does the fitted function need besides the training inputs and the kernel?

Theorem 7.10.
One coefficient \(\alpha_i\) per training point: 133. The price of the kernel trick is that prediction cost and memory grow with \(n\) rather than with the feature dimension, and solving \((K+\lambda I)\alpha=y\) costs \(O(n^3)\), which is why Section 8 matters.

7 — Gaussian processes

Kernel ridge regression gives a single function. The Bayesian version gives a distribution over functions, and with it, error bars. The idea is to put a prior directly on the unknown function: a random function whose values at any finite set of points are jointly Gaussian, with the kernel as their covariance.

definition 7.4 — Gaussian process

A Gaussian process \(f\sim\mathcal{GP}(m,k)\) is a random function such that for every finite set of inputs \(x_1,\dots,x_n\), the vector

$$(f(x_1),\dots,f(x_n))$$

is multivariate normal with mean \((m(x_i))_i\) and covariance matrix \(K_{ij}=k(x_i,x_j)\).

The kernel must be positive semi-definite, since covariance matrices are.

The kernel encodes what we believe about the function before seeing data. An RBF kernel with length scale \(\ell\) says the function is smooth and varies on scales of about \(\ell\); a periodic kernel says it repeats; a sum of kernels says the function is a sum of independent components of those kinds. Observing \(y_i=f(x_i)+\varepsilon_i\) with Gaussian noise of variance \(\sigma^2\) and conditioning gives the posterior in closed form.

theorem 7.13 — the GP posterior, and its link to kernel ridge regression

Let \(f\sim\mathcal{GP}(0,k)\) and \(y_i=f(x_i)+\varepsilon_i\) with \(\varepsilon_i\sim\mathcal N(0,\sigma^2)\) independent. Given the data, \(f(x)\) is Gaussian with

$$\mathbb E[f(x)\mid y]=k(x)^\top(K+\sigma^2I)^{-1}y,\qquad\operatorname{Var}[f(x)\mid y]=k(x,x)-k(x)^\top(K+\sigma^2I)^{-1}k(x).$$

The posterior mean is exactly the kernel ridge regression prediction with \(\lambda=\sigma^2\).

The vector \((f(x),y)\) is jointly Gaussian with mean zero and covariance

$$\begin{pmatrix}k(x,x)&k(x)^\top\\k(x)&K+\sigma^2I\end{pmatrix},$$

since \(\operatorname{Cov}(f(x),y_i)=k(x,x_i)\) and \(\operatorname{Cov}(y)=K+\sigma^2I\).

The conditional distribution of one block of a Gaussian vector given another is Gaussian with mean \(\Sigma_{12}\Sigma_{22}^{-1}y\) and variance \(\Sigma_{11}-\Sigma_{12}\Sigma_{22}^{-1}\Sigma_{21}\) (the regression formulas of Lecture 3).

Comparing with Proposition 7.11, \(\alpha=(K+\sigma^2I)^{-1}y\). \(\square\)

The posterior variance does not depend on \(y\): it measures only how close \(x\) is, in the kernel's sense, to where data were collected. Kernel hyperparameters (length scales, signal and noise variances) can be chosen by maximising the marginal likelihood of the data, the probability of \(y\) with \(f\) integrated out:

$$\log p(y)=-\tfrac12y^\top(K+\sigma^2I)^{-1}y-\tfrac12\log\det(K+\sigma^2I)-\tfrac n2\log2\pi.$$

The first term rewards fitting the data; the second penalises flexible kernels, which spread their prior probability over many possible data sets. It is Occam's razor built into Bayes' rule, and it replaces cross-validation with a single optimisation.

Gaussian process regression

Click on the plot to add an observation; click an observation to remove it. The line is the posterior mean and the band its 95% interval for the function \(f\). The prior is an RBF kernel with signal variance 1; set its length scale and the noise standard deviation and watch the marginal likelihood.

Far from the data the band widens back to the prior (±1.96) and the mean returns to zero: a GP knows where it has not looked. With the default six points, a length scale of 1 and noise 0.1, the log marginal likelihood is −7.18; shortening the length scale to 0.5 and raising the noise to 0.3 lowers it to −7.41. Clear the plot and add points along a straight line, and you will see the marginal likelihood prefer long length scales.

data — the Keeling curve

Monthly mean atmospheric CO₂ concentration (parts per million) measured at Mauna Loa Observatory, Hawaii, from March 1958 to August 2026: 822 months with data. Begun by Charles David Keeling of Scripps Institution of Oceanography; now maintained by NOAA Global Monitoring Laboratory (P. Tans) and Scripps (R. Keeling). We use the copy in the datasets/co2-ppm repository (Open Data Commons PDDL), which mirrors NOAA's monthly file.

Rasmussen and Williams (2006, Section 5.4.3) made this data set the standard GP demonstration, with a kernel built from parts: a smooth long-term trend, a yearly cycle that may slowly change shape, medium-term irregularities and noise. We fit it to the data up to 2015 and forecast the next ten and a half years.

code — forecasting CO₂ with a composite kernel
from sklearn.gaussian_process import GaussianProcessRegressor
from sklearn.gaussian_process.kernels import RBF, ExpSineSquared, RationalQuadratic, WhiteKernel, ConstantKernel as Cst

co2 = pd.read_csv('data/co2-mm-mlo.csv', header=None, skiprows=1,
                  names=['month', 'year', 'ppm', 'deseasonalised', 'days', 'sd', 'unc'])
co2 = co2[co2['ppm'] > 0]                                   # a few early months are missing (-99.99)
train, test = co2[co2['year'] < 2016], co2[co2['year'] >= 2016]
print(f'{len(co2)} months, {co2.month.iloc[0]} to {co2.month.iloc[-1]}; train to 2015 ({len(train)}), test from 2016 ({len(test)})')

kernel = (Cst(50.0**2) * RBF(50.0)                                         # long-term rise
          + Cst(2.0**2) * RBF(100.0) * ExpSineSquared(1.0, 1.0, periodicity_bounds='fixed')   # yearly cycle
          + Cst(0.5**2) * RationalQuadratic(1.0, 1.0)                          # medium-term wiggles
          + Cst(0.1**2) * RBF(0.1) + WhiteKernel(0.1**2))                      # noise
gp = GaussianProcessRegressor(kernel, normalize_y=True, random_state=0)
gp.fit(train[['year']].to_numpy(), train['ppm'].to_numpy())
print('learned kernel:', gp.kernel_)
mean, sd = gp.predict(test[['year']].to_numpy(), return_std=True)
y_te = test['ppm'].to_numpy()
inside = np.abs(y_te - mean) <= 1.96 * sd
print(f'forecast RMSE 2016-{test.month.iloc[-1][:4]}: {np.sqrt(np.mean((mean - y_te) ** 2)):.2f} ppm;'
      f' observed inside the 95% band: {inside.mean():.1%}')
for m in ['2016-05', '2021-05', test.month.iloc[-1]]:
    i = np.where(test.month.to_numpy() == m)[0][0]
    print(f'{m}: forecast {mean[i]:.2f} ± {1.96 * sd[i]:.2f}, observed {y_te[i]:.2f}')
822 months, 1958-03 to 2026-08; train to 2015 (694), test from 2016 (128)
learned kernel: 6.52**2 * RBF(length_scale=114) + 0.112**2 * RBF(length_scale=148) * ExpSineSquared(length_scale=1.54, periodicity=1) + 0.489**2 * RationalQuadratic(alpha=0.000709, length_scale=20.9) + 0.00739**2 * RBF(length_scale=0.12) + WhiteKernel(noise_level=5.85e-05)
forecast RMSE 2016-2026: 2.47 ppm; observed inside the 95% band: 66.4%
2016-05: forecast 406.49 ± 0.86, observed 407.90
2021-05: forecast 417.13 ± 2.45, observed 419.09
2026-08: forecast 423.88 ± 3.79, observed 427.55

The learned kernel is readable: a trend varying over about a century, a yearly cycle whose shape drifts over about 150 years, and irregularities on a 20-year scale. The forecasts are good for a year (406.5 forecast against 407.9 in May 2016) but fall steadily behind: by August 2026 the forecast is 423.9 and the truth 427.6. Only 66% of the observed months fall inside the 95% bands. This is an honest failure and a useful one. A GP with an RBF trend, extrapolated far from data, reverts toward the prior; it has no way to know that emissions kept rising and the growth rate accelerated. Its bands are honest about the noise it has seen, not about the possibility that the kernel's assumptions are wrong. Better forecasts need a kernel that encodes accelerating growth, or physics (emissions data), which is the GP version of choosing the right features.

spot check 7.7

In GP regression with noise variance \(\sigma^2>0\), what is true of the posterior mean at a training input \(x_i\)?

Look at the widget with a noise level of 0.5.
The mean is \(k(x_i)^\top(K+\sigma^2I)^{-1}y\), the kernel ridge fit with \(\lambda=\sigma^2\), which does not interpolate. For a single observation with \(k(x,x)=1\), it is \(y/(1+\sigma^2)\) (Exercise 7).
bayes — Bayesian optimisation: deciding where to look next

When each evaluation of a function is expensive (training a large model with given hyperparameters, synthesising a material, running a simulation), a GP posterior can decide where to evaluate next. An acquisition function such as expected improvement, \(\mathbb E[\max(0,f(x)-f_{\text{best}})]\), is computed in closed form from the posterior mean and variance and trades off exploiting promising regions (high mean) against exploring uncertain ones (high variance). Snoek, Larochelle and Adams (2012) showed this tunes neural network hyperparameters better than experts; DeepMind tuned AlphaGo's hyperparameters this way (Chen et al., 2018), and it is now standard in materials and drug discovery.

8 — Kernels at scale, in deep learning and on quantum computers

Random features

Exact kernel methods cost \(O(n^3)\) time and \(O(n^2)\) memory, impractical beyond a few tens of thousands of points. Rahimi and Recht (2007) turned the kernel trick around: approximate \(k\) by an explicit, finite random feature map, then use a linear method.

theorem 7.14 — Bochner's theorem and random Fourier features

A continuous shift-invariant function \(k(x,z)=\kappa(x-z)\) on \(\mathbb R^p\) with \(\kappa(0)=1\) is a kernel if and only if \(\kappa\) is the Fourier transform of a probability distribution \(\rho\):

$$\kappa(\delta)=\mathbb E_{\omega\sim\rho}\cos(\omega^\top\delta)$$

(Bochner, 1933).

Consequently, with \(\omega_1,\dots,\omega_D\sim\rho\) and \(b_j\sim\mathrm{Unif}[0,2\pi]\) independent, the features

$$z(x)=\sqrt{2/D}\,\big(\cos(\omega_1^\top x+b_1),\dots,\cos(\omega_D^\top x+b_D)\big)$$

satisfy

$$\mathbb E\,z(x)^\top z(x')=k(x,x'),$$

with error of order \(1/\sqrt D\).

For the RBF kernel \(e^{-\|x-z\|^2/(2s^2)}\), \(\rho=\mathcal N(0,s^{-2}I)\).

$$2\cos(a+b)\cos(c+b)=\cos(a-c)+\cos(a+c+2b),$$

and averaging over \(b\sim\mathrm{Unif}[0,2\pi]\) kills the second term. So each coordinate pair contributes

$$\frac2D\cdot\frac12\mathbb E\cos(\omega^\top(x-x'))=\frac1D\kappa(x-x'),$$

and summing over \(D\) coordinates gives \(\kappa(x-x')\). \(\square\)

code — random Fourier features for the RBF kernel
# Random Fourier features: approximate exp(-||x - z||^2 / (2 s^2)) by an explicit D-dimensional map
rng = np.random.default_rng(0)
s = 3.0
K_exact = np.exp(-sq / (2 * s**2))
print('     D   max |K_approx - K_exact|   ridge classifier on the features: test acc.')
from sklearn.linear_model import RidgeClassifier
for D in [10, 100, 1000, 10000]:
    W = rng.standard_normal((30, D)) / s                       # frequencies from the kernel's Fourier transform
    b = rng.uniform(0, 2 * np.pi, D)
    feat = lambda A: np.sqrt(2 / D) * np.cos(A @ W + b)
    err = np.abs(feat(S) @ feat(S).T - K_exact).max()
    clf = RidgeClassifier(alpha=1.0).fit(feat(Ztr), ytr)
    print(f'{D:6d}   {err:24.4f}   {clf.score(feat(Zte), yte):36.3f}')
     D   max |K_approx - K_exact|   ridge classifier on the features: test acc.
    10                     1.2474                                  0.731
   100                     0.4335                                  0.901
  1000                     0.1198                                  0.942
 10000                     0.0414                                  0.930

The worst-case error in the 200 × 200 Gram matrix falls by about \(\sqrt{10}\) for each tenfold increase in \(D\), as the theorem predicts, and a plain ridge classifier on 1,000 random features matches the kernel SVM. These are the random-feature models of Lecture 6's double-descent experiment: a two-layer network whose first layer is random and frozen.

The neural tangent kernel

The link to networks goes further. Train a network \(f(x;\theta)\) by gradient descent on squared loss. If the network is very wide and the parameters barely move from their initial values \(\theta_0\), a first-order Taylor expansion \(f(x;\theta)\approx f(x;\theta_0)+\nabla_\theta f(x;\theta_0)^\top(\theta-\theta_0)\) is accurate, and the network is a linear model in the features \(\nabla_\theta f(x;\theta_0)\).

theorem 7.15 — the neural tangent kernel (informal)

For fully connected networks in the "NTK parameterisation", as the widths of all hidden layers tend to infinity, the kernel

$$\Theta(x,x')=\nabla_\theta f(x;\theta)^\top\nabla_\theta f(x';\theta)$$

converges to a deterministic limit and stays constant during training.

Gradient flow on squared loss then makes the network's function evolve exactly as kernel regression with kernel \(\Theta\), and the trained infinitely wide network equals the minimum-norm kernel interpolant (Jacot, Gabriel and Hongler, 2018; Lee et al., 2019).

The NTK made over-parameterised networks analysable with the tools of this lecture and Lecture 6. Its limitation is also its lesson: in this regime the features do not change, so the network does not learn representations, and finite networks that do (Chizat, Oyallon and Bach, 2019, call the NTK regime "lazy training") usually beat their NTK on real data. Why feature learning helps is one of the central open questions of deep learning theory.

Quantum kernels

A quantum computer can prepare a state \(|\varphi(x)\rangle\) in a space of dimension \(2^q\) by running a circuit whose gate angles depend on \(x\), and estimate overlaps \(|\langle\varphi(x)|\varphi(z)\rangle|^2\) by repeated measurement. That overlap is a kernel (it is \(\langle\rho(x),\rho(z)\rangle\) for the density matrices \(\rho=|\varphi\rangle\langle\varphi|\)), so any quantum feature map defines a kernel SVM. The code simulates the "ZZ feature map" of Havlíček et al. (2019) exactly on the breast-cancer data, compressed to \(q\) principal components.

code — a simulated quantum kernel
# A quantum kernel, simulated exactly: the ZZ feature map of Havlicek et al. (2019) on q qubits
from functools import reduce
H = np.array([[1, 1], [1, -1]]) / np.sqrt(2)

def zz_state(x, reps=2):
    q = len(x)
    bits = (np.arange(2**q)[:, None] >> np.arange(q)[::-1]) & 1
    z = 1 - 2 * bits                                           # eigenvalues of Z on each qubit: +1 or -1
    phase = z @ x                                              # sum_i x_i Z_i
    for i in range(q):
        for j in range(i + 1, q):
            phase = phase + (np.pi - x[i]) * (np.pi - x[j]) * z[:, i] * z[:, j]   # the ZZ couplings
    Hq = reduce(np.kron, [H] * q)
    psi = np.zeros(2**q); psi[0] = 1
    for _ in range(reps):
        psi = np.exp(1j * phase) * (Hq @ psi)                  # layer: Hadamards, then diagonal phases
    return psi

def quantum_kernel(A, B):
    SA, SB = np.array([zz_state(a) for a in A]), np.array([zz_state(b) for b in B])
    return np.abs(SA.conj() @ SB.T) ** 2                       # k(x, z) = |<phi(x)|phi(z)>|^2

from sklearn.decomposition import PCA
print('qubits   quantum test acc.   RBF test acc.   spread of off-diagonal kernel values')
for q in [2, 4, 6, 8]:
    pca = PCA(q).fit(Ztr)
    P_tr, P_te = pca.transform(Ztr), pca.transform(Zte)
    lo, hi = P_tr.min(0), P_tr.max(0)
    A_tr = (P_tr - lo) / (hi - lo) * np.pi                     # scale features to [0, pi]
    A_te = np.clip((P_te - lo) / (hi - lo), 0, 1) * np.pi
    Ktr, Kte = quantum_kernel(A_tr, A_tr), quantum_kernel(A_te, A_tr)
    qsvm = SVC(kernel='precomputed', C=10).fit(Ktr, ytr)
    rbf = SVC(kernel='rbf', C=10).fit(A_tr, ytr)
    off = Ktr[~np.eye(len(Ktr), dtype=bool)]
    print(f'{q:6d}   {qsvm.score(Kte, yte):17.3f}   {rbf.score(A_te, yte):13.3f}   {off.std():.4f}')
qubits   quantum test acc.   RBF test acc.   spread of off-diagonal kernel values
     2               0.836           0.924   0.2746
     4               0.749           0.936   0.0804
     6               0.696           0.947   0.0210
     8               0.667           0.947   0.0068

On two qubits the quantum kernel gets 83.6% against 92.4% for an RBF kernel on the same inputs, and adding qubits makes it worse, not better. The last column shows why. The standard deviation of the off-diagonal kernel values falls from 0.27 to 0.007 as \(q\) goes from 2 to 8: in a space of dimension \(2^q\), random-looking states are nearly orthogonal, so every pair of patients looks equally dissimilar and the Gram matrix approaches the identity. On real hardware each entry would be estimated from measurement shots, and resolving differences of 0.007 needs tens of thousands of shots per entry.

quantum — a quantum model is a kernel method

Schuld (2021) observed that most supervised quantum models, which encode data with a circuit and then measure an observable, are linear models in the feature space \(\rho(x)\), and hence kernel methods: by the representer theorem, the best such model is a kernel machine with the quantum kernel. The question becomes when a quantum kernel is both hard to compute classically and useful. Liu, Arunachalam and Temme (2021) proved a rigorous advantage for a kernel built around the discrete logarithm, a problem believed to be classically hard. Huang et al. (2021) showed that, given data, classical learners can often match quantum kernels, and proposed a test for when they cannot. Thanasilp et al. (2024) proved that many feature maps suffer exactly the exponential concentration seen above, making them untrainable at scale. Quantum kernels are an active research area precisely because the classical theory of this lecture says what would have to be true for them to help.

causal — kernels as independence tests

Causal discovery (Lecture 20) needs tests of whether two variables are independent, or independent given a third, without assuming linear relationships. Kernels supply them. The Hilbert–Schmidt independence criterion (Gretton et al., 2005) is the squared norm of the cross-covariance between the RKHS features of \(X\) and \(Y\); with a characteristic kernel such as the RBF, it is zero if and only if \(X\) and \(Y\) are independent, so it detects nonlinear dependence that correlation misses. The kernel conditional independence test of Zhang et al. (2011) extends this and is a standard choice inside the PC algorithm. In treatment-effect estimation, kernel balancing chooses weights that make the treated and control groups' kernel mean embeddings match, a nonlinear version of the covariate balance checks of Lecture 4.

big picture — where kernels live today

Deep networks displaced SVMs on images, speech and text, but kernels remain the method of choice when data are small and structured. Computational biology classifies protein sequences with string kernels (Leslie, Eskin and Noble, 2002) and molecules with graph kernels. Gaussian processes are the standard surrogate model in Bayesian optimisation, in geostatistics (where they are called kriging), and as fast emulators of expensive climate and engineering simulations. Kernel two-sample tests based on the maximum mean discrepancy check whether a generative model's samples match real data and detect dataset shift. And the theory of deep learning still speaks in kernels: NTK analyses, the random-feature models behind double descent, and the "kernel regime" against "feature learning regime" distinction appear throughout current papers.

9 — Summary, exercises, projects, reading

summary

Next: Lecture 8 turns to a very different way of building flexible models: decision trees, which split feature space into boxes, and the forests and boosted ensembles that make them the strongest methods for tabular data.

exercises 7
  1. Find the hard-margin SVM for the two points \(x_1=(1,1)\), \(y_1=+1\) and \(x_2=(-1,-1)\), \(y_2=-1\), and check that the street width is the distance between them.

    By symmetry \(b=0\) and \(w=c(1,1)\). Both constraints read \(2c\ge1\), so the smallest \(\|w\|\) has \(c=\tfrac12\), \(w=(\tfrac12,\tfrac12)\), \(\|w\|=1/\sqrt2\), width \(2\sqrt2\), which is \(\|x_1-x_2\|\). In the dual, \(\sum\alpha_iy_i=0\) forces \(\alpha_1=\alpha_2=\alpha\), and \(w=\alpha x_1-\alpha x_2=2\alpha(1,1)\), so \(\alpha=\tfrac14\).

  2. Show that at the hard-margin optimum \(\sum_i\alpha_i=\|w\|^2\), so the street width is \(2/\sqrt{\sum_i\alpha_i}\). Check with Exercise 1.

    Complementary slackness gives \(\alpha_iy_i(w^\top x_i+b)=\alpha_i\) for every \(i\). Summing, \(w^\top\sum_i\alpha_iy_ix_i+b\sum_i\alpha_iy_i=\sum_i\alpha_i\), and the left side is \(w^\top w+0\). In Exercise 1, \(\sum\alpha_i=\tfrac12=\|w\|^2\).

  3. Show that the number of monomials of degree at most \(d\) in \(p\) variables is \(\binom{p+d}d\).

    A monomial of degree at most \(d\) is a multiset of size exactly \(d\) drawn from the \(p\) variables plus a dummy symbol "1" (padding up to degree \(d\)). Multisets of size \(d\) from \(p+1\) symbols number \(\binom{p+1+d-1}d=\binom{p+d}d\) (stars and bars).

  4. Show directly from Proposition 7.8 that \(\exp(-\gamma\|x-z\|^2)\) is a kernel for \(\gamma>0\), and that \(\exp(-\gamma\|x-z\|^2)\,(x^\top z+1)^2\) is too.

    \(2\gamma x^\top z\) is a kernel (scaled linear kernel), so is its exponential, and multiplying by \(f(x)f(z)\) with \(f(x)=e^{-\gamma\|x\|^2}\) gives the RBF kernel. The second is a product of two kernels.

  5. Show that \(k(s,t)=\min(s,t)\) on \([0,\infty)\) is a kernel by finding a feature map into a space of functions. (It is the covariance of Brownian motion.)

    Take \(\varphi(s)=\mathbb 1_{[0,s]}\in L^2[0,\infty)\). Then \(\langle\varphi(s),\varphi(t)\rangle=\int_0^\infty\mathbb 1[u\le s]\mathbb 1[u\le t]\,du=\min(s,t)\).

  6. Prove the "push-through" identity, for \(\lambda>0\), $$(X^\top X+\lambda I)^{-1}X^\top=X^\top(XX^\top+\lambda I)^{-1},$$ and explain why it lets ridge regression with \(p\gg n\) features be solved with an \(n\times n\) system.

    \(X^\top(XX^\top+\lambda I)=(X^\top X+\lambda I)X^\top\); multiply on the left by \((X^\top X+\lambda I)^{-1}\) and on the right by \((XX^\top+\lambda I)^{-1}\). The left form inverts a \(p\times p\) matrix, the right an \(n\times n\) one; kernel ridge regression always uses the right form.

  7. A GP with \(k(x,x)=1\) observes a single value \(y\) at \(x\) with noise variance \(\sigma^2\). Find the posterior mean and variance of \(f(x)\).

    Mean \(\frac1{1+\sigma^2}y\), variance \(1-\frac1{1+\sigma^2}=\frac{\sigma^2}{1+\sigma^2}\). With \(\sigma^2=1\) the posterior splits the difference between prior mean 0 and observation \(y\), and the variance halves: two equally reliable sources of information.

  8. Show that a GP with the linear kernel \(k(x,z)=\tau^2x^\top z\) is Bayesian linear regression with prior \(w\sim\mathcal N(0,\tau^2I)\), and that its posterior mean is the ridge estimate of Lecture 3 with \(\lambda=\sigma^2/\tau^2\).

    If \(f(x)=w^\top x\) with \(w\sim\mathcal N(0,\tau^2I)\), then \(\operatorname{Cov}(f(x),f(z))=\tau^2x^\top z\), so \(f\) is this GP. Theorem 7.13 gives mean \(\tau^2x^\top X^\top(\tau^2XX^\top+\sigma^2I)^{-1}y=x^\top(X^\top X+\tfrac{\sigma^2}{\tau^2}I)^{-1}X^\top y\) by the push-through identity: ridge with \(\lambda=\sigma^2/\tau^2\), as in Theorem 3.7.

  9. In the RBF widget, set \(\gamma=50\), \(C=100\) and then \(\gamma=0.1\), \(C=0.1\). Describe each boundary and explain the training and test accuracies in terms of bias and variance.

    \(\gamma=50\): tiny bumps around individual points, 100% training accuracy, 93 support vectors, test accuracy 91.5%: low bias, high variance. \(\gamma=0.1\), \(C=0.1\): a nearly straight boundary that cannot follow the moons' curves, so both accuracies are mediocre: high bias, low variance. The best settings sit between.

  10. A quantum kernel's off-diagonal entries have standard deviation 0.007. Each entry is estimated by repeating the circuit \(N\) times and counting how often the all-zero outcome appears, a binomial proportion. Roughly how large must \(N\) be for the sampling error to be smaller than 0.007, if the entries are around 0.01?

    The standard error of a proportion near \(p=0.01\) is \(\sqrt{p(1-p)/N}\approx0.0995/\sqrt N\). Setting this to 0.007 gives \(N\approx(0.0995/0.007)^2\approx200\) for one standard error; to resolve the differences reliably (say, an error a tenth of the spread) needs about \(2\times10^4\) shots per entry, and a Gram matrix on 400 points has 80,000 distinct entries.

student projects

Each project uses this lecture's methods and public data, and has a clear result.

1. Air-quality maps with honest uncertainty

question
How well can Gaussian-process interpolation map fine particulate matter (PM2.5) across New York City from a limited set of monitors, and are its uncertainty bands trustworthy?
data
The NYC Community Air Survey (NYC Department of Health, on NYC Open Data), annual averages at about 60–100 street-level monitors, with land-use covariates (traffic density, building emissions).
method
GP regression with RBF, Matérn and additive kernels, with and without covariates in the mean; leave-one-monitor-out cross-validation of both accuracy and the coverage of 95% intervals; compare with kriging as used by the survey.
outcome
A validated map with honest uncertainty, and a comparison of kernels that shows which spatial assumptions the data support.

2. Quantum against classical kernels, fairly

question
On small classical benchmarks, does any simulated quantum feature map beat a well-tuned classical kernel, once both are tuned with the same budget?
data
Small OpenML or UCI classification datasets (a few hundred rows, up to 20 features), as in the benchmark of Bowles, Ahmed and Schuld (2024).
method
Simulate several feature maps (ZZ, IQP-style, with bandwidth scaling of the inputs) exactly for up to 12 qubits; tune RBF and polynomial baselines equally; measure accuracy and kernel concentration; add the geometric difference test of Huang et al. (2021).
outcome
A careful comparison that can stand as a publishable result either way; well-executed negative results on quantum advantage are actively sought.

3. Forecasting with honest uncertainty

question
Which kernels give GP forecasts of the Keeling curve, or of NOAA global temperature, whose 95% bands actually cover 95% of later observations?
data
Mauna Loa monthly CO₂ (this lecture) and NOAA's global surface temperature anomalies, using rolling forecast origins from 1990 onward.
method
Composite kernels with RBF, linear, polynomial and accelerating trends; marginal-likelihood fitting versus cross-validated hyperparameters; coverage and interval-score evaluation at horizons of 1, 5 and 10 years.
outcome
A clear account of how kernel choice drives long-range forecast uncertainty, directly useful for teaching and for climate communication.

Reading and sources

Data. Breast cancer: W. N. Street, W. H. Wolberg, O. L. Mangasarian (1993), UCI Machine Learning Repository, via scikit-learn. Crash-helmet data: B. W. Silverman, "Some aspects of the spline smoothing approach to non-parametric regression curve fitting", JRSS B 47(1), 1–52 (1985), as MASS::mcycle via Rdatasets. CO₂: Dr. Pieter Tans, NOAA Global Monitoring Laboratory, and Dr. Ralph Keeling, Scripps Institution of Oceanography, monthly Mauna Loa record, via github.com/datasets/co2-ppm (ODC-PDDL). Two moons: scikit-learn's make_moons generator.

every number in the text and widgets is computed in verify_L07.py; code-box outputs are pasted from actual runs