5.2 Kernel Ridge Regression

Ridge regression in a feature space, without building the features.

These notes walk through the lecture slides. The original deck is unchanged; use (slides) on the course hub if you want that PDF.

The figures follow Deisenroth, Faisal, and Ong, Mathematics for Machine Learning, Theodoridis, and Géron, Hands-On Machine Learning.

1. Kernel ridge regression

Regularized empirical risk in an RKHS is

{min}_{f \in ℍ} J (f) = \sum_{n = 1}^{N} ℒ (y_{n}, f (𝐱_{n})) + λ Ω (‖ f ‖^{2}) .

The regularizer $Ω (‖ f ‖^{2})$ is typically the squared RKHS norm $‖ f ‖^{2}$ .

2. Matrix notation

$𝐲$ : targets.
$𝐗$ : design matrix of inputs.
$𝐊$ : kernel matrix.

The regularizer becomes $λ θ^{⊤} 𝐊 θ$ , where $θ$ holds the coefficients in the RKHS expansion of $f$ .

3. Gradient

The finite-dimensional problem is

{min}_{θ} J (θ) = (𝐲 - 𝐊 θ)^{⊤} (𝐲 - 𝐊 θ) + λ θ^{⊤} 𝐊 θ .

Differentiate and set to zero:

\frac{\partial J (θ)}{\partial θ} = - 2 𝐊^{⊤} (𝐲 - 𝐊 θ) + 2 λ 𝐊 θ = 0 .

4. Solving for $θ$

𝐊^{⊤} 𝐊 θ - 𝐊^{⊤} 𝐲 + λ 𝐊 θ = 0,

(𝐊^{⊤} 𝐊 + λ 𝐈) θ = 𝐊^{⊤} 𝐲,

and

θ = (𝐊^{⊤} 𝐊 + λ 𝐈)^{- 1} 𝐊^{⊤} 𝐲 .

When $𝐊$ can be cancelled, the usual kernel-ridge form is

θ = (𝐊 + λ 𝐈)^{- 1} 𝐲 .

5. Predictions

With that $θ$ ,

\hat{𝐲} = 𝐊 θ .

The linear algebra is the same as ridge, but every inner product among features has been replaced by a kernel evaluation. The penalty still controls complexity and overfitting.

6. Practice

What does the kernel trick avoid computing?
Write the usual closed-form $θ$ for kernel ridge in terms of $𝐊$ , $λ$ , and $𝐲$ .
Once you have $θ$ , how do you form the vector of training predictions?

Ahmad Mousavi