16
$\begingroup$

When explaining LASSO regression, the diagram of a diamond and circle is often used. It is said that because the shape of the constraint in LASSO is a diamond, the least squares solution obtained might touch the corner of the diamond such that it leads to a shrinkage of some variable. However, in ridge regression, because it is a circle, it will often not touch the axis. I could not understand why it cannot touch the axis or maybe have a lower probability than LASSO to shrink certain parameters. On top of that, why do LASSO and ridge have lower variance than ordinary least squares? The above is my understanding of ridge and LASSO and I might be wrong. Can someone help me understand why these two regression methods have lower variance?

$\endgroup$
  • 1
    $\begingroup$ Possible duplicate of Why does the Lasso provide Variable Selection? $\endgroup$ – Juho Kokkala Oct 12 '15 at 16:16
  • 1
    $\begingroup$ Ok, the variance part in bold is not duplicate, at least of this question; so maybe this question could be edited to focus on that. $\endgroup$ – Juho Kokkala Oct 12 '15 at 16:20
  • $\begingroup$ This is well explained in figure 3.11 of web.stanford.edu/~hastie/local.ftp/Springer/OLD/… $\endgroup$ – user83346 Oct 12 '15 at 17:15
  • $\begingroup$ @fcop i read the book but i do not quite understand the math $\endgroup$ – user10024395 Oct 12 '15 at 18:25
  • $\begingroup$ But to understand the picture you do not need the math ? $\endgroup$ – user83346 Oct 17 '15 at 8:54
24
$\begingroup$

This is regarding the variance

OLS provides what is called the Best Linear Unbiased Estimator (BLUE). That means that if you take any other unbiased estimator, it is bound to have a higher variance then the OLS solution. So why on earth should we consider anything else than that?

Now the trick with regularization, such as the lasso or ridge, is to add some bias in turn to try to reduce the variance. Because when you estimate your prediction error, it is a combination of three things: $$ \text{E}[(y-\hat{f}(x))^2]=\text{Bias}[\hat{f}(x))]^2 +\text{Var}[\hat{f}(x))]+\sigma^2 $$ The last part is the irreducible error, so we have no control over that. Using the OLS solution the bias term is zero. But it might be that the second term is large. It might be a good idea, (if we want good predictions), to add in some bias and hopefully reduce the variance.

So what is this $\text{Var}[\hat{f}(x))]$? It is the variance introduced in the estimates for the parameters in your model. The linear model has the form $$ \mathbf{y}=\mathbf{X}\beta + \epsilon,\qquad \epsilon\sim\mathcal{N}(0,\sigma^2I) $$ To obtain the OLS solution we solve the minimization problem $$ \arg \min_\beta ||\mathbf{y}-\mathbf{X}\beta||^2 $$ This provides the solution $$ \hat{\beta}_{\text{OLS}} = (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y} $$ The minimization problem for ridge regression is similar: $$ \arg \min_\beta ||\mathbf{y}-\mathbf{X}\beta||^2+\lambda||\beta||^2\qquad \lambda>0 $$ Now the solution becomes $$ \hat{\beta}_{\text{Ridge}} = (\mathbf{X}^T\mathbf{X}+\lambda I)^{-1}\mathbf{X}^T\mathbf{y} $$ So we are adding this $\lambda I$ (called the ridge) on the diagonal of the matrix that we invert. The effect this has on the matrix $\mathbf{X}^T\mathbf{X}$ is that it "pulls" the determinant of the matrix away from zero. Thus when you invert it, you do not get huge eigenvalues. But that leads to another interesting fact, namely that the variance of the parameter estimates becomes lower.

I am not sure if I can provide a more clear answer then this. What this all boils down to is the covariance matrix for the parameters in the model and the magnitude of the values in that covariance matrix.

I took ridge regression as an example, because that is much easier to treat. The lasso is much harder and there is still active ongoing research on that topic.

These slides provide some more information and this blog also has some relevant information.

EDIT: What do I mean that by adding the ridge the determinant is "pulled" away from zero?

Note that the matrix $\mathbf{X}^T\mathbf{X}$ is a positive definite symmetric matrix. Note that all symmetric matrices with real values have real eigenvalues. Also since it is positive definite, the eigenvalues are all greater than zero.

Ok so how do we calculate the eigenvalues? We solve the characteristic equation: $$ \text{det}(\mathbf{X}^T\mathbf{X}-tI)=0 $$ This is a polynomial in $t$, and as stated above, the eigenvalues are real and positive. Now let's take a look at the equation for the ridge matrix we need to invert: $$ \text{det}(\mathbf{X}^T\mathbf{X}+\lambda I-tI)=0 $$ We can change this a little bit and see: $$ \text{det}(\mathbf{X}^T\mathbf{X}-(t-\lambda)I)=0 $$ So we can solve this for $(t-\lambda)$ and get the same eigenvalues as for the first problem. Let's assume that one eigenvalue is $t_i$. So the eigenvalue for the ridge problem becomes $t_i+\lambda$. It gets shifted by $\lambda$. This happens to all the eigenvalues, so they all move away from zero.

Here is some R code to illustrate this:

# Create random matrix
A <- matrix(sample(10,9,T),nrow=3,ncol=3)

# Make a symmetric matrix
B <- A+t(A)

# Calculate eigenvalues
eigen(B)

# Calculate eigenvalues of B with ridge
eigen(B+3*diag(3))

Which gives the results:

> eigen(B)
$values
[1] 37.368634  6.952718 -8.321352

> eigen(B+3*diag(3))
$values
[1] 40.368634  9.952718 -5.321352

So all the eigenvalues get shifted up by exactly 3.

You can also prove this in general by using the Gershgorin circle theorem. There the centers of the circles containing the eigenvalues are the diagonal elements. You can always add "enough" to the diagonal element to make all the circles in the positive real half-plane. That result is more general and not needed for this.

$\endgroup$
  • $\begingroup$ Can you explain how it "pulls" the determinant away from zero (mathematically)? Thanks $\endgroup$ – user10024395 Oct 12 '15 at 18:24
  • $\begingroup$ @user2675516 I have edited my answer. $\endgroup$ – Gumeo Oct 12 '15 at 19:05
  • $\begingroup$ "That means that if you take any other unbiased estimator, it is bound to have a higher variance then the OLS solution". You mean higher bias than OLS? I thought OLS has least bias so anything else would have higher bias. Pls clarify $\endgroup$ – GeorgeOfTheRF Jul 28 '17 at 4:46
  • $\begingroup$ @ML_Pro OLS has zero bias, and of all unbiased estimators, it has the smallest variance. This is a theorem. So if you pick any other, the variance will increase. But if you regularize, you introduce bias. $\endgroup$ – Gumeo Jul 28 '17 at 10:09
  • $\begingroup$ Thanks! Your response made me curious. Can you answer this new question I created? stats.stackexchange.com/questions/294926/… $\endgroup$ – GeorgeOfTheRF Jul 28 '17 at 11:39
2
$\begingroup$

Ridge Regression

L2 = (y-xβ)^2+λ∑βi^2

Will solve this equation only for one β for now and latter you can generalize this:

So, (y-xβ)^2+λβ^2 this is our equation for one β.

Our goal is to minimize the above equation, to be able to do this, will equate this to zero and take the derivatives w.r.t β

Y^2- 2xyβ+ x^2 β^2+ λβ^2=0 -------Using (a-b) ^2 expansion

Partial derivatives w.r.t

-2xy+2x^2β+2βλ=0

2β (x^2+λ) = 2xy

β= 2xy/ 2(x^2 + λ)

Finally

β= xy/ (x^2 + λ)

If you observe the denominator, it will never become zero, since we are adding some value of λ (i.e. hyper parameter). And therefore the value of β will be as low as possible but will not become zero.

LASSO Regression:

L1= (y-xβ)^2+λ∑|β|

Will solve this equation only for one β for now and latter you can generalize this to more β:

So, (y-xβ)^2+λβ this is our equation for one β, Here I have considered +ve value of β.

Our goal is to minimize the above equation, to be able to do this, will equate this to zero and take the derivatives w.r.t β

Y^2- 2xyβ+ x^2 β^2+ λβ=0 -------Using (a-b) ^2 expansion

Partial derivatives w.r.t

-2xy+2x^2β+λ=0

2x^2β+λ= 2xy

2x^2β=2xy-λ

Finally

β= (2xy-λ)/ (2X^2)

If you observe the numerator, it will become zero, since we are subtracting some value of λ (i.e. hyper parameter). And therefore the value of β will be set as zero.

$\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.