# Prediciting an output with (kernelized) ridge regression

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?

• Use the fitted coefficients just as you would in any regression model. – whuber Jul 29 '17 at 13:53
• 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 – Pegah Jul 29 '17 at 14:27

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.

• For a more thorough discussion, you could check out e.g. these class notes by Max Welling. – Dougal Jul 29 '17 at 16:35
• 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? – Pegah Jul 29 '17 at 17:30
• (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}$. – Dougal Jul 29 '17 at 17:33
• It doesn't, then maybe typo:) thanks for all the effort, it helped me very much! – Pegah Jul 29 '17 at 17:37