Reading club II. The kernel trick

Notes from an ML reading club session, continuing from linear regression.

Recap

First, the computational cost of the two forms from last time. In the primal form, forming $\mathbf{X}^T\mathbf{X}$ costs $O(ND^2)$ and inverting it costs $O(D^3)$. In the dual form, forming $\mathbf{X}\mathbf{X}^T$ costs $O(N^2D)$ and inverting costs $O(N^3)$. The primal form is cheaper when $D \ll N$ (few features, many data points), and the dual form is cheaper when $N \ll D$.

When $N < D$, fewer training points than features, the primal problem is underdetermined and admits infinitely many solutions. This is closely related to overfitting, since with more parameters than constraints the model can fit noise. Ridge regression selects a unique solution by penalizing large weights,

$$L_{\text{ridge}} = \frac{1}{2}\sum_{n=1}^{N}\left(\mathbf{w}^T\mathbf{x}^{(n)} - y^{(n)}\right)^2 + \frac{\lambda}{2}\|\mathbf{w}\|^2$$

where $\lambda > 0$ controls the trade-off between fit and complexity, and the modified normal equations $(\mathbf{X}^T\mathbf{X} + \lambda\mathbf{I})\,\mathbf{w} = \mathbf{X}^T\mathbf{y}$ are always invertible.

Features

Linear regression is not especially expressive. An improvement is to perform linear regression in a basis of $F$ fixed, nonlinear features $\boldsymbol{\phi}(\mathbf{x})$, where each $\phi_j(\mathbf{x})$ maps the input to a new coordinate. The model becomes

$$f(\hat{\mathbf{x}}) = \sum_{j=1}^{F} w_j \phi_j(\hat{\mathbf{x}}) = \mathbf{w}^T\boldsymbol{\phi}(\hat{\mathbf{x}})$$

For example, with $D=2$ inputs $(x_1, x_2)$, a quadratic feature map might be $\boldsymbol{\phi}(\mathbf{x}) = (x_1^2,\; x_1 x_2,\; x_2^2,\; x_1,\; x_2,\; 1)^T$, giving $F = 6$ features from $D = 2$ inputs.

In the dual form, we never need the individual feature vectors, only their inner products. The Gram matrix becomes

$$(\boldsymbol{\Phi}\boldsymbol{\Phi}^T)_{mn} = \boldsymbol{\phi}(\mathbf{x}^{(m)})^T\boldsymbol{\phi}(\mathbf{x}^{(n)})$$

and predictions take the form

$$f(\hat{\mathbf{x}}) = \sum_{n=1}^{N} \alpha_n \,\boldsymbol{\phi}(\mathbf{x}^{(n)})^T\boldsymbol{\phi}(\hat{\mathbf{x}})$$

Computing each inner product costs $O(F)$, which is expensive when $F$ is large.

The kernel trick

The key observation is that certain kernel functions $K(\mathbf{x}^{(m)}, \mathbf{x}^{(n)})$ compute the inner product in feature space without ever constructing the feature vectors. For example, the polynomial kernel of degree 2,

$$K(\mathbf{x}^{(m)}, \mathbf{x}^{(n)}) = (\mathbf{x}^{(m)} \cdot \mathbf{x}^{(n)} + 1)^2$$

costs only $O(D)$ to evaluate, since it operates entirely in the original $D$-dimensional input space, yet expanding it for $D=2$ reproduces the inner product of the quadratic feature map above, computed in $O(D)$ rather than $O(F)$ time.

How can we know the inner product without knowing the features? The features are determined by the choice of kernel. Each valid kernel implicitly defines a unique feature map (up to rotation) via Mercer’s theorem, and the dual form only ever queries inner products, which the kernel supplies directly. We still choose the features, but indirectly, through the choice of kernel, and we never pay the cost of materializing them. This insight is due to Aizerman, Braverman, and Rozonoer (1964), later popularized by Boser, Guyon, and Vapnik (1992) in the context of support vector machines.

Beyond the polynomial kernel, the Gaussian kernel (also called squared exponential or radial basis function) is particularly powerful,

$$K(\mathbf{x}^{(m)}, \mathbf{x}^{(n)}) = \exp\!\left(-\frac{\|\mathbf{x}^{(m)} - \mathbf{x}^{(n)}\|^2}{2\ell^2}\right)$$

where $\ell$ is the length-scale hyperparameter. Taylor-expanding the Gaussian kernel produces an infinite series of polynomial terms, so it is equivalent to working in an infinite-dimensional feature space, yet each evaluation still costs only $O(D)$. Polynomial kernels of degree $d$ capture all multinomial interactions up to order $d$, while the Gaussian kernel captures interactions of all orders.

Prediction in kernel space

In practice, the $N \times N$ kernel matrix $K_{mn} = K(\mathbf{x}^{(m)}, \mathbf{x}^{(n)})$ is constructed once from the training data. At prediction time, only the kernel vector $\mathbf{k}(\hat{\mathbf{x}})$, with entries $K(\mathbf{x}^{(n)}, \hat{\mathbf{x}})$, is needed,

$$f(\hat{\mathbf{x}}) = \mathbf{k}(\hat{\mathbf{x}})^T\boldsymbol{\alpha}$$

This costs $O(ND)$ per prediction, independent of the feature-space dimension $F$. All computation lives in kernel space, the $N$-dimensional space indexed by training points.

Although kernel methods are linear in the implicit feature space and therefore limited in expressiveness compared to deep neural networks, they remain popular when computational speed is prioritized. The FLARE framework for machine-learning interatomic potentials, for example, maps atomic environments to descriptors and uses Gaussian process regression, a kernelized Bayesian extension of ridge regression, to predict energies and forces on the fly during molecular dynamics.