Bishop PRML, Chapter 6

Kernel Methods

The kernel trick, Gaussian processes, and the art of working in infinite-dimensional feature spaces without ever going there.

Prerequisites: Chapters 3–4 (linear regression, classification, Bayesian inference).

Chapters

Simulations

Quizzes

Chapter 0: Why Kernels?

Many algorithms (linear regression, PCA, nearest neighbors) depend on the data only through inner products between data points: x_n^Tx_m. What if we could replace these inner products with a more general similarity measure?

The kernel function k(x, x') measures similarity between two inputs. The remarkable discovery: for many useful kernels, there exists a (possibly infinite-dimensional) feature space where the kernel computes the inner product: k(x, x') = φ(x)^Tφ(x').

The kernel trick: We can work in a high-dimensional (even infinite-dimensional) feature space without ever computing the feature vectors φ(x). We only need the kernel function k(x, x'), which is cheap to compute. This gives us the power of nonlinear feature expansions with the computational cost of working in the original input space.

The kernel trick transforms the question from "what basis functions should I use?" to "what similarity measure is appropriate for my data?" This is often a more natural question.

Check: What is the kernel trick?

Computing inner products in high-dimensional feature space through a kernel function, without ever explicitly computing the feature vectors A method for speeding up matrix multiplication A regularization technique for neural networks

Chapter 1: The Dual Representation

Consider regularized least squares from Ch 3. The solution w = (Φ^TΦ + λI)⁻¹Φ^Tt can be rewritten as:

w = Φ^Ta

where a = (1/λ)(t − Φw) is a vector of N coefficients (one per training point). Substituting back, we get the dual form:

a = (K + λI)⁻¹ t

where K is the N × N Gram matrix with K_nm = k(x_n, x_m) = φ(x_n)^Tφ(x_m).

Primal vs. dual: The primal form inverts an M × M matrix (M = number of basis functions). The dual inverts an N × N matrix (N = number of data points). If we use the kernel trick, M could be infinite but N is always finite. The dual lets us work in infinite feature spaces at cost O(N³).

Prediction for a new input x:

y(x) = k(x)^T (K + λI)⁻¹ t

where k(x)_n = k(x, x_n). The prediction is a weighted sum of kernel evaluations with training points. No explicit feature vectors needed!

Check: The dual representation expresses the solution as:

A linear combination of training points (in feature space), using the Gram matrix A polynomial expansion of the input The eigendecomposition of the data matrix

Chapter 2: The Kernel Trick in Detail

For a function k(x, x') to be a valid kernel, it must correspond to an inner product in some feature space. The key theorem:

Mercer's theorem: A function k(x, x') is a valid kernel if and only if the Gram matrix K_nm = k(x_n, x_m) is positive semi-definite for any set of data points. Equivalently, the kernel has an expansion k(x, x') = ∑_i λ_i ψ_i(x) ψ_i(x') with λ_i ≥ 0.

A concrete example: the polynomial kernel. Consider k(x, x') = (x x' + 1)² in 1D. Expanding: k(x, x') = 1 + 2xx' + x²x'² = φ(x)^Tφ(x') where φ(x) = (1, √2 x, x²). A degree-2 polynomial kernel in D dimensions implicitly works in a feature space of dimension O(D²) — but the kernel evaluation costs just O(D).

For a general degree-M polynomial in D dimensions, the feature space has dimension O(D^M), but the kernel k(x, x') = (x^Tx' + c)^M still costs just O(D). The savings become astronomical for large M or D.

Check: What condition must a valid kernel function satisfy?

The Gram matrix must be positive semi-definite for any set of data points The kernel must be symmetric and bounded above by 1 The kernel must be differentiable everywhere

Chapter 3: Common Kernels

Kernel	Formula	Feature space
Linear	k(x,x') = x^Tx'	D-dimensional (no transformation)
Polynomial	k(x,x') = (x^Tx'+c)^M	O(D^M)-dimensional
Gaussian (RBF)	k(x,x') = exp(−\|\|x−x'\|\|²/2ℓ²)	Infinite-dimensional
Sigmoid	k(x,x') = tanh(κx^Tx'−δ)	Not always valid (not PSD for all κ,δ)

The Gaussian kernel is infinite-dimensional. The Taylor expansion of exp(−||x−x'||²/2ℓ²) contains terms of every polynomial degree. The corresponding feature space is infinite-dimensional. Yet the kernel evaluation is O(D) — a single exponential of the squared distance. This is the magic of kernels: infinite-dimensional feature spaces at finite computational cost.

The length scale ℓ in the Gaussian kernel controls the smoothness. Small ℓ → local influence (only nearby points matter) → wiggly function. Large ℓ → global influence → smooth function. This is the kernel analog of the bias-variance tradeoff.

Check: The Gaussian (RBF) kernel implicitly maps to what kind of feature space?

An infinite-dimensional feature space A D-dimensional feature space A 2D feature space

Chapter 4: Constructing Kernels

We can build complex kernels from simpler ones. If k₁ and k₂ are valid kernels, then so are:

Construction	Result
c k₁(x,x')	Scaled kernel (c > 0)
k₁ + k₂	Sum kernel
k₁ · k₂	Product kernel
f(x) k₁(x,x') f(x')	Scaled kernel (any function f)
exp(k₁(x,x'))	Exponentiated kernel

These rules let us design kernels for structured data — strings, graphs, sets — where traditional feature vectors don't exist. For example, string kernels count shared substrings between two text documents, and graph kernels measure structural similarity between molecules.

Kernels beyond vectors: One of the most powerful aspects of kernel methods is that inputs don't have to be vectors. As long as you can define a valid kernel between any two inputs (sequences, trees, graphs, images), you can apply kernel methods. This makes kernel methods applicable to almost any data type.

Check: Can kernel methods be applied to non-vector data like strings or graphs?

Yes, as long as a valid (positive semi-definite) kernel function can be defined between any two inputs No, kernel methods require fixed-length vector inputs Only with special preprocessing

Chapter 5: RBF Networks

Radial basis function (RBF) networks use Gaussian basis functions centered on a subset of the training data (or on learned centers):

y(x) = ∑_j=1^M w_j exp(−||x − μ_j||² / 2s²) + w₀

This is a linear model in the feature space defined by Gaussian basis functions. The parameters w_j can be found by solving a linear system (unlike neural networks, which require iterative optimization).

RBF vs neural network: Both use nonlinear basis functions. But in an RBF network, each basis function responds to a local region of input space (near its center). In a neural network, each hidden unit divides the input space with a hyperplane. RBF networks are local; neural networks are global. This makes RBFs better for interpolation but potentially requiring more units for complex functions.

Nadaraya-Watson model: A special case of kernel regression where the weights are determined by the kernel itself: y(x) = ∑_n k(x,x_n) t_n / ∑_n k(x,x_n). This is a weighted average of training targets, with weights proportional to kernel similarity. No training required — just look up the nearest neighbors and average.

Check: How do RBF basis functions differ from neural network hidden units?

RBFs respond locally (near their center), while neural network units divide space with hyperplanes (globally) RBFs are always superior There is no difference

Chapter 6: Gaussian Processes — The Idea

A Gaussian process (GP) is a distribution over functions. Instead of specifying a parametric model and putting a prior on parameters, we put a prior directly on the space of functions.

f(x) ~ GP(m(x), k(x, x'))

where m(x) is the mean function (often zero) and k(x, x') is the covariance function (the kernel). This means: for any finite set of points, the function values are jointly Gaussian.

From weights to functions: Remember Bayesian linear regression (Ch 3)? We put a Gaussian prior on weights w, which induced a Gaussian distribution over functions y(x) = w^Tφ(x). As M → ∞, this becomes a Gaussian process with kernel k(x,x') = ∑_j φ_j(x)φ_j(x')/α. The GP is the nonparametric limit of Bayesian linear regression — infinitely many basis functions.

The kernel encodes our prior beliefs about the function: how smooth it is, how quickly it varies, whether it has periodic structure. Choosing a kernel is the GP analog of choosing a model architecture.

Gaussian Process Prior Samples

Random functions drawn from a GP prior with RBF kernel. Adjust the length scale to see how it controls smoothness.

ℓ0.30

Check: What is a Gaussian process?

A distribution over functions, where any finite set of function values is jointly Gaussian A Gaussian distribution with a process noise term A neural network with Gaussian activation functions

Chapter 7: GP Regression

Given N training points, the GP posterior is also a GP (Gaussians are closed under conditioning):

m(x|D) = k(x)^T (K + σ²I)⁻¹ t

σ²(x|D) = k(x,x) − k(x)^T (K + σ²I)⁻¹ k(x)

where K is the N × N kernel matrix and k(x) is the vector of kernel evaluations with training points.

Automatic uncertainty: The predictive variance is small near training points (where we have data) and large far from them (where we're uncertain). This is the ideal behavior: the model "knows what it doesn't know." Unlike neural networks where uncertainty estimation requires approximations, GPs provide exact uncertainty for free.

The kernel hyperparameters (length scale, signal variance, noise variance) can be learned by maximizing the log marginal likelihood:

ln p(t|θ) = −½ t^T(K + σ²I)⁻¹t − ½ ln|K + σ²I| − N/2 ln(2π)

This automatically balances data fit (first term) with model complexity (second term) — the evidence framework from Ch 3, now in function space.

Check: How does GP predictive variance behave?

Small near training data (confident) and large far from training data (uncertain) Constant everywhere Large near training data and small far away

Chapter 8: GP Classification

For classification, the GP prior is placed on a latent function f(x), then passed through a sigmoid to get class probabilities:

p(C₁|x) = σ(f(x))

where f ~ GP(0, k). The problem: the sigmoid likelihood is not conjugate to the Gaussian prior, so the posterior over f is non-Gaussian.

Two approximation strategies:

Laplace approximation: Find the mode of p(f|t) (the MAP latent function values), then fit a Gaussian. Conceptually identical to Laplace for logistic regression (Ch 4) but now in function space.

Expectation propagation (EP): A more accurate approximation that matches the moments of the true posterior at each data point. Generally better calibrated than Laplace.

The recurring theme: Bayesian inference is easy when everything is Gaussian (regression). The moment we introduce non-Gaussian likelihoods (classification), we need approximations. This theme continues throughout the book: Ch 10 (variational inference) and Ch 11 (sampling) develop increasingly powerful tools for non-conjugate inference.

Check: Why is GP classification harder than GP regression?

The sigmoid likelihood breaks conjugacy, making the posterior non-Gaussian and requiring approximations Classification requires more data The kernel matrix becomes singular

Chapter 9: Summary

Chapter 6 introduced a fundamentally different perspective on machine learning:

Parametric (Ch 3-5)	Kernel / GP (Ch 6)
Prior on parameters w	Prior on functions f
Finite-dimensional	Potentially infinite-dimensional
Prediction: O(M) per point	Prediction: O(N) per point
Training: O(NM²)	Training: O(N³)
Fixed basis functions or learned (NN)	Kernel encodes prior beliefs
Scales to large N	Expensive for large N (cubic cost)

The GP perspective: A GP is the Bayesian nonparametric ideal: it uses the data to shape the posterior over functions without committing to a finite parametric form. The kernel replaces architecture design. The marginal likelihood replaces cross-validation. Uncertainty is exact, not approximate. The catch is the O(N³) cost, which limits GPs to moderate-sized datasets unless approximations (inducing points, sparse GPs) are used.

What comes next: Chapter 7 covers sparse kernel machines — SVMs and relevance vector machines — which address the O(N) prediction cost of kernel methods by finding sparse representations.

"The Gaussian process viewpoint provides a unifying
framework for many regression and classification methods."
— Christopher Bishop, PRML §6.4

Check: What is the main computational limitation of Gaussian processes?

O(N^3) training cost due to matrix inversion, limiting them to moderate-sized datasets They can only use linear kernels They require labeled data for every point