1
$\begingroup$

The optimal weight w* for ridge regression is ($\lambda$ is a positive scalar):

$$w^* = (XX^T+\lambda I_n)^{-1}Xy$$

I want to predict the output for a new datapoint $x_i$, whereby $w^*$ is already given - how could that be calculated? I would use the above equation to reformulate:

$$y_i = w^T*x_i$$

to

$$y_{test} = \sum_i y_i x_i^T* (x_ix_i^T+\lambda)^{-1}x_{test}$$

but that does not seem to make any sense since now I get $y$ on both sides?

$\endgroup$
  • 2
    $\begingroup$ Use the fitted coefficients just as you would in any regression model. $\endgroup$ – whuber Jul 29 '17 at 13:53
  • $\begingroup$ I see, so I am indexing wrong, since y should be on the right a vector accounting for all previous outputs -$y_i = x_i^Tw^*$ and $y_i = x_i^T*\sum_i (x_ix_i^T+\lambda)y_i$ -? Could you let me know if these two equations are right? Thank you $\endgroup$ – Pegah Jul 29 '17 at 14:27
4
$\begingroup$

I think this addresses what you're asking, but correct me if I'm wrong.

In normal ridge regression, we have a $p \times n$ data matrix $X$ corresponding to the $n \times 1$ vector of labels $y$. If we don't want to use an explicit constant term, we fit a model with $$ w = (X X^T + \lambda I)^{-1} X y $$ and then make predictions with $$ y_\text{test} = w^T x_\text{test} .$$ Combining the two steps, this is $$ y_\text{test} = y^T X^T (X X^T + \lambda I)^{-1} x_\text{test} \tag{*} .$$


In kernelized ridge regression, we want to implicitly do some feature transformation of the input points to a possibly infinite-dimensional Hilbert space. So we don't want to do anything with $X$ directly, since it might be infinitely big; instead, we want to only work with the $n \times n$ matrix of kernel values, $K = X^T X$.

To do that, we can use the following identity: $$ \left( X X^T + \lambda I \right)^{-1} X = X \left( X^T X + \lambda I \right)^{-1} \tag{**} $$ which you can see is true by considering: \begin{align} \left( X X^T + \lambda I \right) X \left( X^T X + \lambda I \right)^{-1} &= \left( X X^T X + \lambda X \right) \left( X^T X + \lambda I \right)^{-1} \\&= X \left( X^T X + \lambda I \right) \left( X^T X + \lambda I \right)^{-1} \\&= X ,\end{align} and so left-multiplying the first and last lines by $\left( X X^T + \lambda I \right)^{-1}$ yields (**).

Plugging the transpose of (**) into (*), we get $$ y_\text{test} = y^T (K + \lambda I)^{-1} \underbrace{X^T x_\text{test}}_{K_\text{test}} ,$$ where $K_\text{test}$ is the $n \times 1$ vector of kernel evaluations from the training points to the test point. Now, the training step is basically just to precompute the vector $y^T (K + \lambda I)^{-1}$ (via e.g. a Cholesky solve), and so at test time you just need to compute the vector of $n$ kernel values and take a single dot product.

$\endgroup$
  • 1
    $\begingroup$ For a more thorough discussion, you could check out e.g. these class notes by Max Welling. $\endgroup$ – Dougal Jul 29 '17 at 16:35
  • $\begingroup$ Thanks so much, you addressed smaller questions while embedding them into the bigger picture, extremely helpful! Got the idea of kernelizing ridge with help of the woodbury formula - still have a couple of detail questions though: i. In our script in the original formulation $w^* = (X^TX+\lambda I)^-1+X^Ty$ - I guess that depends only on defining X as nxd or dxn dimensional? ii. When you transpose to arrive at (*) why is the inverse not transposed? iii. Is K_test, intuitively, containing the n similarities between n training points and new test point? iv. In our script, y_test is a vector-why? $\endgroup$ – Pegah Jul 29 '17 at 17:30
  • 1
    $\begingroup$ (i) Yes, it's just whether you define $X$ as $n \times d$ or $d \times n$. (ii) It is, but the matrix being inverted is symmetric so it doesn't matter: $(X X^T)^T = (X^T)^T X^T = X X^T$. (iii) Yes, exactly. I wrote this answer as evaluating for a single test point at a time; your script probably (reasonably) supports multiple test points, which since the prediction formula is linear you can do by just making $K_\text{test}$ of shape $n \times n_\text{test}$. $\endgroup$ – Dougal Jul 29 '17 at 17:33
  • 1
    $\begingroup$ It doesn't, then maybe typo:) thanks for all the effort, it helped me very much! $\endgroup$ – Pegah Jul 29 '17 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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