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
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.
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.
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\|\).
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)\).
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.
An SVM in the plane has \(w=(3,4)\). How wide is its street?
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.
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.
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\)
At the optimum, a constraint that holds with strict inequality, \(g_i(x^*)<0\), has multiplier , and removing that constraint would .
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.$$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.
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.
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.
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?
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.
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\).
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)\).
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.
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:
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.
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.)
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.
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\).
\(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.
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.
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\)
# 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.
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.
Which of these is not a positive semi-definite kernel on \(\mathbb R\)?
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.
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.
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\).
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\).
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$$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?
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.
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.
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.
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.
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.
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.
In GP regression with noise variance \(\sigma^2>0\), what is true of the posterior mean at a training input \(x_i\)?
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.
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.
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)\).
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\)
# 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 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)\).
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.
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.
# 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.
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 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.
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.
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.
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\).
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\).
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).
\(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.
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)\).
\(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.
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.
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.
\(\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.
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.
Each project uses this lecture's methods and public data, and has a clear result.
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