Kernel Ridge Regression and Gaussian Processes

Background: Linear Regression

Consider that we have a dataset $\mathcal{D} = \{ (\mathbf x_i, y_i)\}_{i=1}^n$. We assume that

where $\mathbf v$ is the true function and $\epsilon \sim \mathcal{N}(0, \sigma^2_\epsilon)$. Then, we can construct the likelihood

Because $y \sim \mathcal{N}(\mathbf w^T\mathbf x, \sigma^2)$. The expected (empirical) log likelihood is the squared loss:

Taking derivative w.r.t $\mathbf w$ yields

Let $\mathbf X \in \reals^{n\times d} = (\mathbf x_1, \dots, \mathbf x_n)^T$ and $\mathbf y = (y_1, \dots, y_n)$ . The derivative is

Setting the derivative to zero yields

For ridge regression, which has an additional term (called regularizer), $\lambda \| \mathbf w \|_2^2$. The solution is

Nonlinear Regression with Kernel : Kernel Ridge Regression

Instead of using $\mathbf x \in \mathcal{X} \subseteq \reals^d$, we can consider transforming $\mathbf x$ into some feature space first. More precisely, we would like to find $\phi: \mathcal{X} \rightarrow \mathcal{H}$ . We then assume a model

Hence, the solution can be founded using the regularized least squared equation:

However, finding such $\phi(\mathbf x) \mapsto \mathcal{H}$ is not trivial. To overcome this, we instead find $\phi(\cdot)$ implicity through a kernel function $k: \mathcal X \times \mathcal X \rightarrow \reals_+$. Under technical conditions on $k$, it is known that

Consider a test sample $\mathbf x^*$ . The prediction is

Define $k_{\mathbf X}(\mathbf x^*):= \phi(\mathbf X) \phi(\mathbf x^*)$ and $\mathbf K = \phi(\mathbf{X})\phi(\mathbf{X})^T$. From the representer theorem, we also know that the solution $\mathbf w$ is the span of $k(\cdot, \mathbf x_i) \in \mathcal{H}, \forall i = [1, n]$. More precisely, it is in the following form:

Therefore, in other words, we have

where $\alpha^* = (\alpha_1, \dots, \alpha_n)$.

Fig. 1: Prediction from linear regression, kernel ridge regression, and Gaussian processes.

Gaussian Processes: Bayesian Kernel Regression

From Bayes' rule, we know that

In general, $p(\mathcal D) = \int p(\mathcal D | \mathbf w) p(\mathbf w) d\mathbf w$ is intractable. However, if we choose $p(\mathbf w)$ appropriately, the term can be computed analytically. In particular, in the case of regression (i.e. Gaussian likelihood), we can choose $p(\mathbf w) = \mathcal{N}(0, \sigma_w^2 I)$. Because Gaussian distributions are close under multiplication, the posterior distribution is also a Gaussian distribution. In this case, we have

where $\Sigma' = (\sigma^{-2}_\epsilon\mathbf X^T \mathbf X + \sigma^{-2}_wI_d)^{-1}$ and $\mu' = \sigma^{-2}_\epsilon \Sigma' \mathbf X \mathbf y$.

Let's consider using the feature map $\phi : \mathcal X \rightarrow \mathcal H$, we can rewrite $\mu' ,\Sigma'$ as

For linear regression with Gaussian prior (i.e. ridge regression), the predictive mean and variance are

Therefore, we have

Similarly, using the Sherman-Morrison-Woodbury formula, we have

In summary, we have

Fig. 2: linear regression and Gaussian processes trained with datasets with different sizes.

References

These are materials I consulted while writing this article:

• Tzu-Kuo Huang's A Technical Introduction to Gaussian Process Regression
• Chuong B. Do's Gaussian Processes

Figures are made using Google Colab.