Kernel Ridge Regression

We've derived the dual formulation and studied the kernel matrix. Now comes the moment of truth: How do we use the trained model to make predictions on new, unseen data?

In kernel ridge regression, prediction takes a remarkably elegant form. Rather than explicitly computing weights in a high-dimensional feature space, we express predictions as weighted combinations of kernel evaluations between the test point and training points. This not only avoids the computational burden of feature space but also provides rich geometric and probabilistic interpretations.

This page explores prediction in depth—from the basic formula to sophisticated interpretations that connect kernel ridge regression to smoothing, interpolation, and Gaussian processes.

Given a new test point $\mathbf{x}_*$, the kernel ridge regression prediction is:

$$f(\mathbf{x}) = \mathbf{w}^{\top} \phi(\mathbf{x}*)$$

Using the representer theorem ($\mathbf{w}^* = \sum_{i=1}^n \alpha_i^* \phi(\mathbf{x}_i)$), this becomes:

Substituting the solution for $\boldsymbol{\alpha}^*$:

$$f(\mathbf{x}*) = \mathbf{k}*^\top (\mathbf{K} + \lambda\mathbf{I})^{-1} \mathbf{y}$$

Breaking Down the Components:

1. Kernel vector $\mathbf{k}_*$: Measures similarity between $\mathbf{x}*$ and each training point. Points with high similarity to $\mathbf{x}*$ will have larger kernel values.

2. Regularized inverse $(\mathbf{K} + \lambda\mathbf{I})^{-1}$: Transforms the kernel vector accounting for:

   • Dependencies between training points (captured by $\mathbf{K}$)
   • Regularization strength (captured by $\lambda$)
   • This is the "correlation-aware" transformation

3. Target vector $\mathbf{y}$: The training targets we aim to predict

Computational Flow:

1. Training (once):      Compute K, solve (K + λI)α = y for α
2. Prediction (per x*):  Compute k*, return k*ᵀα

After training, predictions require only $O(n)$ kernel evaluations and an $O(n)$ dot product per test point.

Understanding predictions geometrically deepens our intuition about what kernel ridge regression computes.

The Feature Space View:

Recall that the kernel corresponds to an inner product in feature space: $$k(\mathbf{x}, \mathbf{x}') = \langle \phi(\mathbf{x}), \phi(\mathbf{x}') \rangle$$

The prediction formula becomes: $$f(\mathbf{x}) = \langle \mathbf{w}^, \phi(\mathbf{x}*) \rangle$$

This is a linear function in feature space—the inner product of the learned weight vector with the test point's feature representation.

Interpretation:

• $\phi(\mathbf{x}_*)$ is a vector in feature space $\mathcal{H}$
• $\mathbf{w}^*$ is another vector in $\mathcal{H}$ (the model)
• The prediction is the projection of $\phi(\mathbf{x}_)$ onto $\mathbf{w}^$

Even when $\mathcal{H}$ is infinite-dimensional, this inner product is well-defined and computable via the kernel.

Understanding Through the Kernel Trick:

$$f(\mathbf{x}) = \langle \mathbf{w}^, \phi(\mathbf{x}) \rangle = \left\langle \sum_{i=1}^n \alpha_i^ \phi(\mathbf{x}i), \phi(\mathbf{x}*) \right\rangle$$

$$= \sum_{i=1}^n \alpha_i^* \langle \phi(\mathbf{x}i), \phi(\mathbf{x}) \rangle = \sum_{i=1}^n \alpha_i^ k(\mathbf{x}i, \mathbf{x}*)$$

Each training point $i$ contributes $\alpha_i^* k(\mathbf{x}i, \mathbf{x}*)$ to the prediction:

• $\alpha_i^*$: the "importance" of point $i$ determined by training
• $k(\mathbf{x}i, \mathbf{x}*)$: similarity between training point $i$ and test point

Similarity-Weighted Voting:

Think of prediction as each training point "voting" for a value, with votes weighted by:

1. How important that training point is (captured in $\alpha_i^*$)
2. How similar the test point is to that training point (captured in $k(\mathbf{x}i, \mathbf{x}*)$)

When predicting at training points, the predictions take a special form that reveals important structure.

Definition:

The smoother matrix (or hat matrix) $\mathbf{H}$ is defined as: $$\mathbf{H} = \mathbf{K}(\mathbf{K} + \lambda\mathbf{I})^{-1}$$

The vector of predictions at training points is: $$\hat{\mathbf{y}} = \mathbf{K}\boldsymbol{\alpha}^* = \mathbf{K}(\mathbf{K} + \lambda\mathbf{I})^{-1}\mathbf{y} = \mathbf{H}\mathbf{y}$$

The name "hat matrix" comes from putting a "hat" on $\mathbf{y}$ to get predictions: $\hat{\mathbf{y}} = \mathbf{H}\mathbf{y}$.

Interpretation as Smoothing:

The smoother matrix transforms targets $\mathbf{y}$ into predictions $\hat{\mathbf{y}}$. This transformation:

1. Shrinks amplitudes: Eigenvalues of $\mathbf{H}$ are in $[0, 1)$, so $|\hat{\mathbf{y}}| \leq |\mathbf{y}|$

2. Filters high-frequency components: Small eigenvalues of $\mathbf{K}$ (corresponding to "noisy" directions) are heavily suppressed by the ratio $\lambda_i / (\lambda_i + \lambda)$

3. Preserves low-frequency components: Large eigenvalues of $\mathbf{K}$ (corresponding to "smooth" patterns) are nearly preserved

The Degrees of Freedom:

$$\text{df}(\lambda) = \text{trace}(\mathbf{H}) = \sum_{i=1}^n \frac{\lambda_i(\mathbf{K})}{\lambda_i(\mathbf{K}) + \lambda}$$

This measures the effective model complexity:

• df → n as $\lambda \to 0$ (complex, interpolating model)
• df → 0 as $\lambda \to \infty$ (simple, shrunk model)

The degrees of freedom is crucial for model comparison and cross-validation.

The regularization parameter $\lambda$ controls the fundamental trade-off between fitting the data exactly and producing smooth predictions.

Limit Case 1: Pure Interpolation (λ → 0)

As $\lambda \to 0$: $$\boldsymbol{\alpha}^* \to \mathbf{K}^{-1}\mathbf{y}$$ $$\mathbf{H} \to \mathbf{I}$$

Predictions at training points become $\hat{\mathbf{y}} = \mathbf{y}$—exact interpolation. The model passes exactly through each training point.

Consequences of interpolation:

• Zero training error
• Maximum complexity (df = n)
• Sensitive to noise (each yᵢ is perfectly reproduced, including noise)
• Potentially poor generalization
• Numerically problematic if K is ill-conditioned

Limit Case 2: Maximum Smoothing (λ → ∞)

As $\lambda \to \infty$: $$\boldsymbol{\alpha}^* \to \mathbf{0}$$ $$\mathbf{H} \to \mathbf{0}$$

Predictions become $\hat{\mathbf{y}} \to \mathbf{0}$—the trivial zero function.

Consequences of over-smoothing:

• High training error (model ignores the data)
• Minimum complexity (df → 0)
• Underfitting: fails to capture any structure
• Numerically trivial but useless

The Goldilocks Zone:

Optimal $\lambda$ balances these extremes:

• Small enough $\lambda$: captures genuine patterns in the data
• Large enough $\lambda$: filters out noise and ensures stability

Kernel ridge regression shares deep connections with local regression methods like LOESS (Local Regression) and Nadaraya-Watson estimation.

The Nadaraya-Watson Estimator:

A classical nonparametric regression estimator: $$f(\mathbf{x}*) = \frac{\sum{i=1}^n K_h(\mathbf{x}*, \mathbf{x}i) y_i}{\sum{i=1}^n K_h(\mathbf{x}*, \mathbf{x}_i)}$$

where $K_h$ is a kernel with bandwidth $h$.

Comparison with Kernel Ridge Regression:

Key Difference: Correlation Correction

Nadaraya-Watson uses raw kernel weights: $$w_i^{NW}(\mathbf{x}_) \propto k(\mathbf{x}i, \mathbf{x})$$

Kernel ridge regression uses correlation-corrected weights: $$w_i^{KRR}(\mathbf{x}*) = [(\mathbf{K} + \lambda\mathbf{I})^{-1}\mathbf{k}*]_i$$

The $(\mathbf{K} + \lambda\mathbf{I})^{-1}$ factor accounts for the fact that training points are correlated. If multiple training points are close together, they shouldn't each get full weight—they're providing redundant information.

Example:

Consider 10 training points clustered near $x = 0$ and 1 isolated point at $x = 5$:

• Nadaraya-Watson at $x = 4$: Dominated by the cluster (10× more weight)
• Kernel ridge at $x = 4$: Gives more weight to the isolated point (recognizes cluster points are redundant)

Kernel ridge regression produces more sensible extrapolation due to this correlation correction.

While kernel ridge regression gives point predictions, we often want confidence intervals or uncertainty estimates. There are several approaches.

1. Frequentist Confidence Intervals:

Under the assumption that $y_i = f(\mathbf{x}_i) + \epsilon_i$ with $\epsilon_i \sim \mathcal{N}(0, \sigma^2)$ i.i.d., the prediction at a new point has variance:

$$\text{Var}(f(\mathbf{x}*)) = \sigma^2 \mathbf{k}^\top (\mathbf{K} + \lambda\mathbf{I})^{-2} \mathbf{k}_$$

The noise variance $\sigma^2$ can be estimated from residuals: $$\hat{\sigma}^2 = \frac{|\mathbf{y} - \hat{\mathbf{y}}|^2}{n - \text{trace}(\mathbf{H})}$$

A $(1-\alpha)$ confidence interval is approximately: $$f(\mathbf{x}*) \pm z{\alpha/2} \cdot \hat{\sigma} \sqrt{\mathbf{k}*^\top (\mathbf{K} + \lambda\mathbf{I})^{-2} \mathbf{k}*}$$

2. Bootstrap Confidence Intervals:

A non-parametric approach:

1. Resample training data with replacement: $(\mathbf{X}^{(b)}, \mathbf{y}^{(b)})$
2. Refit kernel ridge regression to get $\boldsymbol{\alpha}^{(b)}$
3. Compute prediction $f^{(b)}(\mathbf{x}_*)$
4. Repeat $B$ times (typically $B = 1000$)
5. Use percentiles of ${f^{(b)}(\mathbf{x}_*)}$ as confidence bounds

3. Influence-Based Uncertainty:

Points with low similarity to training data should have higher uncertainty. A simple measure: $$\text{uncertainty}(\mathbf{x}_) \propto \frac{1}{\sum_i k(\mathbf{x}i, \mathbf{x})}$$

This is high when $\mathbf{x}_*$ is far from all training points.

4. Ensemble Methods:

Train multiple models with different:

• Regularization parameters
• Kernel hyperparameters
• Random subsets of training data

Variance across ensemble predictions estimates uncertainty.

In practice, we often need predictions for many test points $\mathbf{x}_1^, \ldots, \mathbf{x}_m^$. Efficiency matters.

Naive Approach:

For each test point independently:

1. Compute $\mathbf{k}_j^* = (k(\mathbf{x}_1, \mathbf{x}_j^), \ldots, k(\mathbf{x}_n, \mathbf{x}_j^))^\top$
2. Return $f(\mathbf{x}_j^) = \mathbf{k}_j^{\top} \boldsymbol{\alpha}^*$

Cost: $O(mn)$ kernel evaluations + $O(mn)$ for dot products = $O(mn)$ total

Matrix Form:

Define the test kernel matrix $\mathbf{K}* \in \mathbb{R}^{n \times m}$: $$(K)_{ij} = k(\mathbf{x}_i, \mathbf{x}_j^)$$

Then all predictions are: $$\mathbf{f}^* = \mathbf{K}_^\top \boldsymbol{\alpha}^ \in \mathbb{R}^m$$

This is a single matrix-vector product, enabling efficient batch prediction.

Optimization Strategies:

1. Precompute and cache $(\mathbf{K} + \lambda\mathbf{I})^{-1}$:

If predictions at training points or leave-one-out evaluations are needed, storing the full inverse (or its Cholesky factor) can save time.

2. Online prediction updates:

For streaming test data, incrementally compute kernel values and predictions without reforming $\mathbf{K}_*$.

3. Approximate nearest neighbor search:

For local kernels (like RBF), only nearby training points contribute significantly. Use KD-trees or ball trees to find the $k$ nearest training points and compute only those kernel values.

4. Low-rank approximations:

If $\mathbf{K} \approx \mathbf{U}\mathbf{U}^\top$ with $\mathbf{U} \in \mathbb{R}^{n \times r}$ ($r << n$), then: $$\boldsymbol{\alpha}^* \approx (\mathbf{U}\mathbf{U}^\top + \lambda\mathbf{I})^{-1}\mathbf{y}$$

Using Woodbury identity, this reduces to an $r \times r$ system. Prediction becomes $O(r)$ per test point. (Covered in Module 5.)

We've comprehensively explored how predictions work in kernel ridge regression. Let's consolidate the key insights:

What's Next:

With prediction mechanics understood, we turn to Computational Complexity. We'll analyze:

• Detailed complexity analysis of training and prediction
• When kernel methods become prohibitively expensive
• The n³ bottleneck and strategies to mitigate it
• Memory considerations for large-scale problems
• Trade-offs between exact and approximate methods