Kernel Methods

01 · Motivation

Why does this matter?

Chapter 02 ended on a remarkable observation: a linear model with cleverly chosen basis functions $\boldsymbol{\phi}(\mathbf{x})$ can fit almost any shape. Polynomials, Gaussians, sigmoids — pick the right $\boldsymbol{\phi}$ and the same closed-form formula $\hat{\mathbf{w}} = (\boldsymbol{\Phi}^\top \boldsymbol{\Phi})^{-1}\boldsymbol{\Phi}^\top \mathbf{t}$ does the rest.

But there’s a catch — actually three.

The kernel trick solves all three at once. Its central insight is so simple it almost feels like cheating.

Three payoffs follow immediately. First, you can use feature spaces so large you couldn’t write them down — even infinite ones — because the kernel computes the inner product directly. Second, you can define kernels on non-vector objects: a kernel on two strings, or two graphs, or two sets, is just a single real number that says “how similar are these two things?”. Third, the same trick instantly upgrades half a dozen algorithms you already know: ridge regression (this chapter), the perceptron, PCA, and most famously SVMs (Chapter 07).

The price you pay is computational. Kernel methods are memory-based — like nearest neighbours, the training points live inside the model and prediction touches all of them. For a training set of size $N$, prediction costs roughly $O(N)$ and training costs roughly $O(N^3)$. This is the trade-off the chapter circles back to repeatedly.

02 · Intuition

The idea in plain language

Imagine you’re given a dataset that no straight line can separate. Reds in the middle, blues around the edge — a classic frustration. You stare at the picture and think: “if only I could see this data from a higher viewpoint, maybe the classes would fall apart cleanly.” That instinct is exactly right. The kernel trick formalises it.

Lifting data to a higher dimension

Take a one-dimensional dataset that no line can split: two red points at $x = -1$ and $x = +1$, one blue point at $x = 0$. In 1D this is hopeless. But now apply the simple map $x \mapsto (x, x^2)$. Suddenly every point lives in 2D, and a horizontal line at $x^2 = 0.5$ splits them cleanly. We didn’t change the data. We changed the space.

That’s the geometric intuition. Push the data into a higher-dimensional space, do something linear there, project the answer back. Polynomial features, Gaussian bumps, sigmoid steps — every basis function from Ch. 02 was secretly doing this.

The trick: skip the lift, keep the answer

Here is where the magic enters. Suppose we want to do ridge regression in a feature space with a million dimensions. The normal pipeline says: build $\boldsymbol{\Phi} \in \mathbb{R}^{N \times 10^6}$, then form $\boldsymbol{\Phi}^\top \boldsymbol{\Phi} \in \mathbb{R}^{10^6 \times 10^6}$, then invert it. The first matrix barely fits in RAM; the second does not exist on any computer.

But notice: in the closed-form OLS pipeline, the feature vectors only ever appear inside dot products. If we can compute those dot products cheaply, without explicitly building $\boldsymbol{\phi}(\mathbf{x})$, we win. Take the polynomial example. In 2D, the quadratic feature map is $\boldsymbol{\phi}(\mathbf{x}) = (x_1^2,\, \sqrt{2}\,x_1 x_2,\, x_2^2)$. Now compute $(\mathbf{x}^\top \mathbf{x}')^2$ directly and expand it:

That single observation is the kernel trick. Crank it up to degree $p$ and you get all monomials of degree $\le p$ for free. Push it to a Gaussian kernel and you implicitly visit an infinite-dimensional feature space — every smooth bump at every centre — while doing one exponential and one subtraction.

Two viewpoints, same kernel

The kernel function quietly wears two hats.

Both viewpoints describe the same object — choose whichever helps you reason about the problem at hand. The exam tends to test the algebraic one; real applications usually live in the geometric one.

03 · Formalism

Definitions and equations

The notation builds directly on Ch. 02 — most of what follows is “linear regression, but inner products replaced by $k(\cdot, \cdot)$“.

φ(x)

a (possibly very high or infinite-dimensional) feature map $\boldsymbol{\phi} : \mathcal{X} \to \mathcal{F}$.

k(x, x′)

the kernel $\boldsymbol{\phi}(\mathbf{x})^\top \boldsymbol{\phi}(\mathbf{x}')$ — a similarity score.

Φ

the $N \times M$ design matrix; row $n$ is $\boldsymbol{\phi}(\mathbf{x}_n)^\top$.

K

the $N \times N$ Gram matrix, $\mathbf{K} = \boldsymbol{\Phi}\boldsymbol{\Phi}^\top$, entries $K_{nm} = k(\mathbf{x}_n, \mathbf{x}_m)$.

a

the dual coefficient vector; the weights become $\mathbf{w} = \boldsymbol{\Phi}^\top \mathbf{a}$.

λ

the ridge regularisation strength (= the GP noise variance $\sigma_n^2$).

The kernel function

The kernel associated with a feature map $\boldsymbol{\phi}$ is

Two important families:

• Stationary kernels: $k(\mathbf{x}, \mathbf{x}') = k(\mathbf{x} - \mathbf{x}')$ — only the difference between inputs matters. Translation-invariant.
• Radial / homogeneous kernels: $k(\mathbf{x}, \mathbf{x}') = k(\|\mathbf{x} - \mathbf{x}'\|)$ — only the distance matters. Rotation- and translation-invariant.

The simplest kernel of all is the linear kernel, corresponding to the identity feature map $\boldsymbol{\phi}(\mathbf{x}) = \mathbf{x}$: $k_{\text{lin}}(\mathbf{x}, \mathbf{x}') = \mathbf{x}^\top \mathbf{x}'$. All kernels can be thought of as generalisations of this.

Dual representation of ridge regression

Recall the regularised least-squares objective from Ch. 02:

Set $\nabla_{\mathbf{w}} L = 0$. You get $\mathbf{w} = -\tfrac{1}{\lambda}\sum_n (\mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}_n) - t_n)\,\boldsymbol{\phi}(\mathbf{x}_n)$. Rename the prefactors $a_n = -\tfrac{1}{\lambda}(\mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}_n) - t_n)$ and the equation becomes

Substitute $\mathbf{w} = \boldsymbol{\Phi}^\top \mathbf{a}$ back into $L$. After a few lines of algebra (done in §4) the objective in terms of $\mathbf{a}$ becomes

Setting $\nabla_{\mathbf{a}} L = 0$ gives the dual solution:

Predicting with kernels

The prediction on a new input $\mathbf{x}$ is $y(\mathbf{x}) = \mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}) = \mathbf{a}^\top \boldsymbol{\Phi}\,\boldsymbol{\phi}(\mathbf{x})$. The vector $\boldsymbol{\Phi}\,\boldsymbol{\phi}(\mathbf{x})$ has $n$-th entry $\boldsymbol{\phi}(\mathbf{x}_n)^\top \boldsymbol{\phi}(\mathbf{x}) = k(\mathbf{x}_n, \mathbf{x})$, so:

When is a function a valid kernel?

We can’t just write down any old function and call it a kernel. The kernel has to actually correspond to an inner product in some Hilbert space. The condition is clean.

Building new kernels from old

Showing PSD directly is awkward. In practice you almost never do it — you compose new kernels from known-valid building blocks. Given valid $k_1, k_2$, all of the following are also valid kernels:

The kernel zoo

Why is the Gaussian kernel valid? Expand the squared distance: $\|\mathbf{x} - \mathbf{x}'\|^2 = \mathbf{x}^\top \mathbf{x} - 2\mathbf{x}^\top \mathbf{x}' + \mathbf{x}'^\top \mathbf{x}'$. Then

The Gaussian kernel extends to non-Euclidean distances by the substitution $\|\mathbf{x} - \mathbf{x}'\|^2 \mapsto \kappa(\mathbf{x},\mathbf{x}) + \kappa(\mathbf{x}',\mathbf{x}') - 2\,\kappa(\mathbf{x},\mathbf{x}')$ for any valid kernel $\kappa$ — which opens the door to Gaussian kernels on strings, graphs, and other exotic objects.

Kernels on non-vector objects

Once you accept that a kernel is “any symmetric PSD similarity score”, you can build kernels on data types that aren’t $\mathbb{R}^d$ at all. Two clean examples:

• Sets: $k(A_1, A_2) = 2^{|A_1 \cap A_2|}$. The implicit feature map is the indicator vector over all subsets of the universe.
• From a generative model: if $p(\mathbf{x})$ is a probability density, then $k(\mathbf{x}, \mathbf{x}') = p(\mathbf{x})\, p(\mathbf{x}')$ is a valid kernel (one-dimensional feature map $\boldsymbol{\phi}(\mathbf{x}) = p(\mathbf{x})$). Two inputs are “similar” if both are individually likely under the model.

RBF networks and Nadaraya–Watson regression

The kernel prediction formula $y(\mathbf{x}) = \sum_n a_n\, k(\mathbf{x}_n, \mathbf{x})$ has a beautiful network interpretation. Each training point $\mathbf{x}_n$ becomes a hidden unit centred at $\mathbf{x}_n$. The activation of that unit for input $\mathbf{x}$ is $k(\mathbf{x}_n, \mathbf{x})$ — a radial bump. The output layer takes the weighted sum with learned weights $a_n$. This is the RBF network.

Historically, RBF networks were first proposed for exact interpolation: choose $N$ weights so that $y(\mathbf{x}_n) = t_n$ for every training point. The system $\mathbf{K}\,\mathbf{w} = \mathbf{t}$ has a unique solution when $\mathbf{K}$ is invertible. Sounds great — until you remember real data is noisy. Exact interpolation through noisy targets is a textbook case of overfitting. The cure is exactly the $\lambda \mathbf{I}$ we added to get the dual ridge formula. Regularised kernel ridge = noise-tolerant RBF network.

Nadaraya–Watson can be derived from a different angle that’s worth seeing — it changes how you think about the model. Treat the training set as samples from an unknown joint density $p(\mathbf{x}, t)$. Estimate $p$ with a Parzen window:

The regression function is the conditional expectation $y(\mathbf{x}) = \mathbb{E}[t \mid \mathbf{x}] = \int t\, p(t \mid \mathbf{x})\, dt$. Substitute the Parzen estimate, integrate $t$ out (which gives the marginal kernel $g(\mathbf{x}) = \int f(\mathbf{x}, t)\, dt$), and the equation collapses to exactly the normalised RBF formula above. Nadaraya–Watson is the regression function implied by a Parzen-window density estimate.

Bonus: because Nadaraya–Watson comes from a density estimate, it naturally supplies a full conditional distribution $p(t \mid \mathbf{x})$ — not just a point prediction. Variance, quantiles, and confidence intervals all fall out without extra work.

From Bayesian linear regression to Gaussian processes

Gaussian processes sit at the probabilistic end of the kernel family. The cleanest way to introduce them is to derive them from a model you already know — Bayesian linear regression.

Start with the familiar linear-in-features model $y(\mathbf{x}, \mathbf{w}) = \mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x})$. Place a zero-mean Gaussian prior on the weights: $p(\mathbf{w}) = \mathcal{N}(\mathbf{w}\mid \mathbf{0},\, \tau \mathbf{I})$. Stack the predictions on the training inputs into a vector $\mathbf{y} = \boldsymbol{\Phi}\mathbf{w}$. Since $\mathbf{y}$ is a linear transformation of a Gaussian random vector, it is itself Gaussian:

Now generalise: instead of choosing $\boldsymbol{\phi}$ and deriving $\mathbf{K}$, pick the kernel $k$ directly. The result is a Gaussian process.

A subtle but important conceptual move just happened: the kernel is now interpreted as a covariance. Two inputs that the kernel rates as “similar” are inputs at which the model expects the function to produce correlated outputs. Smooth kernels → smooth functions; rapidly decaying kernels → wiggly functions.

Now add observation noise: $t_n = y(\mathbf{x}_n) + \varepsilon_n$ with $\varepsilon_n \sim \mathcal{N}(0, \sigma_n^2)$ i.i.d. The joint distribution of the noisy targets is

The GP predictive distribution

For a new input $\mathbf{x}_{N+1}$, define $\mathbf{k} \in \mathbb{R}^N$ with $k_n = k(\mathbf{x}_n, \mathbf{x}_{N+1})$ and $c = k(\mathbf{x}_{N+1}, \mathbf{x}_{N+1}) + \sigma_n^2$. Then the joint distribution of all $N+1$ noisy targets is Gaussian with block-structured covariance:

Apply the standard partitioned-Gaussian conditioning formula. The conditional distribution of $t_{N+1}$ given $\mathbf{t}$ is Gaussian:

m(x)

posterior mean — identical to kernel ridge with $\lambda = \sigma_n^2$.

σ²(x)

posterior variance — how uncertain the model is at $\mathbf{x}$. Decreases near training points; increases far from them.

C⁻¹t

computed once at cost $O(N^3)$; the same vector is reused for every prediction.

c − kᵀC⁻¹k

the prior variance $c$ minus the variance “explained” by the data. Always non-negative because $\mathbf{C}_N$ is PSD.

Why this is worth the algebra: the GP gives you a full predictive distribution, not just a point estimate. Knowing where the model is uncertain is essential for active learning, Bayesian optimisation, and safety-critical applications.

04 · Worked example

Kernel ridge regression on three points, by hand

We’ll fit a kernel ridge regressor to a tiny 1-D dataset using a Gaussian kernel. Every matrix is small enough to track by hand, and you’ll see the dual formula $\hat{\mathbf{a}} = (\mathbf{K} + \lambda \mathbf{I})^{-1}\mathbf{t}$ in concrete numbers.

05 · Visual explanation

Pictures that lock the ideas in

The Gram matrix as a heatmap

For points scattered on a line, the Gram matrix is a heatmap whose $(n, m)$ cell tells you how similar points $n$ and $m$ are in the eyes of the kernel. Bright cells near the diagonal mean “neighbouring points see each other”; the matrix darkens as you move off-diagonal. The Gram matrix is also where validity is decided — a kernel is valid iff every such heatmap, for every possible point set, is a PSD matrix. The hands-on heatmap below lets you recompute it live.

A non-linear decision boundary, built from circular bumps

The left plot is a binary classification dataset that no straight line can solve — the classes are concentric. The right plot shows the boundary a Gaussian-kernel classifier learns. It bends, it curves, it does things linear methods can never do.

inner class (+1) outer class (−1)

The right-hand boundary is built from a sum of Gaussian bumps, one per training point. Each training point’s bump pulls the boundary toward its own class; where the bumps balance, the boundary forms. This is the geometric face of the dual formula $y(\mathbf{x}) = \sum_n a_n k(\mathbf{x}_n, \mathbf{x})$ — every training point contributes a tiny vote, weighted by how close $\mathbf{x}$ is to it.

A Gaussian process and its uncertainty

Gaussian processes don’t just predict — they also tell you how confident they are. Where the data are dense, the predictive band is narrow (the model is confident); where there are no data, the band fans out (the model knows it doesn’t know). This calibrated uncertainty is what makes GPs irresistible for safety-critical applications. You can watch the band breathe in the RBF / GP explorer below.

06 · Hands-on

Try it yourself

Three interactive labs, each isolating one concept. Slide, click, and watch the maths move — these are the moments where kernels stop being a list of formulas and start being something you can feel.

07 · Exam intel

What the exam actually tests

Kernel methods are an exam favourite: derivations are short, symbol-heavy, and very specific. Six question shapes appear essentially every year.

08 · Common mistakes

Where students get this wrong

09 · Self-check

Can you answer these?

Six quick checks in the style the chapter likes to be tested. Click an option for instant feedback.

10 · Recap

One-screen summary