Module 10: Gaussian Processes

Module 10: Gaussian Processes

This module introduces Gaussian processes (GPs) as distributions over functions, discusses covariance kernels and their connection to reproducing kernel Hilbert spaces (RKHS), and derives the exact posterior for GP regression. We also address hyperparameter estimation and computational complexity.

1. Gaussian Processes as Distributions over Functions

Definition 10.1 (Gaussian Process)

Let () be an index set (e.g., (^d)). A stochastic process ({f(x) : x }) is a Gaussian process if for any finite collection of points (x_1, , x_n ), the random vector ((f(x_1), , f(x_n))) is multivariate Normal.

A GP is characterized by its mean function (m: ) and covariance kernel (k: ): \[ m(x) = \mathbb{E}[f(x)], \quad k(x,x') = \operatorname{Cov}(f(x), f(x')). \] We write \[ f \sim \operatorname{GP}(m, k). \]

2. Covariance Kernels and RKHS

2.1 Positive Definiteness

A function (k: ) is a positive-definite kernel if for any finite set (x_1, , x_n) and coefficients (c_1, , c_n), \[ \sum_{i=1}^n \sum_{j=1}^n c_i c_j k(x_i, x_j) \ge 0. \]

2.2 RKHS Associated with a Kernel

Given a positive-definite kernel (k), there exists a unique Hilbert space (_k) of functions on () such that:

  1. For each (x), the function (k(x, ) _k).
  2. Reproducing property: For all (f _k) and (x ), \[ f(x) = \langle f, k(x, \cdot) \rangle_{\mathcal{H}_k}. \]

Proof idea: Use the Moore–Aronszajn theorem to construct (_k) as the completion of finite linear combinations of kernel sections.

2.3 GP Sample Paths and RKHS

While (_k) is not generally the support of the GP, there is a close relationship between sample path regularity and RKHS norms. For some kernels, GP sample paths almost surely lie outside the RKHS but are controlled by it.

3. Gaussian Process Regression

3.1 Model Setup

Let (f (0, k)). Observations are \[ y_i = f(x_i) + \varepsilon_i, \quad \varepsilon_i \sim N(0, \sigma^2), \] independent noise. Collect (y = (y_1, , y_n)^) and define the Gram matrix (K ^{n n}) with entries (K_{ij} = k(x_i, x_j)).

For a set of test inputs (X_* = (x_^{(1)}, , x_^{(m)})), define:

  • (K_* ^{n m}) with entries ((K_){i} = k(x_i, x^{()})),
  • (K_{} ^{m m}) with entries ((K_{})_{‘} = k(x_^{()}, x_^{(’)})).

3.2 Joint Prior and Posterior

The joint prior for (f(X)) and (f(X_*)) is multivariate Normal: \[ \begin{pmatrix} f(X) \\ f(X_*) \end{pmatrix} \sim N\left( 0, \begin{pmatrix} K & K_* \\ K_*^\top & K_{**} \end{pmatrix} \right). \]

The observation model adds independent Gaussian noise to (f(X)), so \[ y \mid f(X) \sim N(f(X), \sigma^2 I_n). \]

Theorem 10.2 (GP Regression Posterior)

The posterior distribution of (f_* := f(X_*)) given data (y) is multivariate Normal: \[ f_* \mid y \sim N(m_*, \Sigma_*), \] where \[ m_* = K_*^\top (K + \sigma^2 I_n)^{-1} y, \] \[ \Sigma_* = K_{**} - K_*^\top (K + \sigma^2 I_n)^{-1} K_*. \]

Proof: Let (f = f(X)) and (f_* = f(X_)). By the GP prior, \[ \begin{pmatrix} f \\ f_* \end{pmatrix} \sim N\left(0, \begin{pmatrix} K & K_* \\ K_*^\top & K_{**} \end{pmatrix}\right). \] The observation model is \[ y = f + \varepsilon, \quad \varepsilon \sim N(0, \sigma^2 I_n), \; \varepsilon \text{ independent of } f_*. \] Hence the joint distribution of ((y, f_)) is Gaussian with mean zero and covariance \[ \operatorname{Cov}\bigl((y, f_*)\bigr) = \begin{pmatrix} K + \sigma^2 I_n & K_* \\ K_*^\top & K_{**} \end{pmatrix}. \] Using the conditional distribution formula for a jointly Gaussian vector \[ \begin{pmatrix} Y \\ Z \end{pmatrix} \sim N\left(0, \begin{pmatrix} \Sigma_{YY} & \Sigma_{YZ} \\ \Sigma_{ZY} & \Sigma_{ZZ} \end{pmatrix}\right), \] we have \[ Z \mid Y = y \sim N\bigl( \Sigma_{ZY} \Sigma_{YY}^{-1} y,\; \Sigma_{ZZ} - \Sigma_{ZY} \Sigma_{YY}^{-1} \Sigma_{YZ} \bigr). \] Identifying (Y = y), (Z = f_), ({YY} = K + ^2 I_n), ({YZ} = K_), we obtain \[ m_* = K_*^\top (K + \sigma^2 I_n)^{-1} y, \] and \[ \Sigma_* = K_{**} - K_*^\top (K + \sigma^2 I_n)^{-1} K_*, \] which proves the stated posterior distribution. ()

4. Hyperparameter Estimation

Covariance kernels often depend on hyperparameters (_k) (e.g., length-scales, output variance). Common approaches:

  • Empirical Bayes / Type II ML: Maximize the marginal likelihood (p(y _k, ^2)) with respect to (_k).
  • Fully Bayesian: Place priors on (_k) and use MCMC or other methods to sample from the joint posterior.

The marginal likelihood in GP regression is \[ \log p(y \mid \theta_k, \sigma^2) = -\tfrac12 y^\top (K_\theta + \sigma^2 I_n)^{-1} y - \tfrac12 \log |K_\theta + \sigma^2 I_n| - \tfrac{n}{2} \log (2\pi). \]

5. Computational Complexity and Approximations

5.1 Exact Complexity

  • Computing the Cholesky factorization of (K + ^2 I_n) costs (O(n^3)).
  • Storage cost is (O(n^2)).

Thus exact GP regression becomes impractical for very large (n).

5.2 Approximation Techniques

  • Inducing point methods: Introduce (m n) pseudo-inputs and approximate the GP via low-rank covariance structures.
  • Sparse approximations: Use low-rank plus diagonal covariance approximations.
  • Structured kernels: Exploit Kronecker or Toeplitz structure when inputs lie on grids.

These methods reduce computational cost at the price of approximation error.

6. Problem Set 10 (Representative Problems)

  1. GP Regression Derivation. Derive Theorem ?@thm-gp-regression in full detail by starting from the joint Gaussian distribution of ((f(X), f(X_*))) and applying the conditional multivariate Normal formula.

  2. RKHS Reproducing Property. Prove the reproducing property for the RKHS associated with a kernel (k) (see Section Section 1.2.2), and discuss its implications for function evaluation and regularization.

  3. Marginal Likelihood Gradient. Derive the gradient of the GP marginal likelihood with respect to a kernel hyperparameter (k), expressing the result in terms of (K^{-1}) and derivatives of (K_).

  4. Computational Scaling. For an inducing point approximation with (m) inducing points, show how the computational cost scales in terms of (n) and (m). Discuss trade-offs between accuracy and efficiency.

  5. Sample Path Regularity. For the squared exponential kernel, discuss the almost-sure smoothness of GP sample paths and contrast this with the Sobolev regularity implied by Matérn kernels.