Kernel Selection and Design

Choosing the right kernel function is one of the most consequential decisions in kernel-based machine learning. The kernel defines the similarity structure of your feature space, determining what patterns your model can learn and how effectively it generalizes to unseen data.

Unlike hyperparameters that can be tuned through cross-validation, kernel selection requires understanding the mathematical properties that different kernel families possess and how these properties align with the structure of your problem domain.

A kernel function $k(\mathbf{x}, \mathbf{x}')$ implicitly defines a mapping $\phi: \mathcal{X} \rightarrow \mathcal{H}$ to a reproducing kernel Hilbert space (RKHS), where:

$$k(\mathbf{x}, \mathbf{x}') = \langle \phi(\mathbf{x}), \phi(\mathbf{x}') \rangle_{\mathcal{H}}$$

The choice of kernel fundamentally determines:

1. The function class — What types of functions can be represented in the RKHS
2. The smoothness assumptions — How rapidly functions can vary
3. The similarity metric — What makes two inputs "close" in feature space
4. The generalization behavior — How the model interpolates and extrapolates

Mercer's Theorem Revisited:

Recall that a function $k: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$ is a valid (positive semi-definite) kernel if and only if for any finite set of points ${\mathbf{x}_1, \ldots, \mathbf{x}n}$, the Gram matrix $K{ij} = k(\mathbf{x}_i, \mathbf{x}_j)$ is positive semi-definite.

This requirement ensures the existence of the feature map $\phi$ and guarantees that kernel-based optimization problems (like kernel ridge regression or SVM) are convex and have unique solutions.

The polynomial kernel family models functions that depend on polynomial interactions between input features. These kernels are particularly suited for problems where the target function is well-approximated by polynomial functions of the input.

Homogeneous Polynomial Kernel:

$$k(\mathbf{x}, \mathbf{x}') = (\mathbf{x}^\top \mathbf{x}')^d$$

Inhomogeneous Polynomial Kernel:

$$k(\mathbf{x}, \mathbf{x}') = (\mathbf{x}^\top \mathbf{x}' + c)^d$$

where $d \in \mathbb{N}$ is the polynomial degree and $c \geq 0$ is a constant that trades off the influence of higher-order versus lower-order terms.

Mathematical Analysis of Feature Space:

For the inhomogeneous kernel with $d=2$ and $c=1$:

$$k(\mathbf{x}, \mathbf{x}') = (\mathbf{x}^\top \mathbf{x}' + 1)^2 = \sum_{i,j} x_i x_j x'_i x'_j + 2\sum_i x_i x'_i + 1$$

The implicit feature map includes:

• A constant term (bias)
• Linear terms $\sqrt{2} x_i$
• Squared terms $x_i^2$
• Cross terms $\sqrt{2} x_i x_j$ for $i eq j$

When to Use Polynomial Kernels:

• NLP tasks with bag-of-words representations (models word co-occurrences)
• Problems with known polynomial structure
• When explicit feature computation is desired (finite-dimensional embedding)
• Image classification with histogram features

The Radial Basis Function (RBF) kernel, also known as the Gaussian kernel or squared exponential kernel, is the most widely used kernel in practice due to its flexibility and universal approximation properties.

RBF Kernel Definition:

$$k(\mathbf{x}, \mathbf{x}') = \exp\left(-\frac{|\mathbf{x} - \mathbf{x}'|^2}{2\ell^2}\right) = \exp\left(-\gamma |\mathbf{x} - \mathbf{x}'|^2\right)$$

where $\ell > 0$ is the length-scale parameter and $\gamma = \frac{1}{2\ell^2}$ is the inverse squared length-scale.

The kernel value depends only on the Euclidean distance between points, making it stationary (translation-invariant) and isotropic (rotation-invariant).

The Length-Scale Parameter $\ell$:

The length-scale $\ell$ is the most critical hyperparameter, controlling the smoothness and locality of the kernel:

• Large $\ell$ (small $\gamma$): Distant points remain correlated; the resulting function is very smooth, varying slowly. Risk of underfitting.

• Small $\ell$ (large $\gamma$): Only nearby points are correlated; the function can vary rapidly. Risk of overfitting to noise.

Spectral Analysis:

By the Bochner's theorem, any stationary kernel can be written as the Fourier transform of a spectral density. For the RBF kernel:

$$k(\mathbf{x} - \mathbf{x}') = \int p(\boldsymbol{\omega}) e^{i\boldsymbol{\omega}^\top(\mathbf{x} - \mathbf{x}')} d\boldsymbol{\omega}$$

where $p(\boldsymbol{\omega})$ is a Gaussian spectral density. This means the RBF kernel places most weight on low-frequency components, explaining its smoothness preference.

Automatic Relevance Determination (ARD):

The standard RBF kernel uses a single $\ell$ for all input dimensions. The ARD variant uses dimension-specific length-scales:

$$k(\mathbf{x}, \mathbf{x}') = \exp\left(-\sum_{d=1}^{D} \frac{(x_d - x'_d)^2}{2\ell_d^2}\right)$$

When optimized (e.g., via marginal likelihood), dimensions with large $\ell_d$ contribute little to similarity—the kernel effectively performs automatic feature selection. This is particularly valuable in high-dimensional problems where many features may be irrelevant.

The Matérn family of kernels provides a flexible spectrum between very rough and infinitely smooth functions, parameterized by a smoothness parameter $ u$. This makes Matérn kernels more versatile than the RBF kernel, which is fixed at infinite smoothness.

General Matérn Kernel:

$$k(r) = \frac{2^{1- u}}{\Gamma( u)} \left(\frac{\sqrt{2 u} r}{\ell}\right)^{ u} K_{ u}\left(\frac{\sqrt{2 u} r}{\ell}\right)$$

where $r = |\mathbf{x} - \mathbf{x}'|$, $\ell$ is the length-scale, $ u > 0$ is the smoothness parameter, $\Gamma$ is the gamma function, and $K_{ u}$ is the modified Bessel function of the second kind.

Special Cases with Closed Forms:

Matérn-1/2 (Exponential/Ornstein-Uhlenbeck): $$k(r) = \exp\left(-\frac{r}{\ell}\right)$$

Samples are continuous but not differentiable—appropriate for rough, jagged functions.

Matérn-3/2: $$k(r) = \left(1 + \frac{\sqrt{3}r}{\ell}\right) \exp\left(-\frac{\sqrt{3}r}{\ell}\right)$$

Samples are once differentiable—a good default for many physical phenomena.

Matérn-5/2: $$k(r) = \left(1 + \frac{\sqrt{5}r}{\ell} + \frac{5r^2}{3\ell^2}\right) \exp\left(-\frac{\sqrt{5}r}{\ell}\right)$$

Samples are twice differentiable—smooth but not excessively so.

Why Matérn Kernels Matter in Practice:

1. Physical realism: Many real-world processes (temperature fields, terrain, economic indicators) are continuous but not infinitely smooth. Matérn captures this accurately.

2. Better uncertainty quantification: The RBF kernel's infinite smoothness can lead to overconfident predictions between data points. Matérn provides more realistic uncertainty estimates.

3. Computational advantages: Matérn-3/2 and 5/2 have sparse precision matrices (inverses of covariance matrices) in certain discretization schemes, enabling efficient computation.

4. Interpretable hyperparameters: The smoothness parameter $ u$ has a clear physical interpretation, unlike the arbitrary choice of RBF.

When data exhibits periodic patterns—daily temperature cycles, seasonal sales, weekly website traffic—standard stationary kernels fail to capture this structure. Periodic kernels encode the assumption that the function repeats with a known or learnable period.

Standard Periodic Kernel:

$$k(\mathbf{x}, \mathbf{x}') = \exp\left(-\frac{2\sin^2(\pi|x - x'|/p)}{\ell^2}\right)$$

where $p$ is the period and $\ell$ is the length-scale within each period.

Locally Periodic Kernel:

Real-world periodic phenomena rarely maintain exact periodicity. The locally periodic kernel combines periodic structure with slow drift:

$$k(\mathbf{x}, \mathbf{x}') = \underbrace{\exp\left(-\frac{2\sin^2(\pi|x - x'|/p)}{\ell_p^2}\right)}{\text{periodic component}} \times \underbrace{\exp\left(-\frac{(x - x')^2}{2\ell{se}^2}\right)}_{\text{secular trend}}$$

This kernel captures patterns that are periodic in the short term but can evolve over longer timescales.

Multivariate Periodic Extensions:

For multiple input dimensions with potentially different periods:

$$k(\mathbf{x}, \mathbf{x}') = \exp\left(-2\sum_{d=1}^{D}\frac{\sin^2(\pi|x_d - x'_d|/p_d)}{\ell_d^2}\right)$$

Spectral mixture kernels represent a powerful, expressive approach to kernel design based on Bochner's theorem: any stationary kernel can be represented as the Fourier transform of a positive spectral density.

The key insight is that instead of hand-crafting kernels, we can parameterize the spectral density and let the data determine the optimal frequency content.

Spectral Mixture Kernel (Wilson & Adams, 2013):

$$k(\tau) = \sum_{q=1}^{Q} w_q \exp\left(-2\pi^2 \tau^2 v_q\right) \cos(2\pi \tau \mu_q)$$

where $\tau = |\mathbf{x} - \mathbf{x}'|$, and for each mixture component $q$:

• $w_q \geq 0$: weight (contribution of this frequency band)
• $\mu_q$: mean frequency (center of this spectral peak)
• $v_q$: variance (width of this spectral peak)

Interpretation of Components:

Each mixture component $(w_q, \mu_q, v_q)$ corresponds to a bandpass filter in the frequency domain:

• Low $\mu_q$ with high $v_q$: Captures smooth, slowly-varying trends (like RBF)
• High $\mu_q$ with low $v_q$: Captures sharply-defined periodic components
• Multiple components: Can capture complex patterns with multiple characteristic frequencies

Learning Spectral Parameters:

The parameters $(w_q, \mu_q, v_q)$ can be optimized via marginal likelihood maximization. The gradients are tractable, making this amenable to gradient-based optimization.

Initialization Strategy:

A common approach is to initialize $\mu_q$ values from the empirical periodogram of the data, placing components at peaks in the estimated power spectrum.

Selecting the right kernel family is about matching mathematical properties to problem structure. Here's a consolidated decision framework: