Lecture 32 · Regression: non-linear relationships

Kernel Regression

What if the label depends on the features non-linearly, through terms like height² or height × weight? Use the same trick as kernel PCA: map the data to a richer feature space and do linear regression there, but write everything in terms of dot products so a kernel can stand in for the mapping.

Source: this lecture on YouTube (≈19 min). Previous: L31 · Next: L33.

1 · The problem with linear

If the true relationship is something like height² + 3·weight − weight², or contains a cross term like height × weight, linear regression can't capture it. Even the best $w$ makes large errors. Kernel PCA solved the same issue for PCA by working only with dot products between data points and replacing them with a kernel $k(x,x')=\phi(x)^\top\phi(x')$. The goal here is the same: express regression through dot products.

2 · Key fact: w* lies in the span of the data points

Suppose some optimal $w^\star$ pokes outside the span of the data. Split it into a part inside the span, $\tilde w$, and a part perpendicular to it, $w_\perp$. The perpendicular part has zero dot product with every data point, so

$$w^{\star\top}x_i=\tilde w^\top x_i+\underbrace{w_\perp^\top x_i}_{0}=\tilde w^\top x_i\quad\text{for every }i .$$

So $\tilde w$ makes exactly the same predictions and has the same error. We can always use a solution inside the span, which means $w^\star$ is a weighted combination of the data points:

$$w^\star=X\alpha^\star=\sum_{i=1}^{n}\alpha^\star_i\,x_i,\qquad \alpha^\star\in\mathbb R^n .$$

3 · Solving for α in terms of dot products

Combine with L29's solution: $\;X\alpha^\star=(XX^\top)^{+}Xy$.
Multiply both sides by $XX^\top$, which cancels the pseudo-inverse: $\;XX^\top X\alpha^\star=Xy$.
Multiply both sides by $X^\top$: $\;(X^\top X)(X^\top X)\alpha^\star=(X^\top X)\,y$.
$X^\top X$ is the $n\times n$ matrix of dot products between data points, the kernel matrix $K$. So $K^2\alpha^\star=Ky$, and if $K$ is invertible, $\;\boxed{\alpha^\star=K^{-1}y}$.

Now replace the plain dot products with a kernel, $K_{ij}=k(x_i,x_j)=\phi(x_i)^\top\phi(x_j)$. That's linear regression on the mapped points $\phi(x_i)$, without ever computing $\phi$.

4 · Predicting a new point

For a test point, the prediction would be $w^{\star\top}\phi(x_{\text{test}})$. But $w^\star=\sum_i\alpha^\star_i\phi(x_i)$, so

$$\boxed{\;\hat y(x_{\text{test}})=\sum_{i=1}^{n}\alpha^\star_i\;k(x_i,\,x_{\text{test}})\;}$$

$k(x_i,x_{\text{test}})$: how similar the test point is to training point $i$.
$\alpha^\star_i$: how important training point $i$ is to the solution.
The prediction adds up similarity × importance over all training points. A test point close to an unimportant training point doesn't get much from it.

The algorithm: (1) build the $n\times n$ kernel matrix $K$; (2) compute $\alpha^\star=K^{-1}y$; (3) predict with $\sum_i\alpha^\star_i k(x_i,x)$. Choose any kernel: polynomial (quadratic, cubic, …), Gaussian (RBF), etc. Unlike kernel PCA, the labels $y$ come in here.

20 noisy training points from a curved relationship. Each kernel gives a different family of fitted curves. Grey dots are fresh test points from the same process.

use (K + λI)⁻¹y with λ = 0.1 instead of K⁻¹y

–

training error (avg squared)

–

test error

training pointstest points

Two implementation notes, going beyond the video. (1) With a polynomial kernel, $K$ has low rank and isn't invertible, so the demo uses the pseudo-inverse $K^{+}$, the least-norm solution from L29. (2) With an RBF kernel, $K$ is invertible but nearly singular, so $\alpha=K^{-1}y$ fits every training point almost exactly, noise included, and the fitted curve can swing wildly elsewhere. That's the memorising problem from L28. The standard fix, tried in the demo, is to add a small amount to the diagonal: $(K+\lambda I)^{-1}y$ ("kernel ridge regression"), a form of regularisation the course covers later.

Key takeaways

Non-linear relationships need non-linear features. Kernels supply them implicitly.
The optimal $w^\star$ lies in the span of the data, $w^\star=X\alpha^\star$, so everything can be written with the kernel matrix $K$.
$\alpha^\star=K^{-1}y$, and the prediction is $\sum_i\alpha^\star_i\,k(x_i,x)$: similarity × importance.
Regression → kernel regression mirrors PCA → kernel PCA, with the labels added.