2
$\begingroup$

Every presentation that I have seen for kernelized regression focuses on finding $$\underset{f \in \mathcal{H}_k}{\min} \sum_{i=1}^{n}(y_i-f(\mathbf{x}_i))^2+\lambda \|f\|^2_{\mathcal{H}_k}.$$ Here, $\mathcal{H}_k$ is a Reproducing kernel Hilbert space (RKHS).

I was wondering

  • Why the focus on ridge regression? Can we use other penalties here, or is there something about the ridge penalty that is natural in this setting?
  • Can we do un-penalized kernelized regression? Why is this not usually presented prior to kernel ridge regression?
$\endgroup$
3
  • 2
    $\begingroup$ RKHS has a structure that lends itself to Tikhonov regularization. There is a lack of motive for doing otherwise. $\endgroup$
    – Carl
    Nov 23, 2021 at 2:46
  • $\begingroup$ @Carl Could you elaborate on the first point? Also after some thought, I reasoned that no regularization wouldn't be good since there may be many $f$ in the RKHS that minimize the loss. The regularization term gives us a unique solution. Is my understanding correct? $\endgroup$ Nov 23, 2021 at 3:08
  • 1
    $\begingroup$ Perhaps your understanding is correct, however, I cannot entirely put myself in your thought process. OK try this, compare the Wikipedia link I put into your question with my Q/A on Tikhonov/ridge regression. Maybe that will allow you to verify your train of thought. $\endgroup$
    – Carl
    Nov 23, 2021 at 3:43

1 Answer 1

3
$\begingroup$

Great question!

Alternative Norms Exist (kind of): Though we call it "Kernel Ridge", let's take a second to note that the norm we're using is the RKHS norm (whereas regular "ridge regression" penalizes the $\ell_2$ norm of the parameter vector). One could consider a different function space norm to be penalized instead, like an $L_p$ norm. Alternatively, we could directly penalize the kernel coefficients, as in this article about kernel lasso. But yeah, what's so nice about the RKHS penalty is that its solution is available in closed form (from the Bayesian perspective, it is a conjugate prior to the normal likelihood). GPs wouldn't be nearly as popular if you needed to solve a nonlinear optimization program to use them. (but you often do anyways if you have enough kernel hyperparameters to estimate...)

Other Approaches than Penalties Exist (kind of): The reason we usually use regularization in kernel regression is because we have, in effect, an infinite dimensional parameter space, with one "column" associated with each possible input location: $k(\mathbf{x},.)$. Without regularization, there are not only infinitely many solutions which interpolate our data (which is possible in underdetermined, finite-dimensional regression), but indeed most of those solutions are made of infinitely many kernel functions $\hat{f}=\sum_{i=1}^\infty a_i k(\mathbf{x}_i,.)$. So we want some way of simplifying things. But it doesn't have to be a penalty per se. Usually we solve:

$$ \min_{f\in\mathcal{H}_k} \sum_{i=1}^N (f(\mathbf{x}_i)-y_i)^2+\lambda||f||_{\mathcal{H}_k} $$

which has solution given by $\alpha = (\mathbf{K}+\lambda \mathbf{I})^{-1}\mathbf{y}$ then $\hat{f}=\sum_{i=1}^N \alpha_i k(\mathbf{x}_i,.)$.

But instead of solving a penalized problem, we could instead solve this constrained one:

$$ \min_{f\in\mathcal{H}_k} ||f||_{\mathcal{H}_k}$$ $$\textrm{Such that:}$$ $$\sum_{i=1}^N (f(\mathbf{x}_i)-y_i)^2 = 0 $$

Which has solution given by $\alpha = (\mathbf{K})^{\dagger}\mathbf{y}$, where $\mathbf{A}^\dagger$ gives the Moore-Penrose Pseudoinverse of $\mathbf{A}$. [I should mention I have the noiseless case in mind here, where $y_i$ is observed exactly as $f(\mathbf{x}_i)$].

Now the reason I put "kind of" above is that this is clearly what the limit of our penalty method gives us as $\lambda\to 0$, so while not a penalty method, it is a limit of them. There may be other, truly different ways of sieving it down to a finite dimensional approximation space that are useful in applications, but I haven't personally run into them.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.