23
$\begingroup$

So I was asked a question on which central measures L1 (i.e., lasso) and L2 (i.e., ridge regression) estimated. The answer is L1=median and L2=mean. Is there any type of intuitive reasoning to this? Or does it have to be determined algebraically? If so, how do I go about doing that?

$\endgroup$
  • 4
    $\begingroup$ By L1/L2 are you referring to the objective function or the constraints? If objective function then yes L1 error is minimized with the conditional median and L2 the conditional mean. If constraints (what ridge/lasso refer to) then this is the wrong way to think about this. Their "central measures" are still aiming for a conditional mean but with different penalties on $\beta$. $\endgroup$ – muratoa Aug 19 '12 at 7:10
24
$\begingroup$

There is a simple geometric explanation for why the L1 loss function yields the median.

Recall that we are working in one dimension, so imagine a number line spreading horizontally. Plot each of the data points on the number line. Put your finger somewhere on the line; your finger will be your current candidate estimate.

Suppose you move your finger a little bit to the right, say $\delta$ units to the right. What happens to the total loss? Well, if your finger was between two data points, and you move it across a data point, you've increased the total loss by $\delta$ for each data point to the left of your finger, and decreased it by $\delta$ for each data point to the right of your finger. So, if there are more data points to the right of your finger than there are to the left, moving your finger to the right decreases the total loss. In other words, if more than half of the data points are to the right of your finger, you should move your finger to the right.

This leads to you moving your finger towards a spot where half of the data points are on the of that spot, and half are on the right. That spot is the median.

That's L1 and the median. Unfortunately, I don't have a similar, "all intuition, no algebra" explanation for L2 and the mean.

$\endgroup$
  • 7
    $\begingroup$ If we are talking about a simple point estimate then it is straightforward calculus. $\frac{d}{d \beta} \frac{1}{n}\sum_{i=1}^n (y_i - \beta)^2 = -2\frac{1}{n}\sum_{i=1}^n(y_i - \beta) = 0 \Rightarrow \beta = \frac{1}{n}\sum_i y_i$ $\endgroup$ – muratoa Aug 19 '12 at 7:15
  • 3
    $\begingroup$ @muratoa, yes, I know the calculus derivation, but the question asks specifically for an explanation that focuses on intuition and avoids algebra. I would assume that the question-asker knows the calculus derivation already, but is looking for something that provides more intuition. $\endgroup$ – D.W. Aug 19 '12 at 7:50
  • $\begingroup$ I thought the OP mentioned regression which suggests that he is talking about the estimate of y given x which is a conditional mean using least squares and the conditional median for mean absolute error. The same explanations should work but the problem is a little different. The calculus explanation for the mean is pretty clear and straightforward. Perhaps an explanation for the mean can be given in a similar fashion to D.W.s for the median. The sample mean is an unbiased estimate for the population mean. $\endgroup$ – Michael Chernick Aug 19 '12 at 12:07
  • $\begingroup$ As you move the estimate away from the sample mean the mean square error changes because of an increase in bias. The mean square error actually increases by d$^2$ when the estimate adds d to the sample mean as the candidate estimate. $\endgroup$ – Michael Chernick Aug 19 '12 at 12:08
  • 10
    $\begingroup$ A quick and dirty version of the algebra given by muratoa exists for the L1 case. Observe that except when $\beta = y_i$, the derivative of $| y_i -\beta |$ w.r.t $\beta$ is $-\mathrm{sgn}(y_i-\beta)$, that is $-1$ if $\beta < y_i$ and $+1$ if $\beta > y_i$. So $\frac{\mathrm{d}}{\mathrm{d}\beta} \,\frac{1}{n}\sum_i | y_i -\beta | = -\frac{1}{n}\,\sum_i \mathrm{sgn}(y_i-\beta)$, except when $\beta$ is an $y_i$. The derivative vanishes when there is the same number of positive and negative terms among the $y_i-\beta$, which roughly speaking arises when $\beta$ is the median of the $y_i$. $\endgroup$ – Yves Aug 19 '12 at 12:59
15
$\begingroup$

This explanation is a summation of muratoa and Yves's comments on D.W.'s answer. Though it is based on calculus, I found it straightforward and easy to understand.

Assuming we have $y_1, y_2, ... y_k$ and to want get a new estimate $\beta$ based on them. The smallest loss is obtained when we find $\beta$ which makes the derivative of the loss to zero.

L1 loss

$$L1=\frac{1}{k}\sum_{i=1}^k|y_i-\beta|$$ $$\frac{\partial L_1}{\partial\beta}=-\frac{1}{k}\sum_{i=1}^k sgn(y_i-\beta)$$ $sgn(y_i-\beta)$ is 1 when $y_i>\beta$, -1 when $y_i<\beta$. The derivative equals to 0 when there is the same number of positive and negative terms among the $y_i-\beta$, which means $\beta$ should be the median of $y_i$.

L2 loss

$$L2=\frac{1}{k}\sum_{i=1}^k(y_i-\beta)^2$$ $$\frac{\partial L_2}{\partial\beta}=-\frac{2}{k}\sum_{i=1}^k(y_i-\beta)$$ $$\frac{\partial L_2}{\partial\beta}=0\rightarrow\beta=\frac{1}{k}\sum_{i=1}^k y_i$$
So to minimize L2 loss, $\beta$ should be the mean of $y_i$.

$\endgroup$
2
$\begingroup$

Adding to D.W.'s answer with an even more practical example (for L2 loss function as well):

Imagine a small village made of 4 houses close to each other (e.g. 10 meters). At 1 kilometer from those, you have another very isolated house. Now, you arrive in that town and want to build your own house somewhere. You want to live close to the other houses and be friend with everybody. Consider those two alternative scenarios:

  1. You decide to be at the location where the average distance to any house is the smallest (i.e. minimizing a L1 loss function).

    • If you put your house at the center of the village, you will be around 10 meters away from 4 houses and 1 kilometer away from one house, which gives you an average distance of about 200 meters (10+10+10+10+1000 / 5).
    • If you place your house 500 meters away from the village, you will be around 500 meters away from 5 houses, which gives you an average distance of 500 meters.
    • If you place your house next to the isolated house, you will be 1km away from the village (4 houses) and around 10 meters away from 1 house, which gives you an average distance of about 800 meters.

    So the lowest average distance of 100 meters is reached by building your house in the village. More specifically, you will build your house in the middle of these 4 houses to gain a few more meters of average distance. And it turns out that this point is the "median point", that you would have obtained similarly using the median formula.

  2. You decide to take a democratic approach. You ask each of your five future neighbors their preferred location for your new house. They all like you and want you to live close to them. So they all state their preferred location to be the spot just next to their own house. You take the average of all the voted locations of your five neighbors, and the result is "200 meters away from the village" (average of the votes: 0+0+0+0+1000/5 = 200), which is the "mean point" of the 5 houses, that you would have obtained similarly using the mean formula. And this location turns out to be exactly the same that mimimizes the sum of squared distances (i.e. L2 loss function). Let's just do the math to see it:
    • At this location, the sum of squared distances is: 200^2 + 200^2 + 200^2 + 200^2 + 800^2 = 800 000
    • If we build the house in the center of the village, our sum of squared distances would be: 0^2 + 0^2 + 0^2 + 0^2 + 1000^2 = 1 000 000
    • If we build build the house at 100 meters away from the village (like in 1), the sum of squared distances is: 100^2 + 100^2 + 100^2 + 100^2 + 900^2 = 850 000
    • If we build the house at 100 meters away from the isolated house, the sum of squared distances is: 900^2 + 900^2 + 900^2 + 900^2 + 100^2 = 3 250 000

So yes, it is interesting to notice that, a bit counter-intuitively, when we minimize the sum of the distances, we don't end up being in the "middle" in the sense of the mean, but in the sense of the median. This is part of the reason why OLS, one of the most popular regression models, uses squared errors rather than absolute errors.

$\endgroup$
0
$\begingroup$

In addition to the already-posted answers (which have been very helpful to me!), there is a geometric explanation for the connection between the L2 norm and the mean.

To use the same notation as chefwen, the formula for L2 loss is:

$$ L2 = \frac{1}{k} \sum^{k}_{i=1} (y_i - \beta)^2$$

We wish to find the value of $\beta$ which minimizes $L2$. Notice that this is equivalent to minimizing the following, since multiplying by $k$ and taking the square root both preserve order:

$$ \sqrt { \sum^{k}_{i=1} (y_i - \beta)^2 }$$

If you consider the data vector $y$ as a point in $k$-dimensional space, this formula calculates the Euclidean distance between the point $y$ and the point $\vec{\beta} = (\beta, \beta, ..., \beta)$.

So the problem is to find the value $\beta$ which minimizes the Euclidean distance between the points $y$ and $\vec{\beta}$. Since the possible values of $\vec{\beta}$ all lie on the line parallel to $\vec{1} = (1, 1, ..., 1)$ by definition, this is equivalent to finding the vector projection of $y$ onto $\vec{1}$.

It's only really possible to visualize this when $k = 2$, but here is an example where $y = (2, 6)$. As shown, projecting onto $\vec{1}$ yields $(4, 4)$ as we expect.

the vector y projected onto beta

To show that this projection always yields the mean (including when $k > 2$), we can apply the formula for projection:

$$ \begin{alignat}{2} \vec{\beta} &= \operatorname{proj}_{\vec{1}}{y} \\ &= \frac{y \cdot \vec{1}}{|\vec{1}|^2}\vec{1} \\ \beta &= \frac{\sum^k_{i=1} y_i}{k} \end{alignat} $$

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