Simple Algorithm
Artificial Intelligence · Deep Layer · 30 min

Gaussian Processes & Bayesian ML

Distributions over functions and calibrated uncertainty.

Put a Gaussian prior on the weights of a linear model and something remarkable happens: predictions never need the weights, only similarities between inputs. Replace those by a kernel and you have a Gaussian process, a prior over functions with error bars in closed form. The same object describes infinitely wide neural networks, drives Bayesian optimization and sets the standard for calibrated uncertainty, at a price of O(n3)\order{n^3}.

What you’ll learn

  • Derive Bayesian linear regression, show that its predictions depend on the inputs only through a kernel, and recover ridge regression as its posterior mean.
  • Define Gaussian processes and derive the posterior mean and variance by Gaussian conditioning, with the Cholesky algorithm and its cost.
  • Choose kernels, learn hyperparameters by maximizing the marginal likelihood, and state Bochner's theorem and posterior contraction rates.
  • Explain sparse and random-feature approximations, the regret bound of GP-UCB, and the infinite-width correspondence between neural networks and Gaussian processes.

From weights to functions

DerivationBayesian linear regression
  1. w∣D∼N(wˉ,A−1),A=σ−2Φ⊤Φ+Σp−1,wˉ=σ−2A−1Φ⊤y\mathbf w\mid\data\sim\mathcal N\big(\bar{\mathbf w},A^{-1}\big),\qquad A=\sigma^{-2}\Phi^\top\Phi+\Sigma_p^{-1},\qquad \bar{\mathbf w}=\sigma^{-2}A^{-1}\Phi^\top\mathbf y

    Model f(x)=ϕ(x)⊤wf(\mathbf x)=\boldsymbol\phi(\mathbf x)^\top\mathbf w with prior w∼N(0,Σp)\mathbf w\sim\mathcal N(\mathbf 0,\Sigma_p) and observations y=Φw+ε\mathbf y=\Phi\mathbf w+\boldsymbol\varepsilon, ε∼N(0,σ2I)\boldsymbol\varepsilon\sim\mathcal N(\mathbf 0,\sigma^2I), where row ii of Φ\Phi is ϕ(xi)⊤\boldsymbol\phi(\mathbf x_i)^\top. Completing the square in w\mathbf w gives a Gaussian posterior:

  2. wˉ=(Φ⊤Φ+σ2τ2I)−1Φ⊤y\bar{\mathbf w}=\big(\Phi^\top\Phi+\tfrac{\sigma^2}{\tau^2}I\big)^{-1}\Phi^\top\mathbf y

    With Σp=τ2I\Sigma_p=\tau^2I the posterior mean is the ridge solution, with penalty λ=σ2/τ2\lambda=\sigma^2/\tau^2 on the sum of squared errors: a prior's strength is a regularization constant.

  3. ϕ∗⊤wˉ=k∗⊤(K+σ2I)−1y,Kij=k(xi,xj),k(x,x′)=ϕ(x)⊤Σp ϕ(x′)\boldsymbol\phi_*^\top\bar{\mathbf w}=\mathbf k_*^\top\big(K+\sigma^2I\big)^{-1}\mathbf y,\qquad K_{ij}=k(\mathbf x_i,\mathbf x_j),\quad k(\mathbf x,\mathbf x')=\boldsymbol\phi(\mathbf x)^\top\Sigma_p\,\boldsymbol\phi(\mathbf x')

    The prediction at x∗\mathbf x_* is ϕ∗⊤wˉ\boldsymbol\phi_*^\top\bar{\mathbf w}. A matrix identity, σ−2A−1Φ⊤=ΣpΦ⊤(ΦΣpΦ⊤+σ2I)−1\sigma^{-2}A^{-1}\Phi^\top=\Sigma_p\Phi^\top(\Phi\Sigma_p\Phi^\top+\sigma^2I)^{-1}, removes the weights entirely:

  4. f∼GP(0, k)f\sim\mathcal{GP}\big(0,\ k\big)

    Only the kernel kk remains, so the features may be infinite-dimensional as long as kk is computable: the kernel trick, applied to a Bayesian model.

The posterior in closed form

DerivationConditioning a Gaussian
  1. (yf∗)∼N(0,(K+σ2Ik∗k∗⊤k∗∗)),(k∗)i=k(xi,x∗),k∗∗=k(x∗,x∗)\begin{pmatrix}\mathbf y\\ f_*\end{pmatrix}\sim\mathcal N\left(\mathbf 0,\begin{pmatrix}K+\sigma^2I&\mathbf k_*\\ \mathbf k_*^\top&k_{**}\end{pmatrix}\right),\qquad (\mathbf k_*)_i=k(\mathbf x_i,\mathbf x_*),\quad k_{**}=k(\mathbf x_*,\mathbf x_*)

    With prior mean 00 and noisy observations yi=f(xi)+εiy_i=f(\mathbf x_i)+\varepsilon_i, the training outputs and the test value are jointly Gaussian:

  2. f∗∣y ∼ N(k∗⊤(K+σ2I)−1y,  k∗∗−k∗⊤(K+σ2I)−1k∗)f_*\mid\mathbf y\ \sim\ \mathcal N\Big(\mathbf k_*^\top(K+\sigma^2I)^{-1}\mathbf y,\ \ k_{**}-\mathbf k_*^\top(K+\sigma^2I)^{-1}\mathbf k_*\Big)

    The conditional of a jointly Gaussian vector is Gaussian, with the Schur complement as its covariance:

  3. μ(x∗)=∑i=1nαi k(xi,x∗)\mu(\mathbf x_*)=\sum_{i=1}^n\alpha_i\,k(\mathbf x_i,\mathbf x_*)

    The mean is a weighted sum of kernels centered on the data, ∑iαik(xi,x∗)\sum_i\alpha_ik(\mathbf x_i,\mathbf x_*) with α=(K+σ2I)−1y\boldsymbol\alpha=(K+\sigma^2I)^{-1}\mathbf y. The variance never involves y\mathbf y: it shrinks near the inputs and returns to the prior's k∗∗k_{**} far from them.

text
function GP-PREDICT(X, y, kernel k, noise σ², test point x*)
  L ← CHOLESKY(K + σ²I)           // K[i][j] = k(xi, xj); about n³/3 flops
  α ← Lᵀ \ (L \ y)                  // two triangular solves: O(n²)
  mean ← k*ᵀ α                      // k*[i] = k(xi, x*): O(n)
  v ← L \ k*                        // O(n²)
  var ← k(x*, x*) − vᵀ v
  logZ ← −½ yᵀα − Σi log L[i][i] − (n/2) log 2π   // log marginal likelihood
  return mean, var, logZ

Rasmussen and Williams's Algorithm 2.1. Training costs O(n3)\order{n^3} time and O(n2)\order{n^2} memory, then each prediction O(n)\order{n} for the mean and O(n2)\order{n^2} for the variance. A few tens of thousands of points are feasible exactly; millions are not.

Predict before you look

One observation, y=1y=1 at x=0x=0. The kernel is k(x,x′)=exp⁡(−(x−x′)2/2)k(x,x')=\exp\big(-(x-x')^2/2\big) and the noise variance is σ2=0.01\sigma^2=0.01. What is the posterior mean at x∗=1x_*=1?

Show the answer

0.6

μ=k(1,0) y/(1+σ2)=e−1/2/1.01≈0.601\mu=k(1,0)\,y/(1+\sigma^2)=e^{-1/2}/1.01\approx0.601. The variance there is 1−e−1/1.01≈0.641-e^{-1}/1.01\approx0.64, while at x∗=0x_*=0 it is 1−1/1.01≈0.00991-1/1.01\approx0.0099, about the noise level. Two units away the mean has decayed to e−2/1.01≈0.13e^{-2}/1.01\approx0.13.

Kernels and their hyperparameters

Kernelk(r)k(r), with r=∥x−x′∥r=\|\mathbf x-\mathbf x'\|Sample functions
Squared exponential (RBF)s2exp⁡(−r2/2ℓ2)s^2\exp\big(-r^2/2\ell^2\big)infinitely differentiable
Matérn ν=12\nu=\tfrac12s2exp⁡(−r/ℓ)s^2\exp(-r/\ell)continuous, nowhere differentiable (Ornstein–Uhlenbeck)
Matérn ν=32\nu=\tfrac32s2(1+3r/ℓ)e−3r/ℓs^2\big(1+\sqrt3r/\ell\big)e^{-\sqrt3r/\ell}once differentiable
Matérn ν=52\nu=\tfrac52s2(1+5r/ℓ+5r2/3ℓ2)e−5r/ℓs^2\big(1+\sqrt5r/\ell+5r^2/3\ell^2\big)e^{-\sqrt5r/\ell}twice differentiable
Periodic (one dimension)s2exp⁡(−2sin⁡2(πr/p)/ℓ2)s^2\exp\big(-2\sin^2(\pi r/p)/\ell^2\big)exactly periodic with period pp
Linearσb2+x⊤x′\sigma_b^2+\mathbf x^\top\mathbf x'straight lines: Bayesian linear regression
Sums and products of kernels are kernels: a sum models a function as a sum of independent parts, and a product of periodic and squared-exponential kernels gives "locally periodic". The length scale ℓ\ell sets how fast correlation decays, and the amplitude ss the function's typical size.

Hyperparameters such as ℓ\ell, ss and σ\sigma are usually fit by maximizing the log marginal likelihood, which balances fit against complexity, the same Occam's razor as Bayes factors:

log⁡p(y∣X,θ)=−12y⊤(K+σ2I)−1y⏟data fit −12log⁡det⁡(K+σ2I)⏟complexity − n2log⁡2π.\log p(\mathbf y\mid X,\boldsymbol\theta)=\underbrace{-\tfrac12\mathbf y^\top(K+\sigma^2I)^{-1}\mathbf y}_{\text{data fit}}\ \underbrace{-\tfrac12\log\det(K+\sigma^2I)}_{\text{complexity}}\ -\ \tfrac n2\log2\pi.

Its gradient is 12Tr⁡[(αα⊤−(K+σ2I)−1) ∂K/∂θj]\tfrac12\Tr\big[(\boldsymbol\alpha\boldsymbol\alpha^\top-(K+\sigma^2I)^{-1})\,\partial K/\partial\theta_j\big], also O(n3)\order{n^3}. The objective is non-convex, so restarts or priors on hyperparameters help.

Scaling up, deciding, and deep networks

Three families of methods attack the O(n3)\order{n^3} cost:

  • Inducing points. Summarize the function by its values at m≪nm\ll n pseudo-inputs. Titsias's (2009) variational bound trains in O(nm2)\order{nm^2}, and stochastic variational GPs (Hensman, Fusi & Lawrence, 2013) use minibatches.
  • Random features. By Bochner's theorem, DD random Fourier features turn a GP into Bayesian linear regression with O(nD2)\order{nD^2} cost.
  • Structure and iteration. Kernel interpolation on grids (KISS-GP; Wilson & Nickisch, 2015) and conjugate-gradient solvers on GPUs (GPyTorch; Gardner et al., 2018) compute the same quantities with matrix–vector products.
Check your understanding

What can go wrong if GP-UCB is run with βt=0\beta_t=0, that is, always picking the maximizer of the posterior mean?

  1. Nothing: the posterior mean is the best estimate, so following it is optimal
  2. It stops exploring, can keep sampling a suboptimal point forever, and its regret can grow linearly
  3. Its computation becomes cubic in TT
  4. It samples uniformly at random
Show the answer

B. It stops exploring, can keep sampling a suboptimal point forever, and its regret can grow linearly

Without the σ\sigma bonus, regions the model is unsure about are never tried, so an early, misleading posterior can lock the search onto a local optimum: regret Ω(T)\Omega(T) in the worst case. The bonus is optimism in the face of uncertainty, as in UCB1 for bandits.

Neural networks connect back to GPs. Neal (1996) showed that a one-hidden-layer network with independent priors on its weights, scaled by the inverse width, converges to a Gaussian process as the width grows, by the central limit theorem; the result extends to deep networks, with kernels computed layer by layer (Lee et al., 2018; Matthews et al., 2018). Under gradient-descent training, infinitely wide networks evolve as kernel regression with the neural tangent kernel (Jacot, Gabriel & Hongler, 2018). Finite networks, however, learn their features, which no fixed kernel can do, so these limits explain some behaviors of deep learning but not its representation learning.

In practice, uncertainty for deep networks comes from approximations: Laplace approximations around a trained network, Monte Carlo dropout (Gal & Ghahramani, 2016) and deep ensembles (Lakshminarayanan, Pritzel & Blundell, 2017), which are often the best calibrated though not Bayesian in the strict sense. All of them degrade under distribution shift (Ovadia et al., 2019).

Key takeaways

  • Bayesian linear regression predicts through the kernel k(x,x′)=ϕ(x)⊤Σpϕ(x′)k(\mathbf x,\mathbf x')=\boldsymbol\phi(\mathbf x)^\top\Sigma_p\boldsymbol\phi(\mathbf x') alone, and its posterior mean is ridge regression with λ=σ2/τ2\lambda=\sigma^2/\tau^2; letting kk be any valid kernel gives a Gaussian process.
  • The GP posterior has mean k∗⊤(K+σ2I)−1y\mathbf k_*^\top(K+\sigma^2I)^{-1}\mathbf y and variance k∗∗−k∗⊤(K+σ2I)−1k∗k_{**}-\mathbf k_*^\top(K+\sigma^2I)^{-1}\mathbf k_*, which does not depend on y\mathbf y. Exact inference costs O(n3)\order{n^3} time and O(n2)\order{n^2} memory.
  • Kernels encode assumptions such as smoothness, periodicity and additivity. The marginal likelihood trades fit against complexity, Bochner's theorem yields random features, and contraction is fastest, at the minimax rate, when the prior's smoothness matches the truth's.
  • Inducing points, random features and iterative solvers scale GPs. GP-UCB achieves sublinear regret through information gain, and infinitely wide networks are GPs (NNGP, NTK), though finite networks learn features that fixed kernels cannot.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

In Bayesian linear regression with prior w∼N(0,τ2I)\mathbf w\sim\mathcal N(\mathbf 0,\tau^2I) and noise variance σ2\sigma^2, the posterior mean equals ridge regression minimizing ∥y−Φw∥2+λ∥w∥2\|\mathbf y-\Phi\mathbf w\|^2+\lambda\|\mathbf w\|^2 with…

  1. λ=τ2/σ2\lambda=\tau^2/\sigma^2
  2. λ=σ2τ2\lambda=\sigma^2\tau^2
  3. λ=σ2/τ2\lambda=\sigma^2/\tau^2
  4. λ=1/τ2\lambda=1/\tau^2
Show the answer

C. λ=σ2/τ2\lambda=\sigma^2/\tau^2

The negative log-posterior is 12σ2∥y−Φw∥2+12τ2∥w∥2\frac1{2\sigma^2}\|\mathbf y-\Phi\mathbf w\|^2+\frac1{2\tau^2}\|\mathbf w\|^2; multiply by 2σ22\sigma^2. A tighter prior (small τ\tau) or noisier data (large σ\sigma) means more shrinkage.

Question 2

Why does the GP posterior variance at a test point not depend on the observed outputs y\mathbf y?

  1. Because the outputs are assumed to be noise-free
  2. Because the variance is computed from the prior only
  3. Because the kernel is stationary
  4. Because a Gaussian's conditional covariance depends only on the joint covariance, not on the observed values
Show the answer

D. Because a Gaussian's conditional covariance depends only on the joint covariance, not on the observed values

k∗∗−k∗⊤(K+σ2I)−1k∗k_{**}-\mathbf k_*^\top(K+\sigma^2I)^{-1}\mathbf k_* involves only inputs and hyperparameters. The data's values enter through the hyperparameters if those are fit by marginal likelihood, but not directly.

Question 3

Exact GP training uses a Cholesky factorization of the n×nn\times n matrix K+σ2IK+\sigma^2I. If the training set doubles, the training time grows by a factor of about…

  1. 2
  2. 4
  3. 8
  4. 16
Show the answer

C. 8

Cholesky takes about n3/3n^3/3 floating-point operations, so doubling nn multiplies the time by 23=82^3=8, and memory by 4.

Question 4

The true regression function on [0,1][0,1] has Sobolev smoothness β=2\beta=2. Which Matérn prior smoothness α\alpha gives the fastest posterior contraction, and at what rate?

  1. α=2\alpha=2, rate n−2/5n^{-2/5}
  2. α=∞\alpha=\infty (squared exponential with a fixed length scale), rate n−1/2n^{-1/2}
  3. α=12\alpha=\tfrac12, rate n−1/4n^{-1/4}
  4. Any α\alpha, rate n−1/2n^{-1/2}
Show the answer

A. α=2\alpha=2, rate n−2/5n^{-2/5}

The rate n−min⁡(α,β)/(2α+d)n^{-\min(\alpha,\beta)/(2\alpha+d)} is maximized at α=β=2\alpha=\beta=2: n−2/(4+1)=n−2/5n^{-2/(4+1)}=n^{-2/5}, the minimax rate. A rougher prior (α=12\alpha=\tfrac12) gives n−1/4n^{-1/4}; smoother ones are slower too.

Further reading

  • C. E. Rasmussen & C. K. I. Williams, Gaussian Processes for Machine Learning (MIT Press, 2006).
  • R. M. Neal, Bayesian Learning for Neural Networks (Springer, 1996).
  • M. Titsias, "Variational learning of inducing variables in sparse Gaussian processes," AISTATS (2009).
  • N. Srinivas, A. Krause, S. M. Kakade & M. Seeger, "Gaussian process optimization in the bandit setting: No regret and experimental design," ICML (2010).
  • A. Rahimi & B. Recht, "Random features for large-scale kernel machines," NeurIPS (2007).