12.3 The Kernel Trick for Regression

Introduction

The kernel trick extends beyond classification to regression problems. Kernel methods allow us to perform non-linear regression efficiently by working in high-dimensional feature spaces without explicit computation of transformations.

1. From Linear to Kernel Ridge Regression

1.1 Linear Ridge Regression

Ridge regression minimizes:

$$\min_{\mathbf{w}} \sum_{i=1}^{n} (y_i - \mathbf{w}^T \mathbf{x}_i)^2 + \lambda \|\mathbf{w}\|^2$$

The solution is:

$$\mathbf{w}^* = (\mathbf{X}^T\mathbf{X} + \lambda \mathbf{I})^{-1}\mathbf{X}^T\mathbf{y}$$

where $\mathbf{X}$ is the $n \times d$ data matrix.

1.2 Dual Representation

By the representer theorem, the solution can be written as:

$$\mathbf{w}^* = \sum_{i=1}^{n} \alpha_i \mathbf{x}_i = \mathbf{X}^T \boldsymbol{\alpha}$$

Substituting back and solving for $\boldsymbol{\alpha}$:

$$\boldsymbol{\alpha} = (\mathbf{K} + \lambda \mathbf{I})^{-1}\mathbf{y}$$

where $\mathbf{K} = \mathbf{X}\mathbf{X}^T$ is the $n \times n$ Gram matrix with $K_{ij} = \mathbf{x}_i^T \mathbf{x}_j$.

1.3 Prediction

For a new point $\mathbf{x}$:

$$f(\mathbf{x}) = \mathbf{w}^{*T}\mathbf{x} = \sum_{i=1}^{n} \alpha_i \mathbf{x}_i^T \mathbf{x} = \sum_{i=1}^{n} \alpha_i k(\mathbf{x}_i, \mathbf{x})$$

This depends only on inner products, enabling the kernel trick!

2. Kernel Ridge Regression (KRR)

Replace inner products with a kernel function $k(\mathbf{x}, \mathbf{z})$:

$$K_{ij} = k(\mathbf{x}_i, \mathbf{x}_j)$$

The solution is:

$$\boldsymbol{\alpha} = (\mathbf{K} + \lambda \mathbf{I})^{-1}\mathbf{y}$$

Predictions:

$$f(\mathbf{x}) = \sum_{i=1}^{n} \alpha_i k(\mathbf{x}_i, \mathbf{x}) = \mathbf{k}(\mathbf{x})^T \boldsymbol{\alpha}$$

where $\mathbf{k}(\mathbf{x}) = [k(\mathbf{x}_1, \mathbf{x}), \ldots, k(\mathbf{x}_n, \mathbf{x})]^T$.

Kernel Function Gallery & Gram Matrix Explorer

Interactively explore how different kernels and their hyperparameters shape the Gram (kernel) matrix, its eigen spectrum (capturing implicit feature space energy), and positive semi-definiteness properties.

3. Computational Aspects

3.1 Complexity

• Training: $O(n^2 d + n^3)$
  • $O(n^2 d)$ to compute kernel matrix
  • $O(n^3)$ to solve linear system
• Prediction: $O(nd)$ per test point
• Space: $O(n^2)$ to store kernel matrix

3.2 Efficient Solutions

For large $n$, use:

• Cholesky decomposition: $\mathbf{K} + \lambda\mathbf{I} = \mathbf{L}\mathbf{L}^T$
• Conjugate gradient: Iterative solver, no matrix inversion
• Nyström approximation: Low-rank approximation of $\mathbf{K}$
• Random features: Explicit feature map approximation

4. Gaussian Processes Basics

Gaussian Processes (GPs) provide a probabilistic interpretation of kernel regression.

4.1 Definition

A GP is a collection of random variables, any finite number of which have a joint Gaussian distribution:

$$f(\mathbf{x}) \sim \mathcal{GP}(m(\mathbf{x}), k(\mathbf{x}, \mathbf{x}'))$$

where:

• $m(\mathbf{x}) = \mathbb{E}[f(\mathbf{x})]$ is the mean function (often 0)
• $k(\mathbf{x}, \mathbf{x}') = \mathbb{E}[(f(\mathbf{x}) - m(\mathbf{x}))(f(\mathbf{x}') - m(\mathbf{x}'))]$ is the covariance (kernel) function

4.2 GP Regression

Given training data $\mathcal{D} = \{(\mathbf{x}_i, y_i)\}_{i=1}^{n}$ with noisy observations:

$$y_i = f(\mathbf{x}_i) + \epsilon_i, \quad \epsilon_i \sim \mathcal{N}(0, \sigma^2)$$

The posterior distribution at a test point $\mathbf{x}_*$ is Gaussian:

$$f(\mathbf{x}_*) | \mathcal{D} \sim \mathcal{N}(\mu_*, \sigma_*^2)$$

where:

$$\mu_* = \mathbf{k}_*^T (\mathbf{K} + \sigma^2\mathbf{I})^{-1} \mathbf{y}$$

$$\sigma_*^2 = k(\mathbf{x}_*, \mathbf{x}_*) - \mathbf{k}_*^T (\mathbf{K} + \sigma^2\mathbf{I})^{-1} \mathbf{k}_*$$

Note: The mean $\mu_*$ is identical to kernel ridge regression with $\lambda = \sigma^2$!

4.3 Predictive Uncertainty

GPs provide uncertainty estimates with predictions:

• Mean $\mu_*$ gives point prediction
• Variance $\sigma_*^2$ quantifies uncertainty
• 95% confidence interval: $[\mu_* - 1.96\sigma_*, \mu_* + 1.96\sigma_*]$

5. Kernel Choice for Regression

5.1 Squared Exponential (RBF)

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

Parameters: $\sigma_f^2$ (signal variance), $\ell$ (length scale). Infinitely differentiable, smooth functions.

5.2 Matérn Kernel

$$k(\mathbf{x}, \mathbf{x}') = \sigma_f^2 \frac{2^{1-\nu}}{\Gamma(\nu)} \left(\frac{\sqrt{2\nu}r}{\ell}\right)^\nu K_\nu\left(\frac{\sqrt{2\nu}r}{\ell}\right)$$

where $r = \|\mathbf{x} - \mathbf{x}'\|$, $\nu$ controls smoothness. More flexible than RBF.

5.3 Rational Quadratic

$$k(\mathbf{x}, \mathbf{x}') = \sigma_f^2 \left(1 + \frac{\|\mathbf{x} - \mathbf{x}'\|^2}{2\alpha \ell^2}\right)^{-\alpha}$$

Mixture of RBF kernels with different length scales.

5.4 Periodic Kernel

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

For periodic functions with period $p$.

6. Hyperparameter Learning

Kernel hyperparameters $\boldsymbol{\theta}$ (e.g., $\ell$, $\sigma_f$) significantly affect performance.

6.1 Maximum Likelihood

For GPs, maximize the marginal log-likelihood:

$$\log p(\mathbf{y}|\mathbf{X}, \boldsymbol{\theta}) = -\frac{1}{2}\mathbf{y}^T (\mathbf{K} + \sigma^2\mathbf{I})^{-1}\mathbf{y} - \frac{1}{2}\log|\mathbf{K} + \sigma^2\mathbf{I}| - \frac{n}{2}\log(2\pi)$$

Optimize using gradient descent. Gradients can be computed efficiently.

6.2 Cross-Validation

Alternatively, select $\boldsymbol{\theta}$ by cross-validation:

1. Define grid of hyperparameter values
2. For each combination, compute CV error
3. Select hyperparameters with lowest CV error

7. Sparse Approximations

For large datasets, exact kernel methods become intractable. Sparse approximations reduce complexity.

7.1 Nyström Method

Approximate $\mathbf{K}$ using $m \ll n$ inducing points:

$$\mathbf{K} \approx \mathbf{K}_{nm}\mathbf{K}_{mm}^{-1}\mathbf{K}_{mn}$$

Reduces complexity from $O(n^3)$ to $O(nm^2)$.

7.2 Subset of Regressors

Use only $m$ selected training points for prediction. Simple but can lose information.

7.3 Random Fourier Features

For shift-invariant kernels, approximate with explicit features:

$$k(\mathbf{x}, \mathbf{z}) \approx \mathbf{z}(\mathbf{x})^T \mathbf{z}(\mathbf{z})$$

where $\mathbf{z}(\mathbf{x})$ is a $D$-dimensional random feature map. Enables linear methods with kernel performance.

8. Multi-output Regression

Extend to multiple outputs $\mathbf{y} = [y^{(1)}, \ldots, y^{(m)}]$:

Use a matrix-valued kernel or coregionalization model that captures output correlations.

9. Connection to LLMs

Kernel methods and GPs relate to modern language models:

• Neural Tangent Kernel: Infinite-width neural networks behave as GPs with specific kernels
• Attention as kernel: Attention mechanism computes kernel-weighted predictions
• Uncertainty quantification: GP-inspired methods add uncertainty to neural predictions
• Bayesian neural networks: Combine neural architectures with Bayesian inference like GPs
• Meta-learning: Few-shot learning in LLMs similar to GP adaptation with few points
• Kernel embeddings: Word embeddings create implicit kernel spaces
• Contextual bandits: GP-based exploration strategies for reinforcement learning from human feedback

10. Practical Considerations

Advantages

• Closed-form solutions (no local minima)
• Uncertainty quantification (GPs)
• Flexible function approximation
• Automatic smoothness control
• Works well with small to medium data

Disadvantages

• $O(n^3)$ training complexity
• $O(n^2)$ memory for kernel matrix
• Challenging for very high dimensions
• Hyperparameter selection critical
• Limited scalability to massive datasets

Key Takeaways

• Kernel ridge regression extends linear regression to non-linear settings
• Dual formulation enables kernel trick: work with inner products
• Gaussian processes provide probabilistic interpretation with uncertainty
• GP prediction mean equals kernel ridge regression
• Kernel choice encodes assumptions about function smoothness
• Hyperparameters must be carefully selected via ML or CV
• Sparse methods enable scaling to larger datasets
• Connection to neural networks via Neural Tangent Kernel