77
$\begingroup$

I'm just getting started with some machine learning, and until now I have been dealing with linear regression over one variable.

I have learnt that there is a hypothesis, which is:

$h_\theta(x)=\theta_0+\theta_1x$

To find out good values for the parameters $\theta_0$ and $\theta_1$ we want to minimize the difference between the calculated result and the actual result of our test data. So we subtract

$h_\theta(x^{(i)})-y^{(i)}$

for all $i$ from $1$ to $m$. Hence we calculate the sum over this difference and then calculate the average by multiplying the sum by $\frac{1}{m}$. So far, so good. This would result in:

$\frac{1}{m}\sum_{i=1}^mh_\theta(x^{(i)})-y^{(i)}$

But this is not what has been suggested. Instead the course suggests to take the square value of the difference, and to multiply by $\frac{1}{2m}$. So the formula is:

$\frac{1}{2m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})^2$

Why is that? Why do we use the square function here, and why do we multiply by $\frac{1}{2m}$ instead of $\frac{1}{m}$?

$\endgroup$
44
$\begingroup$

Your loss function would not work because it incentivizes setting $\theta_1$ to any finite value and $\theta_0$ to $-\infty$.

Let's call $r(x,y)=\frac{1}{m}\sum_{i=1}^m {h_\theta\left(x^{(i)}\right)} -y$ the residual for $h$.

Your goal is to make $r$ as close to zero as possible, not just minimize it. A high negative value is just as bad as a high positive value.

EDIT: You can counter this by artificially limiting the parameter space $\mathbf{\Theta} $(e.g. you want $|\theta_0| < 10$). In this case, the optimal parameters would lie on certain points on the boundary of the parameter space. See https://math.stackexchange.com/q/896388/12467. This is not what you want.

Why do we use the square loss

The squared error forces $h(x)$ and $y$ to match. It's minimized at $u=v$, if possible, and is always $\ge 0$, because it's a square of the real number $u-v$.

$|u-v|$ would also work for the above purpose, as would $(u-v)^{2n}$, with $n$ some positive integer. The first of these is actually used (it's called the $\ell_1$ loss; you might also come across the $\ell_2$ loss, which is another name for squared error).

So, why is the squared loss better than these? This is a deep question related to the link between Frequentist and Bayesian inference. In short, the squared error relates to Gaussian Noise.

If your data does not fit all points exactly, i.e. $h(x)-y$ is not zero for some point no matter what $\theta$ you choose (as will always happen in practice), that might be because of noise. In any complex system there will be many small independent causes for the difference between your model $h$ and reality $y$: measurement error, environmental factors etc. By the Central Limit Theorem(CLT), the total noise would be distributed Normally, i.e. according to the Gaussian distribution. We want to pick the best fit $\theta$ taking this noise distribution into account. Assume $R = h(X)-Y$, the part of $\mathbf{y}$ that your model cannot explain, follows the Gaussian distribution $\mathcal{N}(\mu,\sigma)$. We're using capitals because we're talking about random variables now.

The Gaussian distribution has two parameters, mean $\mu = \mathbb{E}[R] = \frac{1}{m} \sum_i h_\theta(X^{(i)})-Y^{(i))}$ and variance $\sigma^2 = E[R^2] = \frac{1}{m} \sum_i \left(h_\theta(X^{(i)})-Y^{(i))}\right)^2$. See here to understand these terms better.

  • Consider $\mu$, it is the systematic error of our measurements. Use $h'(x) = h(x) - \mu$ to correct for systematic error, so that $\mu' = \mathbb{E}[R']=0$ (exercise for the reader). Nothing else to do here.

  • $\sigma$ represents the random error, also called noise. Once we've taken care of the systematic noise component as in the previous point, the best predictor is obtained when $\sigma^2 = \frac{1}{m} \sum_i \left(h_\theta(X^{(i)})-Y^{(i))}\right)^2$ is minimized. Put another way, the best predictor is the one with the tightest distribution (smallest variance) around the predicted value, i.e. smallest variance. Minimizing the the least squared loss is the same thing as minimizing the variance! That explains why the least squared loss works for a wide range of problems. The underlying noise is very often Gaussian, because of the CLT, and minimizing the squared error turns out to be the right thing to do!

To simultaneously take both the mean and variance into account, we include a bias term in our classifier (to handle systematic error $\mu$), then minimize the square loss.

Followup questions:

  • Least squares loss = Gaussian error. Does every other loss function also correspond to some noise distribution? Yes. For example, the $\ell_1$ loss (minimizing absolute value instead of squared error) corresponds to the Laplace distribution (Look at the formula for the PDF in the infobox -- it's just the Gaussian with $|x-\mu|$ instead of $(x-\mu)^2$). A popular loss for probability distributions is the KL-divergence. -The Gaussian distribution is very well motivated because of the Central Limit Theorem, which we discussed earlier. When is the Laplace distribution the right noise model? There are some circumstances where it comes about naturally, but it's more commonly as a regularizer to enforce sparsity: the $\ell_1$ loss is the least convex among all convex losses.

    • As Jan mentions in the comments, the minimizer of squared deviations is the mean and the minimizer of the sum of absolute deviations is the median. Why would we want to find the median of the residuals instead of the mean? Unlike the mean, the median isn't thrown off by one very large outlier. So, the $\ell_1$ loss is used for increased robustness. Sometimes a combination of the two is used.
  • Are there situations where we minimize both the Mean and Variance? Yes. Look up Bias-Variance Trade-off. Here, we are looking at a set of classifiers $h_\theta \in H$ and asking which among them is best. If we ask which set of classifiers is the best for a problem, minimizing both the bias and variance becomes important. It turns out that there is always a trade-off between them and we use regularization to achieve a compromise.

Regarding the $\frac{1}{2}$ term

The 1/2 does not matter and actually, neither does the $m$ - they're both constants. The optimal value of $\theta$ would remain the same in both cases.

  • The expression for the gradient becomes prettier with the $\frac{1}{2}$, because the 2 from the square term cancels out.

    • When writing code or algorithms, we're usually concerned more with the gradient, so it helps to keep it concise. You can check progress just by checking the norm of the gradient. The loss function itself is sometimes omitted from code because it is used only for validation of the final answer.
  • The $m$ is useful if you solve this problem with gradient descent. Then your gradient becomes the average of $m$ terms instead of a sum, so its' scale does not change when you add more data points.

    • I've run into this problem before: I test code with a small number of points and it works fine, but when you test it with the entire dataset there is loss of precision and sometimes over/under-flows, i.e. your gradient becomes nan or inf. To avoid that, just normalize w.r.t. number of data points.
  • These aesthetic decisions are used here to maintain consistency with future equations where you'll add regularization terms. If you include the $m$, the regularization parameter $\lambda$ will not depend on the dataset size $m$ and it will be more interpretable across problems.

$\endgroup$
  • $\begingroup$ you said, "when you take the derivative, the expression is prettier, because the 2 cancels out the 2 from the square term". But why do we want to take its derivative ? $\endgroup$ – DrGeneral May 25 '17 at 11:20
  • $\begingroup$ We typically optimize the loss using gradient descent, which requires taking the Derivative. I didn't mention this because it should be clear from the context of this question. $\endgroup$ – Harsh May 25 '17 at 15:31
  • 1
    $\begingroup$ Harsh, Forgive my naivete, but why not use absolute value instead of square? $\endgroup$ – Alexander Suraphel Sep 5 '17 at 16:42
  • 1
    $\begingroup$ Absolute error can also work, but in that case you will regress to the expected median instead of the mean. Take a small list of numbers and see how the loss differs by shifting your estimate (for both squared and absolute error) $\endgroup$ – Jan van der Vegt Oct 26 '17 at 10:58
  • $\begingroup$ @AlexanderSuraphel Sorry for the delay in answering :) I've added a section above to address that $\endgroup$ – Harsh Nov 10 '18 at 22:23
25
$\begingroup$

The 1/2 coefficient is merely for convenience; it makes the derivative, which is the function actually being optimized, look nicer. The 1/m is more fundamental; it suggests that we are interested in the mean squared error. This allows you to make fair comparisons when changing the sample size, and prevents overflow. So called "stochastic" optimizers use a subset of the data set (m' < m). When you introduce a regularizer (an additive term to the objective function), using the 1/m factor allows you to use the same coefficient for the regularizer regardless of the sample size.

As for the question of why the square and not simply the difference: don't you want underestimates to be penalized similarly to overestimates? Squaring eliminates the effect of the sign of the error. Taking the absolute value (L1 norm) does too, but its derivative is undefined at the origin, so it requires more sophistication to use. The L1 norm has its uses, so keep it in mind, and perhaps ask the teacher if (s)he's going to cover it.

$\endgroup$
  • 4
    $\begingroup$ In addition to differentiability, the $L^2$ norm is unique in the $L^p$ norms in that it is a Hilbert space. The fact that the norm arises from an inner product makes a huge amount of machinery available for $L^2$ which is not available for other norms. $\endgroup$ – Steven Gubkin Feb 11 '16 at 5:59
6
$\begingroup$

The error measure in the loss function is a 'statistical distance'; in contrast to the popular and preliminary understanding of distance between two vectors in Euclidean space. With 'statistical distance' we are attempting to map the 'dis-similarity' between estimated model and optimal model to Euclidean space.

There is no constricting rule regarding the formulation of this 'statistical distance', but if the choice is appropriate then a progressive reduction in this 'distance' during optimization translates to a progressively improving model estimation. Consequently, the choice of 'statistical distance' or error measure is related to the underlying data distribution.

In fact, there are several well defined distance/error measures for different classes of statistical distributions. It is advisable to select the error measure based on the distribution of the data in hand. It just so happens that the Gaussian distribution is ubiquitous, and consequently its associated distance measure, the L2-norm is the most popular error measure. However, this is not a rule and there exist real world data for which an 'efficient'* optimization implementation would adopt a different error measure than the L2-norm.

Consider the set of Bregman divergences. The canonical representation of this divergence measure is the L2-norm (squared error). It also includes relative entropy (Kullback-Liebler divergence), generalized Euclidean distance (Mahalanobis metric), and Itakura-Saito function. You can read more about it in this paper on Functional Bregman Divergence and Bayesian Estimation of Distributions.

Take-away: The L2-norm has an interesting set of properties which makes it a popular choice for error measure (other answers here have mentioned some of these, sufficient to the scope of this question), and the squared error will be the appropriate choice most of the time. Nevertheless, when the data distribution requires it, there are alternate error measures to choose from, and the choice depends in large part on the formulation of the optimization routine.

*The 'appropriate' error measure would make the loss function convex for the optimization, which is very helpful, as opposed to some other error measure where the loss function is non-convex and thereby notoriously difficult.

$\endgroup$
5
$\begingroup$

In addition to the key points made by others, using squared error puts a greater emphasis on larger error (what happens to 1/2 when you square it vs 3/2?).

Having an algorithm that moves the fractional errors, that would likely result in correct classification or very small difference between estimate and ground truth, if left alone close to zero, while leaving the large errors as large errors or misclassifications, is not a desirable characteristic of an algorithm.

Using squared error uses the error as an implied importance weight for adjusting prediction.

$\endgroup$
  • $\begingroup$ so, what is the arbitrary error $\endgroup$ – jeza Oct 8 '18 at 21:52
3
$\begingroup$

In your formulation, you try to obtain the mean deviation of your approximation from the observed data.

If the mean value of your approximation is close or equal to the mean value of the observed data (something which is desirable and often happens with many approximation schemes) then the result of your formulation would be zero or negligible, because positive errors compensate with negative errors. This might lead to the conclusion that your approximation is wonderful at each observed sample, while it might not be the case. That's why you use the square of the error at each sample and you add them up (your turn each error positive).

Of course this is only a possible solution, as you could have used L1-norm (absolute value of the error at each sample) or many others, instead of L2-norm.

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