4. Kernels, Gaussian Processes, and Conformal Prediction

Previous: linear classifiers and SVMs · Course overview

Source: Lectures 17-23, pp. 63-90.

Part 3 showed that an SVM can work entirely through feature-space inner products. This part asks which functions represent such inner products, how they define spaces of predictors, and how the same kernels describe random functions. The course ends by calibrating prediction sets.

1. Kernels and their basic constructions

Lecture 17; pp. 63-65.

A real function $K:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ is a positive semidefinite kernel if, for every finite collection $x_1,\dots ,x_m$, its Gram matrix

$$G_{ij}=K(x_i,x_j)$$

is symmetric and positive semidefinite: $c^{\top }Gc\ge 0$ for every $c\in {\mathbb{R}}^m$. The requirement concerns every finite collection, not just the current training sample.

Inner products define kernels

If $K(x,z)=⟨\Phi (x),\Phi (z){⟩}_{\mathcal{H}}$, symmetry follows from the inner product. Moreover,

$$\begin{array}{rl}{c}^{\top }Gc& =\sum _{i,j}{c}_i{c}_j⟨\Phi (x_i),\Phi (x_j){⟩}_{\mathcal{H}}\\ & ={⟨\sum _i{c}_i\Phi (x_i),\sum _j{c}_j\Phi (x_j)⟩}_{\mathcal{H}}\\ & ={\Vert \sum _i{c}_i\Phi (x_i)\Vert }_{\mathcal{H}}^2\ge 0.\end{array}$$

Thus every feature map supplies a valid kernel.

Closure properties

The lecture uses several ways to construct new kernels.

Nonnegative sums. If $K_1,K_2$ are kernels and $a_1,a_2\ge 0$, then $a_1{K}_1+a_2{K}_2$ is a kernel because

$$c^{\top }(a_1{G}_1+a_2{G}_2)c=a_1{c}^{\top }{G}_{1}c+a_2{c}^{\top }{G}_{2}c\ge 0.$$

Scaling by a function. For any real function $a$, the kernel $\tilde{K}(x,z)=a(x)a(z)K(x,z)$ has Gram matrix $DGD$, where $D_{ii}=a(x_i)$. Its quadratic form is $(Dc{)}^{\top }G(Dc)\ge 0$.

Products. $K_1(x,z)K_2(x,z)$ is also a kernel. On any finite sample, factor $G_1,G_2$ as Gram matrices of vectors $u_i,v_i$. Then

$$(G_1{)}_{ij}(G_2{)}_{ij}=\sum _{a,b}(u_{ia}{v}_{ib})(u_{ja}{v}_{jb}),$$

which is itself a Gram matrix. This is the positive-semidefinite property of the entrywise product.

Pointwise limits. A finite pointwise limit of kernels is a kernel: each finite quadratic form is the limit of nonnegative quadratic forms.

Polynomial, exponential, and Gaussian examples

Start with $K(x,z)=x^{\top }z$. Products and nonnegative sums show that

$$(x^{\top }z{)}^m,\sum _{m=0}^M{a}_m(x^{\top }z{)}^m(a_m\ge 0)$$

are kernels. Taking the limit of Taylor polynomials gives

$$e^{x^{\top }z}=\sum _{m=0}^{\infty }\frac{(x^{\top }z{)}^m}{m!}.$$

Now expand the squared distance:

$$\Vert x-z{\Vert }^2=\Vert x{\Vert }^2-2x^{\top }z+\Vert z{\Vert }^2.$$

For $\ell >0$,

$$e^{-\Vert x-z{\Vert }^2/(2{\ell }^2)}=e^{-\Vert x{\Vert }^2/(2{\ell }^2)}{e}^{-\Vert z{\Vert }^2/(2{\ell }^2)}{e}^{x^{\top }z/{\ell }^2}.$$

The last factor is an exponential inner-product kernel, and the first two implement scaling by a function. This proves that the Gaussian/RBF kernel is valid.

2. Hilbert spaces and continuous evaluation

Lecture 18; pp. 66-68.

A Hilbert space is an inner-product vector space complete in its induced norm: every Cauchy sequence converges to an element of the space. Its inner product gives

$$\Vert u{\Vert }_{\mathcal{H}}=\sqrt{⟨u,u{⟩}_{\mathcal{H}}},|⟨u,v{⟩}_{\mathcal{H}}|\le \Vert u{\Vert }_{\mathcal{H}}\Vert v{\Vert }_{\mathcal{H}}.$$

The second inequality is Cauchy-Schwarz.

The lecture examples are:

• ${\mathbb{R}}^m$, with $⟨u,v⟩={\sum }_i{u}_i{v}_i$.
• ${\ell }^2$, the sequences with ${\sum }_i{u}_i^2<\infty$, using the same infinite-sum inner product.
• $L^2$, square-integrable functions with $⟨f,g⟩=\int fg$. Its elements are equivalence classes up to equality almost everywhere.

A linear functional $L:\mathcal{H}\to \mathbb{R}$ is continuous exactly when $|L(f)|\le C\Vert f{\Vert }_{\mathcal{H}}$ for some finite $C$. Inner products with a fixed $g$ are continuous by Cauchy-Schwarz.

The Riesz representation theorem, stated in the lecture, says the converse: every continuous linear functional has a unique representation $L(f)=⟨f,g{⟩}_{\mathcal{H}}$.

The reproducing property

An RKHS is a Hilbert space of actual functions on $\mathcal{X}$ for which evaluation $L_x(f)=f(x)$ is continuous for every $x$.

Riesz then gives an element $K_x\in \mathcal{H}$ satisfying

$$f(x)=⟨f,K_x{⟩}_{\mathcal{H}}.$$

Take $f=K_z$ to get $K_z(x)=⟨K_z,K_x{⟩}_{\mathcal{H}}$. Define

$$K(x,z)=⟨K_x,K_z{⟩}_{\mathcal{H}}.$$

It is a kernel by the inner-product calculation above, and $K_x=K(\cdot ,x)$. Therefore

$$f(x)=⟨f,K(\cdot ,x){⟩}_{\mathcal{H}}.$$

The kernel “reproduces” evaluation. In particular,

$$|f(x)|\le \Vert f{\Vert }_{\mathcal{H}}\sqrt{K(x,x)}.$$

This is the link between controlling a function’s RKHS norm and controlling its predictions. Ordinary $L^2$ need not be an RKHS: changing a function at one point does not change its $L^2$ element, so point evaluation is not generally well-defined.

3. From a kernel back to its RKHS

Lectures 18-19; pp. 68-71.

The Moore-Aronszajn theorem states that every positive semidefinite kernel determines a unique RKHS with that reproducing kernel.

Start from finite linear combinations

$$f=\sum _i{a}_{i}K(\cdot ,x_i),g=\sum _j{b}_{j}K(\cdot ,z_j),$$

and define

$$⟨f,g⟩=\sum _{i,j}{a}_i{b}_{j}K(x_i,z_j).$$

Positive semidefiniteness makes squared norms nonnegative. Identify any zero-norm representations, then complete this inner-product space. Evaluation is bounded because

$$|f(x)|=|⟨f,K(\cdot ,x)⟩|\le \Vert f\Vert \sqrt{K(x,x)},$$

so it extends continuously to the completion. This produces the RKHS.

This construction makes precise the infinite-sum notation in the PDF: membership and convergence are governed by the RKHS norm. An arbitrary formal infinite sum is not automatically a member.

Example 1: the Gaussian kernel

For $K(x,z)=e^{-\Vert x-z{\Vert }^2}$, each Gaussian bump $K(\cdot ,x_i)$ lies in the RKHS, as does any finite sum. For example,

$$f(\cdot )=K(\cdot ,x_1)+2K(\cdot ,x_2)$$

has squared norm

$$\Vert f{\Vert }_{\mathcal{H}}^2=K(x_1,x_1)+4K(x_1,x_2)+4K(x_2,x_2).$$

The coefficients and pairwise kernel values determine its norm.

Example 2: derive the kernel $\min (s,t)$

Consider absolutely continuous functions on $[0,1]$ with $f(0)=0$ and $f^{\prime }\in L^2[0,1]$, with

$$⟨f,g{⟩}_{\mathcal{H}}={\int }_0^1{f}^{\prime }(t)g^{\prime }(t)dt.$$

The derivative map identifies this space with $L^2$, so it is complete. Also

$$|f(x)|=\left|{\int }_0^x{f}^{\prime }(t)dt\right|\le \sqrt{x}{\left({\int }_0^x|f^{\prime }(t){|}^{2}dt\right)}^{1/2}\le \Vert f{\Vert }_{\mathcal{H}}.$$

Thus evaluation is continuous. To find its representer, rewrite

$$f(x)={\int }_0^1{f}^{\prime }(t)1_{[0,x]}(t)dt.$$

We need ${\partial }_{t}K(t,x)=1_{[0,x]}(t)$ almost everywhere and $K(0,x)=0$. Integrating,

$$K(t,x)={\int }_0^t{1}_{[0,x]}(s)ds=\min (t,x).$$

Substituting its derivative into the inner product verifies the reproducing identity.

4. Regularized ERM and the representer theorem

Lectures 19-20; pp. 71-74.

Let $\mathcal{H}$ be the RKHS of $K$. Consider

$$\underset{f\in \mathcal{H}}{\min }\frac{1}{n}\sum _i\ell (f(X_i),Y_i)+\lambda \Vert f{\Vert }_{\mathcal{H}}^2,\lambda >0.$$

The PDF uses summed loss plus $C\Vert f{\Vert }^2$; dividing its objective by $n$ gives $\lambda =C/n$. This $C$ multiplies the norm, unlike the soft-margin convention in Part 3 where $C$ multiplies the loss.

Since $f(X_i)=⟨f,K(\cdot ,X_i){⟩}_{\mathcal{H}}$, squared-loss fitting is ridge regression on the canonical features $\Phi (X_i)=K(\cdot ,X_i)$. But $\mathcal{H}$ may be infinite-dimensional.

Representer theorem and proof

If a minimizer exists, every minimizer has the form

$$\hat{f}(x)=\sum _{i=1}^n{a}_{i}K(x,X_i).$$

Let $S=\mathrm{span}\{K(\cdot ,X_1),\dots ,K(\cdot ,X_n)\}$ and decompose

$$f=f_S+f_{\perp },f_S\in S,f_{\perp }\perp S.$$

Because $K(\cdot ,X_i)\in S$,

$$f_{\perp }(X_i)=⟨f_{\perp },K(\cdot ,X_i){⟩}_{\mathcal{H}}=0.$$

Therefore $f(X_i)=f_S(X_i)$ for every training input: their empirical losses are identical. Pythagoras gives

$$\Vert f{\Vert }_{\mathcal{H}}^2=\Vert f_S{\Vert }_{\mathcal{H}}^2+\Vert f_{\perp }{\Vert }_{\mathcal{H}}^2.$$

If $f_{\perp }\ne 0$, removing it strictly reduces the penalty because $\lambda >0$. Hence no minimizer can have a nonzero perpendicular component, proving the theorem. This argument does not require convex loss, though convexity helps solve the resulting problem.

The finite coefficient problem

Set $G_{ij}=K(X_i,X_j)$ and $a=(a_1,\dots ,a_n{)}^{\top }$. Then

$$\begin{array}{rl}(\hat{f}(X_1),\dots ,\hat{f}(X_n){)}^{\top }& =Ga,\\ \Vert \hat{f}{\Vert }_{\mathcal{H}}^2& =\sum _{i,j}{a}_i{a}_j⟨K(\cdot ,X_i),K(\cdot ,X_j){⟩}_{\mathcal{H}}\\ & =a^{\top }Ga.\end{array}$$

The optimization therefore becomes

$$\underset{a\in {\mathbb{R}}^n}{\min }\frac{1}{n}\sum _i\ell ((Ga{)}_i,Y_i)+\lambda a^{\top }Ga.$$

Infinite-dimensional learning has reduced to at most $n$ coefficients.

5. Kernel regression and classification losses

Lectures 19-20; pp. 73-76.

Kernel ridge regression

For squared loss, minimize

$$J(a)=\frac{1}{n}\Vert Ga-y{\Vert }^2+\lambda a^{\top }Ga.$$

Since $G$ is symmetric,

$$\nabla J(a)=\frac{2}{n}G(Ga-y)+2\lambda Ga.$$

Setting the gradient to zero gives

$$G[(G+n\lambda I)a-y]=0.$$

A solution is obtained by solving the linear system

$$(G+n\lambda I)a=y.$$

This matrix is positive definite: for $v\ne 0$,

$$v^{\top }(G+n\lambda I)v=v^{\top }Gv+n\lambda \Vert v{\Vert }^2>0.$$

Thus $a=(G+n\lambda I{)}^{-1}y$ is valid even if $G$ is singular. It satisfies the stationarity equation, and convexity makes it optimal. Predict using $\hat{f}(x)={\sum }_i{a}_{i}K(x,X_i)$.

Clarification of p. 73: the formula $(G^2+CG{)}^{-1}Gy$ given there assumes invertible $G$ and simplifies to $(G+CI{)}^{-1}y$. The latter remains valid for singular $G$. Coefficients can then have additional null-space representations, but the fitted RKHS function is unique.

Quantile regression

For $\tau \in (0,1)$, define the pinball loss

$${\ell }_{\tau }(u)=\{\begin{array}{ll}(\tau -1)u,& u<0,\\ \tau u,& u\ge 0.\end{array}$$

Why does it estimate a quantile? For fixed $x$, consider $Q(a)=\mathbb{E}[{\ell }_{\tau }(Y-a)\mid X=x]$, assuming integrability. For $Y<a$, the derivative with respect to $a$ is $1-\tau$; for $Y>a$, it is $-\tau$. At continuity points of the conditional distribution,

$$Q^{\prime }(a)=(1-\tau )\mathrm{Pr}(Y<a\mid x)-\tau \mathrm{Pr}(Y>a\mid x)=F_{Y\mid x}(a)-\tau .$$

Thus the minimum occurs at the conditional $\tau$-quantile. With atoms, the subgradient condition becomes $F_{Y\mid x}(a-)\le \tau \le F_{Y\mid x}(a)$.

Its regularized sample version is

$$\underset{f\in \mathcal{H}}{\min }\frac{1}{n}\sum _i{\ell }_{\tau }(Y_i-f(X_i))+\lambda \Vert f{\Vert }_{\mathcal{H}}^2.$$

The representer theorem applies as before.

Kernel logistic regression

For $Y_i\in \{-1,1\}$, use

$$\ell (s,Y_i)=-\log \frac{e^{Y_{i}s}}{1+e^{Y_{i}s}}=\log (1+e^{-Y_{i}s}).$$

Minimize the regularized objective to obtain a real score $\hat{f}(x)$. Convert it to a hard prediction by its sign, or report the model probability

$$\hat{p}(x)=\frac{e^{\hat{f}(x)}}{1+e^{\hat{f}(x)}}.$$

The lecture also describes drawing a random class using this probability. That is a randomized prediction rule, distinct from reporting the probability or thresholding it.

Kernel hinge loss and SVMs

For $\ell (s,y)=\max \{0,1-ys\}$, regularized ERM becomes

$$\underset{f\in \mathcal{H}}{\min }\frac{1}{n}\sum _i\max \{0,1-Y_{i}f(X_i)\}+\lambda \Vert f{\Vert }_{\mathcal{H}}^2.$$

Multiplying by $1/(2\lambda )$ gives norm penalty $\Vert f{\Vert }^2/2$ and loss coefficient $C=1/(2n\lambda )$, matching the soft-margin formulation. An unpenalized intercept can be added to match Part 3 exactly.

Squared, quantile, logistic, and hinge losses are convex in the score. Since $Ga$ is linear in $a$ and $G$ is positive semidefinite, all these coefficient problems are convex.

6. Stationary kernels and Bochner’s theorem

Lecture 20; pp. 76-77.

A stationary kernel depends only on displacement:

$$K(x,z)=h(x-z).$$

For a random frequency vector $\omega$, its characteristic function is

$${\phi }_{\omega }(u)=\mathbb{E}[e^{i{\omega }^{\top }u}].$$

If $\omega$ and $-\omega$ have the same distribution, the imaginary sine terms cancel, giving ${\phi }_{\omega }(u)=\mathbb{E}\cos ({\omega }^{\top }u)$.

To see positive semidefiniteness, for real coefficients $c_i$,

$$\begin{array}{rl}\sum _{i,j}{c}_i{c}_j{\phi }_{\omega }(x_i-x_j)& =\mathbb{E}\sum _{i,j}{c}_i{c}_j{e}^{i{\omega }^{\top }{x}_i}{e}^{-i{\omega }^{\top }{x}_j}\\ & =\mathbb{E}{\left|\sum _i{c}_i{e}^{i{\omega }^{\top }{x}_i}\right|}^2\ge 0.\end{array}$$

Bochner’s theorem gives the converse for continuous stationary positive semidefinite kernels: each nonzero real such kernel can be written

$$K(x,z)=A\mathbb{E}\cos ({\omega }^{\top }(x-z)),A=K(0,0)>0,$$

for a symmetric frequency distribution. The zero kernel is the trivial separate case. Continuity is needed in this statement.

The lecture’s examples

The rational quadratic family is

$$K(x,z)={\left(1+\frac{\Vert x-z{\Vert }^2}{\alpha {\ell }^2}\right)}^{-\alpha },\alpha ,\ell >0.$$

For $r=\Vert x-z{\Vert }^2/{\ell }^2$, take logarithms: $-\alpha \log (1+r/\alpha )\to -r$. Hence this family approaches $e^{-\Vert x-z{\Vert }^2/{\ell }^2}$ as $\alpha \to \infty$.

Another family is

$$K(x,z)=\exp \left(-\frac{\Vert x-z{\Vert }^{\gamma }}{{\ell }^{\gamma }}\right),0<\gamma \le 2.$$

At $\gamma =2$ it is Gaussian; at $\gamma =1$ it is exponential, corresponding to a Cauchy-type spectral distribution. The PDF also points to the Matérn family as further kernel examples, without deriving its formula.

7. Gaussian processes and covariance kernels

Lecture 21; pp. 78-81.

A Gaussian process is a collection of random variables indexed by inputs, $\{Z(x):x\in \mathcal{X}\}$, such that every finite collection is jointly Gaussian. For a zero-mean process with covariance function $K$,

$$(Z(x_1),\dots ,Z(x_m){)}^{\top }\sim \mathcal{N}(0,G),G_{ij}=K(x_i,x_j).$$

A sample is therefore a random function. The covariance describes how its values vary together across inputs.

Covariance functions are kernels. Symmetry is immediate, and

$$\sum _{i,j}{c}_i{c}_{j}K(x_i,x_j)=\mathrm{Var}\left(\sum _i{c}_{i}Z(x_i)\right)\ge 0.$$

Conversely, a positive semidefinite kernel defines compatible Gaussian distributions on finite input sets, and hence a Gaussian process. The lectures develop a spectral construction to explain how to sample one.

8. Mercer expansion: the spectral view of a kernel

Lecture 21; pp. 79-80.

Take a bounded continuous kernel on ${\mathbb{R}}^d$ and a strictly positive probability density $p$. Define an integral operator on $L^2(p)$:

$$(Tf)(x)=\int K(x,z)f(z)p(z)dz.$$

This generalizes matrix-vector multiplication: the sum over a matrix column becomes an integral over $z$. It is an integral operator, not generally a convolution.

The operator is bounded

If $|K(x,z)|\le M$, Cauchy-Schwarz gives

$$|(Tf)(x){|}^2\le \left(\int K(x,z{)}^{2}p(z)dz\right)\left(\int f(z{)}^{2}p(z)dz\right)\le M^2\Vert f{\Vert }_{L^2(p)}^2.$$

Integrating over $x$ and using $\int p=1$ yields

$$\Vert Tf{\Vert }_{L^2(p)}\le M\Vert f{\Vert }_{L^2(p)}.$$

Symmetry of $K$ makes $T$ self-adjoint; positive semidefiniteness makes it positive. Square integrability of $K$ also makes it compact. These are the operator counterparts of the finite-dimensional spectral setting.

Eigenfunctions replace eigenvectors

A symmetric positive semidefinite matrix has an expansion $G={\sum }_k{\lambda }_k{u}_k{u}_k^{\top }$. The corresponding Mercer expansion is

$$T{\psi }_k={\lambda }_k{\psi }_k,⟨{\psi }_k,{\psi }_l{⟩}_{L^2(p)}={\delta }_{kl},K(x,z)=\sum _k{\lambda }_k{\psi }_k(x){\psi }_k(z).$$

The positive eigenvalues tend to zero if there are infinitely many. Zero-eigenvalue directions may be needed to complete a basis of $L^2(p)$, but contribute nothing to the kernel expansion. This avoids assuming that the positive eigenfunctions alone span the whole space.

The spectral series converges in $L^2(p\otimes p)$; the continuous representatives supplied by the Mercer setting give the pointwise kernel expansion, locally uniformly. The density $p$ determines the eigenfunctions and eigenvalues, even though the represented kernel is fixed.

Derive the coefficients

For fixed $x$, boundedness gives $K(\cdot ,x)\in L^2(p)$. Expand it in the spectral basis:

$$K(\cdot ,x)=\sum _k⟨K(\cdot ,x),{\psi }_k{⟩}_{L^2(p)}{\psi }_k(\cdot ).$$

Compute each coefficient:

$$\begin{array}{rl}⟨K(\cdot ,x),{\psi }_k{⟩}_{L^2(p)}& =\int K(z,x){\psi }_k(z)p(z)dz\\ & =(T{\psi }_k)(x)={\lambda }_k{\psi }_k(x).\end{array}$$

Substitution yields the Mercer expansion. This calculation uses the $L^2(p)$ inner product; the RKHS reproducing inner product is a different one.

The expansion also supplies an explicit feature map:

$$\Phi (x)=(\sqrt{{\lambda }_1}{\psi }_1(x),\sqrt{{\lambda }_2}{\psi }_2(x),\dots ),⟨\Phi (x),\Phi (z){⟩}_{{\ell }^2}=K(x,z).$$

9. Karhunen-Loève expansion and sampling

Lectures 21-22; pp. 80-83.

Let ${\xi }_k$ be independent $\mathcal{N}(0,1)$ variables. Define

$$Z(x)=\sum _k\sqrt{{\lambda }_k}{\xi }_k{\psi }_k(x).$$

For a finite truncation, any finite set of values is a linear transformation of independent Gaussians, so it is jointly Gaussian. Moreover,

$$\mathbb{E}{\left|\sum _{k>M}\sqrt{{\lambda }_k}{\xi }_k{\psi }_k(x)\right|}^2=\sum _{k>M}{\lambda }_k{\psi }_k(x{)}^2\to 0,$$

because the full diagonal sum equals $K(x,x)<\infty$. The finite-dimensional Gaussian vectors therefore have a mean-square limit.

The process has mean zero. Its covariance is

$$\begin{array}{rl}\mathrm{Cov}(Z(x),Z(z))& =\sum _{k,l}\sqrt{{\lambda }_k{\lambda }_l}{\psi }_k(x){\psi }_l(z)\mathbb{E}[{\xi }_k{\xi }_l]\\ & =\sum _k{\lambda }_k{\psi }_k(x){\psi }_k(z)\\ & =K(x,z).\end{array}$$

Only terms with $k=l$ survive because $\mathbb{E}[{\xi }_k{\xi }_l]={\delta }_{kl}$. This proves that the expansion produces the desired GP.

Method 1: truncate the expansion

Draw $M$ standard normals and use

$$Z_M(x)=\sum _{k=1}^M\sqrt{{\lambda }_k}{\xi }_k{\psi }_k(x).$$

The sampled function can be evaluated at any input. The cost is needing the eigenpairs and accepting the omitted spectral tail.

Method 2: sample on a finite input grid

Choose $x_1,\dots ,x_m$, form $G_{ij}=K(x_i,x_j)$, and sample $\mathcal{N}(0,G)$ directly. For example, if $G=U\Lambda U^{\top }$, draw $\xi \sim \mathcal{N}(0,I)$ and set

$$z=U{\Lambda }^{1/2}\xi .$$

Then $\mathbb{E}z=0$ and $\mathrm{Cov}(z)=U\Lambda U^{\top }=G$. This also works for singular $G$. If $G$ is positive definite, a Cholesky factor $G=L{L}^{\top }$ gives $z=L\xi$.

This method needs no continuous-domain eigenfunctions. It produces values at the chosen grid points; interpolation is an additional approximation.

10. Work out the eigenpairs of $\min (s,t)$

Lecture 22; pp. 83-84.

On $[0,1]$ with uniform measure,

$$(Tf)(t)={\int }_0^1\min (s,t)f(s)ds.$$

For a positive eigenvalue $\lambda$, split the eigenvalue equation at $s=t$:

$$\lambda f(t)={\int }_0^{t}sf(s)ds+t{\int }_t^{1}f(s)ds.$$

Differentiate using the fundamental theorem of calculus and the product rule:

$$\lambda f^{\prime }(t)=tf(t)+{\int }_t^{1}f(s)ds-tf(t)={\int }_t^{1}f(s)ds.$$

Differentiate again:

$$\lambda f^{\prime \prime }(t)=-f(t).$$

The original equation at $t=0$ gives $f(0)=0$, while the first derivative at $t=1$ gives $f^{\prime }(1)=0$.

Set $\omega =1/\sqrt{\lambda }$. The differential equation has solution

$$f(t)=A\sin (\omega t)+B\cos (\omega t).$$

The first boundary condition forces $B=0$. The second gives $A\omega \cos \omega =0$. A nonzero eigenfunction requires

$$\cos \omega =0⟹\omega =(k-\frac{1}{2})\pi ,k=1,2,\dots .$$

Finally,

$${\int }_0^1{\sin }^2((k-\frac{1}{2})\pi t)dt=\frac{1}{2},$$

so normalization gives

$$\boxed{{\lambda }_k=\frac{1}{(k-\frac{1}{2}{)}^2{\pi }^2},{\psi }_k(t)=\sqrt{2}\sin ((k-\frac{1}{2})\pi t).}$$

Correction to p. 84: the printed integer frequencies $k\pi$ do not satisfy $f^{\prime }(1)=0$. The half-integer frequencies above follow from the lecture’s own boundary conditions.

Substituting these eigenpairs into the preceding expansion gives a GP with covariance $\min (s,t)$, namely standard Brownian motion on $[0,1]$.

11. Why the course looks beyond fixed kernels

Lecture 22; pp. 84-85.

Kernel learning with convex losses offers tractable convex objectives. Gaussian kernels also have a universal approximation property: on compact $A\subset {\mathbb{R}}^d$, their RKHS is dense in the continuous functions under the uniform norm.

This means that for continuous $g$ and every $\epsilon >0$, some RKHS function satisfies

$$\underset{x\in A}{\sup }|f(x)-g(x)|\le \epsilon .$$

Existence says nothing by itself about how many basis functions or observations efficient learning needs.

The lecture illustrates the curse of dimensionality by the worst-case approximation scaling for a bounded smoothness class:

$$n\text{ on the order of }{\epsilon }^{-d/k}$$

for $k$ derivatives of smoothness. A grid interpretation is that local error of order $h^k$ needs $h\approx {\epsilon }^{1/k}$, while covering a $d$-dimensional region needs about $h^{-d}$ cells.

For $k=2,d=400,\epsilon =1/2$, the illustration becomes $2^{200}$. This is a worst-case approximation-complexity example, not a universal sample-size formula for every kernel or target.

Structure can change the problem. A compositional function may have the form

$$g(x_1,\dots ,x_d)=h(h(x_1,x_2),h(x_3,x_4))$$

with further pairwise composition for larger $d$. A deep network can represent that hierarchy directly, motivating the discussion of deep learning.

The PDF uses summation as a simple compositional example. Summation is also easy for a linear kernel, so this example alone does not establish a neural-network advantage. Efficiency depends on the target structure and the chosen model. Universal approximation is also distinct from universal statistical consistency.

12. Conformal prediction

Lecture 23; pp. 87-90.

So far a model predicts a value, label, or probability. We now ask for a set $C(x)$ whose coverage has a finite-sample guarantee.

Step 1: fit using training data

Use any fitting method to obtain a predictor. For classification it can output real class scores; it need not output a hard label.

Keep a separate calibration sample $({\tilde{X}}_i,{\tilde{Y}}_i{)}_{i=1}^m$. Fix both predictor and scoring rule before using it. Under the lecture’s assumption, training, calibration, and future test pairs are i.i.d.

Step 2: define a nonconformity score

Choose $s(x,y)$ to be larger when outcome $y$ agrees less with the prediction. The lecture examples are:

$$\begin{array}{ll}\text{Binary, }y\in \{-1,1\}:& s(x,y)=e^{-yf(x)},\\ \text{Multiclass, scores }{f}_j(x):& s(x,y)=e^{-f_y(x)}.\end{array}$$

For a strongly positive binary score, label $+1$ has a small nonconformity score and label $-1$ has a large one. The score need not be a calibrated probability.

Step 3: calibrate a threshold

Compute $s_i=s({\tilde{X}}_i,{\tilde{Y}}_i)$ and sort

$$s_{(1)}\le \cdots \le s_{(m)}.$$

For target error level $\alpha \in (0,1)$, define

$$k=\lceil (m+1)(1-\alpha )\rceil ,q=\{\begin{array}{ll}{s}_{(k)},& k\le m,\\ +\infty ,& k=m+1.\end{array}$$

The $m+1$ adjustment accounts for the future score as one more exchangeable observation. The infinite-threshold case completes the definition when the requested coverage exceeds what a finite calibration quantile can supply.

For $m=99$ and $\alpha =0.1$, $k=90$, so use the 90th smallest calibration score.

Step 4: invert the score

Output

$$C(x)=\{y:s(x,y)\le q\}.$$

In classification, test each candidate class against the same threshold. Depending on scores, the set can be empty, contain one label, or contain several. Larger sets express less decisive predictions.

Regression with estimated quantiles

Fit lower and upper quantile functions $L(x),U(x)$, for example at levels $0.25$ and $0.75$ as in the PDF. Assume the initial bounds are ordered. Define

$$s(x,y)=\max \{L(x)-y,y-U(x),0\}.$$

Because these scores are nonnegative, the calibrated $q$ is nonnegative. The condition $s(x,y)\le q$ is equivalent to the three inequalities

$$L(x)-y\le q,y-U(x)\le q,0\le q.$$

Rearranging the first two yields

$$C(x)=[L(x)-q,U(x)+q].$$

Calibration therefore expands the initial interval by a common amount sufficient for the desired marginal coverage.

Derive the coverage guarantee

Condition on the fitted predictor and fixed score rule. The calibration scores and future true-label score

$$s_{\mathrm{new}}=s(X_{\mathrm{new}},Y_{\mathrm{new}})$$

are exchangeable. If there are no ties, the future score’s rank among all $m+1$ scores is uniform on $\{1,\dots ,m+1\}$.

For $k\le m$, $s_{\mathrm{new}}\le s_{(k)}$ exactly when that rank is at most $k$. Hence

$$\mathrm{Pr}(s_{\mathrm{new}}\le q)=\frac{k}{m+1}\ge 1-\alpha .$$

With ties, imagine random tie-breaking only for the rank argument. Every rank-at-most-$k$ event is still accepted by the rule using $\le$, so ties can only increase coverage. If $k=m+1$, the threshold is infinite and coverage is 1.

Since membership in $C(X_{\mathrm{new}})$ is precisely $s_{\mathrm{new}}\le q$,

$$\mathrm{Pr}\{Y_{\mathrm{new}}\in C(X_{\mathrm{new}})\}\ge 1-\alpha .$$

This is marginal coverage: it averages over calibration data and the new pair, conditional on model fitting under the i.i.d. setup. It is not a $1-\alpha$ guarantee for every individual input or for every fixed calibration set.

Using calibration labels to fit or tune the score breaks this simple exchangeability argument. A poor model can still obtain valid coverage by producing large sets; coverage and informativeness are separate properties.