58
$\begingroup$

I understand that the ridge regression estimate is the $\beta$ that minimizes residual sum of square and a penalty on the size of $\beta$

$$\beta_\mathrm{ridge} = (\lambda I_D + X'X)^{-1}X'y = \operatorname{argmin}\big[ \text{RSS} + \lambda \|\beta\|^2_2\big]$$

However, I don't fully understand the significance of the fact that $\beta_\text{ridge}$ differs from $\beta_\text{OLS}$ by only adding a small constant to the diagonal of $X'X$. Indeed,

$$\beta_\text{OLS} = (X'X)^{-1}X'y$$

  1. My book mentions that this makes the estimate more stable numerically -- why?

  2. Is numerical stability related to the shrinkage towards 0 of the ridge estimate, or it's just a coincidence?

$\endgroup$
75
$\begingroup$

In an unpenalized regression, you can often get a ridge* in parameter space, where many different values along the ridge all do as well or nearly as well on the least squares criterion.

* (at least, it's a ridge in the likelihood function -- they're actually valleys$ in the RSS criterion, but I'll continue to call it a ridge, as this seems to be conventional -- or even, as Alexis points out in comments, I could call that a thalweg, being the valley's counterpart of a ridge)

In the presence of a ridge in the least squares criterion in parameter space, the penalty you get with ridge regression gets rid of those ridges by pushing the criterion up as the parameters head away from the origin:

enter image description here
[Clearer image]

In the first plot, a large change in parameter values (along the ridge) produces a miniscule change in the RSS criterion. This can cause numerical instability; it's very sensitive to small changes (e.g. a tiny change in a data value, even truncation or rounding error). The parameter estimates are almost perfectly correlated. You may get parameter estimates that are very large in magnitude.

By contrast, by lifting up the thing that ridge regression minimizes (by adding the $L_2$ penalty) when the parameters are far from 0, small changes in conditions (such as a little rounding or truncation error) can't produce gigantic changes in the resulting estimates. The penalty term results in shrinkage toward 0 (resulting in some bias). A small amount of bias can buy a substantial improvement in the variance (by eliminating that ridge).

The uncertainty of the estimates are reduced (the standard errors are inversely related to the second derivative, which is made larger by the penalty).

Correlation in parameter estimates is reduced. You now won't get parameter estimates that are very large in magnitude if the RSS for small parameters would not be much worse.

$\endgroup$
  • 4
    $\begingroup$ This answer really helps me understand shrinkage and numerical stability. However, I'm still unclear about how "adding a small constant to $X'X$" achieves these two things. $\endgroup$ – Heisenberg Oct 12 '14 at 16:45
  • 4
    $\begingroup$ Adding a constant to the diagonal* is the same as adding a circular paraboloid centered at $0$ to the RSS (with the result shown above - it "pulls up" away from zero - eliminating the ridge). $\quad\quad$ *(it's not necessarily small, it depends on how you look at it and how much you added) $\endgroup$ – Glen_b Oct 12 '14 at 17:05
  • 6
    $\begingroup$ Glen_b the antonym of "ridge" in the English language that you are looking for (that path/curve along a valley floor) is thalweg. Which I just learned about two weeks ago and simply adore. It doesn't even sound like an English word! :D $\endgroup$ – Alexis Oct 12 '14 at 18:01
  • 4
    $\begingroup$ @Alexis That would no doubt be a handy word, so thanks for that. It probably doesn't sound English because it's a German word (indeed the thal is the same 'thal' as in "Neanderthal" = "Neander valley", and weg ='way'). [As it was, I wanted "ridge" not because I couldn't think of what to call it, but because people seem to call it a ridge whether they're looking at likelihood or RSS, and I was explaining my desire to follow the convention, even though it seems odd. Thalweg would be an excellent choice for just the right word, were I not following the odd thalweg of convention.] $\endgroup$ – Glen_b Oct 12 '14 at 21:28
  • 4
    $\begingroup$ X becomes close to a matrix not of full rank (and hence X'X becomes nearly singular) exactly when a ridge appears in the likelihood. The ridge is a direct consequence of a nearly linear relationship between columns of $X$, which makes $\beta$s (nearly) linearly dependent. $\endgroup$ – Glen_b Oct 13 '14 at 20:23
27
$\begingroup$

+1 on Glen_b's illustration and the stats comments on the Ridge estimator. I would just like to add a purely mathematical (linear algebra) pov on Ridge regression which answers OPs questions 1) and 2).

First note that $X'X$ is a $p \times p$ symmetric positive semidefinite matrix - $n$ times the sample covariance matrix. Hence it has the eigen-decomposition

$$ X'X = V D V', \quad D = \begin{bmatrix} d_1 & & \\ & \ddots & \\ & & d_p \end{bmatrix}, d_i \geq 0 $$

Now since matrix inversion corresponds to inversion of the eigenvalues, the OLS estimator requires $(X'X)^{-1} = V D^{-1} V'$ (note that $V ' = V^{-1}$). Obviously this only works if all eigenvalues are strictly greater than zero, $d_i > 0$. For $p \gg n$ this is impossible; for $n \gg p$ it is in general true - this is were we are usually concerned with multicollinearity.

As statisticians we also want to know how small perturbations in the data $X$ change the estimates. It is clear that a small change in any $d_i$ leads to huge variation in $1 / d_i$ if $d_i$ is very small.

So what Ridge regression does is move all eigenvalues further away from zero as

$$ X'X + \lambda I_p = V D V' + \lambda I_p = V D V' + \lambda V V' = V (D + \lambda I_p) V', $$ which now has eigenvalues $d_i + \lambda \geq \lambda \geq 0$. This is why choosing a positive penalty parameter makes the matrix invertible -- even in the $p \gg n$ case. For Ridge regression a small variation in the data $X$ does not have anymore the extremely unstable effect it has on the matrix inversion.

The numerical stability is related to shrinkage to zero as they both are a consequence of adding a positive constant to the eigenvalues: it makes it more stable because a small perturbation in $X$ does not change the inverse too much; it shrinks it close to $0$ since now the $V^{-1} X'y$ term is multiplied by $1 / (d_i + \lambda)$ which is closer to zero than the OLS solution with inverse eigenvalues $1 / d$.

$\endgroup$
  • 2
    $\begingroup$ This answers satisfactorily answers the algebra part of my question! Together with Glen_b answer it makes a full explanation of the issue. $\endgroup$ – Heisenberg Feb 29 '16 at 16:17
17
$\begingroup$

@Glen_b's demonstration is wonderful. I would just add that aside from the exact cause of the problem and description about how quadratic penalized regression works, there is the bottom line that penalization has the net effect of shrinking the coefficients other than the intercept towards zero. This provides a direct solution to the problem of overfitting that is inherent in most regression analyses when the sample size is not enormous in relation to the number of parameters estimate. Almost any penalization towards zero for non-intercepts is going to improve predictive accuracy over an un-penalized model.

$\endgroup$

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.