26
$\begingroup$

I completed Andrew Ng's Machine Learning course around a year ago, and am now writing my High School Math exploration on the workings of Logistic Regression and techniques to optimize on performance. One of these techniques is, of course, regularization.

The aim of regularization is to prevent overfitting by extending the cost function to include the goal of model simplicity. We can achieve this by penalizing the size of weights by adding to the cost function each of the weights squared, multiplied by some regularization paramater.

Now, the Machine Learning algorithm will aim to reduce the size of the weights whilst retaining the accuracy on the training set. The idea is that we will reach some point in the middle where we can produce a model that generalizes on the data and does not try to fit in all the stochastic noise by being less complex.

My confusion is why we penalize the size of the weights? Why do larger weights create more complex models, and smaller weights create simpler/smoother models? Andrew Ng claims in his lecture that the explanation is a difficult one to teach, but I guess I am looking for this explanation now.

Prof. Ng did indeed give an example of how the new cost function may cause the weights of features (ie. x^3 and x^4) to tend towards zero so that the model's degree is reduced, but this does not create a complete explanation.

My intuition is that smaller weights will tend to be more "acceptable" on features with greater exponents than ones with smaller exponents (because the features with small weights are like the basis of the function). Smaller weights imply smaller "contributions" to the features with high order. But this intuition is not very concrete.

$\endgroup$
  • 2
    $\begingroup$ this sounds like a question in need of a "so my grandma would understand it" answer. $\endgroup$ – EngrStudent Dec 27 '15 at 23:12
  • 2
    $\begingroup$ @EngrStudent Because that's exactly how I need to present it in my Math IA for my high school math teacher and high school math examiners to read. $\endgroup$ – MCKapur Dec 28 '15 at 7:41
4
+100
$\begingroup$

If you use regularization you're not only minimizing the in-sample error but $OutOfSampleError \le InSampleError + ModelComplexityPenalty$.

More precisely, $J_{aug}(h(x),y,\lambda,\Omega)=J(h(x),y)+\frac{\lambda}{2m}\Omega$ for a hypothesis $h \in H$, where $\lambda$ is some parameter, usually $\lambda \in (0,1)$, $m$ is the number of examples in your dataset, and $\Omega$ is some penalty that is dependent on the weights $w$, $\Omega=w^Tw$. This is known as the augmented error. Now, you can only minimize the function above if the weights are rather small.

Here is some R code to toy with

w <- c(0.1,0.2,0.3)
out <- t(w) %*% w
print(out)

So, instead of penalizing the whole hypothesis space $H$, we penalize each hypothesis $h$ individually. We sometimes refer to the hypothesis $h$ by its weight vector $w$.

As for why small weights go along with low model complexitity, let's look at the following hypothesis: $h_1(x)=x_1 \times w_1 + x_2 \times w_2 + x_3 \times w_3$. In total we got three active weight parameters ${w_1,\dotsc,w_3}$. Now, let's set $w_3$ to a very very small value, $w_3=0$. This reduces the model's complexity to: $h_1(x)=x_1 \times w_1 + x_2 \times w_2$. Instead of three active weight parameters we only got two remaining.

$\endgroup$
  • 1
    $\begingroup$ Obviously if a weight reduces to zero then the complexity of the model is reduced since you can remove a term and therefore a computational operation. But this doesn't help to explain why the complexity of the model is reduced as the value of the weight approaches zero. Can anyone explain that with words not formulas? $\endgroup$ – greg7gkb Jul 5 at 18:44
5
$\begingroup$

I'm not sure if I really know what I'm talking about but I'll give it a shot. It isn't so much having small weights that prevents overfitting (I think), it is more the fact that regularizing more strongly reduces the model space. In fact you can regularize around 10000000 if you wanted to by taking the L2 norm of your X values minus a vector of 10000000s. This would also reduce overfitting (of course you should also have some rationale behind doing that (ie perhaps your Y values are 10000000 times bigger than the sum of your X values, but no one really does that because you can just rescale data).

Bias and variance are both a function of model complexity. This is related to VC theory so look at that. The larger the space of possible models (ie values all your parameters can take basically) the more likely the model will overfit. If your model can do everything from being a straight line to wiggling in every direction like a sine wave that can also go up and down, it's much more likely to pick up and model random perturbations in your data that isn't a result of the underlying signal but the result of just lucky chance in that data set (this is why getting more data helps overfitting but not underfitting).

When you regularize, basically you are reducing the model space. This doesn't necessarily mean smoother/flatter functions have higher bias and less variance. Think of a linear model that is overlaid with a sine wave that is restricted to have a really small amplitude oscillations that basically does nothing (its basically a fuzzy line). This function is super wiggly in a sense but only overfits slightly more than a linear regression. The reason why smoother/flatter functions tend to have higher bias and less variance is because we as data scientist assume that if we have a reduced sample space we would much rather by occam's razor keep the models that are smoother and simpler and throw out the models that are wiggly and oscillating all over the place. It makes sense to throw out wiggly models first, which is why smoother models tend to be more prone to underfitting and not overfitting.

Regularization like ridge regression, reduces the model space because it makes it more expensive to be further away from zero (or any number). Thus when the model is faced with a choice of taking into account a small perturbation in your data, it will more likely err on the side of not, because that will (generally) increase your parameter value. If that perturbation is due to random chance (ie one of your x variables just had a slight random correlation with your y variables) the model will not take that into account versus a non-regularized regression because the non regularized regression has no cost associated with increasing beta sizes. However, if that perturbation is due to real signal, your regularized regression will more likely miss it which is why it has higher bias (and why there is a variance bias tradeoff).

$\endgroup$
  • $\begingroup$ Thank you for your thoughtful answer! So yes, in the fourth paragraph you state "Thus when the model is faced with a choice of taking into account a small perturbation in your data, it will more likely err on the side of not, because that will (generally) increase your parameter value.". This is what I'm asking in specific why this is the case? Thanks! $\endgroup$ – MCKapur Dec 24 '15 at 7:12
  • $\begingroup$ By adding a penalty factor you make it less likely that the model will have higher betas, therefore your model space is smaller. The other thing to remember is that if your model is all noise, it will likely have zero slope as there is no correlation (this was one thing I didn't think about when making my wiggly/flat argument but I think the argument is still generally true). Thus if there is a perterbation/relationship, it is likely to increase the beta. Thus regularization penalizes this fact and stops the regression from fitting those perturbations be they signal or noise. $\endgroup$ – www3 Dec 24 '15 at 20:32
  • $\begingroup$ @ww3 I understand. But why do larger betas result in a higher model space? $\endgroup$ – MCKapur Dec 24 '15 at 20:39
  • $\begingroup$ I'm not sure if you need this anymore but I thought I would answer. It's not big betas that matter. For example you can perform a regression with Y or 1000*Y each will have the same complexity but the betas will be 1000 higher in the second case. Typical regularization makes attaining certain beta combinations more difficult, like having one coefficient be 1000 and another -1000, and others that are flatter/simpler like all 0s easier. This means if you model has certain noisy quirks from the data the regularized model is less likely to pick it up. $\endgroup$ – www3 Jan 16 '16 at 18:56
  • $\begingroup$ To continue, the model will not ignore all noisy quirks, it will only ignore quirks that increase the absolute values of the betas. This means that quirks that reduce the values of betas will be more emphasized. This is okay though because there are far more wiggly lines you can draw than straight lines (ie compare a quadratic equation to a linear or constant equation). Thus if there are noisy quirks that affect the data, they are much more likely to make a model fit a more wiggly (and therefore more complex model) than a flatter/straighter model. $\endgroup$ – www3 Jan 16 '16 at 19:09
3
$\begingroup$

Story:
My grandma walks, but doesn't climb. Some grandmas do. One grandma was famous for climbing Kilimanjaro.

That dormant volcano is big. It is 16,000 feet above its base. (Don't hate my imperial units.) It also has glaciers on the top, sometimes.

If you climb on a year where there is no glacier, and you get to the top, is it the same top as if there was a glacier? The altitude is different. The path you have to take is different. What if you go to the top when the glacier thickness is larger? Does that make it more of an accomplishment? About 35,000 people attempt to climb it every year, but only about 16,000 succeed.

Application:
So I would explain the control of weights (aka minimizing model complexity) to my grandma, as follows:

Grandma, your brain is an amazing thinker whether or not you know it. If I ask you how many of the 16,000 who think they reached the top actually did so, you would say "all of them".

If I put sensors in shoes of all the 30,000 climbers, and measured height above sea-level, then some of those folks didn't get as high as others, and might not qualify. When I do that I am going to a constant model - I am saying if height is not equal to some percentile of measured max heights then it is not the top. Some people jump at the top. Some people just cross the line and sit down.

I could add latitude and longitude to the sensor, and fit some higher order equations and maybe I could get a better fit, and have more folks in, maybe even exactly 45% of the total folks who attempt it.

So let's say next year is a "big glacier" year or a "no glacier" year because some volcano really transforms the albedo of the earth. If I take my complex and exacting model from this year and apply it to the folks who climb next year the model is going to have strange results. Maybe everyone will "pass" or even be too high to pass. Maybe nobody at all will pass, and it will think nobody actually completed the climb. Especially when the model is complex it will tend to not generalize well. It may exactly fit this year's "training" data, but when new data comes it behaves poorly.

Discussion:
When you limit the complexity of the model, then you can usually have better generalization without over-fitting. Using simpler models, ones that are more built to accommodate real-world variation, tends to give better results, all else being equal.

Now you have a fixed network topology, so you are saying "my parameter count is fixed" - I can't have variation in model complexity. Nonsense. Measure the entropy in the weights. When the entropy is higher it means some coefficients carry substantially more "informativeness" than others. If you have very low entropy it means that in general the coefficients carry similar levels of "informativeness". Informativeness is not necessarily a good thing. In a democracy you want all people to be equal, and things like George Orwell "more equal than others" is a measure of failures of the system. If you don't have a great reason for it, you want weights to be pretty similar to each other.

On a personal note: instead of using voodoo or heuristics, I prefer things like "information criteria" because they allow me to get reliable and consistent results. AIC, AICc, and BIC are some common and useful starting points. Repeating the analysis to determine stability of the solution, or range of information criteria results is a common approach. One might look at putting a ceiling on the entropy in the weights.

$\endgroup$
  • 2
    $\begingroup$ Interestingly different. Pedant's corner: you wrote "Orson Wells". the spelling is Welles. I suspect you meant George Orwell (Animal Farm) all along. $\endgroup$ – Nick Cox Jan 4 '16 at 1:35
  • $\begingroup$ @NickCox - I have been very sick. My brain isn't working as well as I wished. Orwell it was. $\endgroup$ – EngrStudent Jan 4 '16 at 2:59
  • $\begingroup$ I want to understand why model complexity can vary with a fixed number of parameters (the idea of your second-to-last paragraph), and I am not having any luck googling "parameter entropy" or "ols parameter entropy". Did you use the concept of entropy because it just fits well or is this the actual, widely-known name of a property of model parameters? Thanks in advance. $\endgroup$ – Alvaro Fuentes Dec 4 '18 at 16:53
  • 1
    $\begingroup$ @AlvaroFuentes - Entropy, in this sense, comes from Information Theory. Here is the wikipedia article. Think of weights as a list, and you can compute the entropy of the system of all weights, using a kernel method to approximate the probability density. You could look at mean entropy per neuron to compare across neurons at a higher scale. $\endgroup$ – EngrStudent Dec 4 '18 at 21:05
0
$\begingroup$

A simple intuition is the following. Remember that for regularization the features should be standardized in order to have approx. the same scale.

Let's say that the minimisation function is only the sums of squared errors:

$SSE$

Adding more features will likely reduce this $SSE$, especially if the feature is selected from a noisy pool. The feature by chance reduces the $SSE$, leading to overfitting.

Now consider regularization, LASSO in this case. The functions to be minimized is then

$SSE + \lambda \Sigma |\beta|$

Adding an extra feature now results in an extra penalty: the sum of absolute coefficients gets larger! The reduction in SSE should outweigh the added extra penalty. It is no longer possible to add extra features without cost.

The combination of feature standardization and penalizing the sum of the absolute coefficients restricts the search space, leading to less overfitting.

Now LASSO:

$SSE + \lambda \Sigma |\beta|$

tends to put coefficients to zero, while ridge regression:

$SSE + \lambda \Sigma \beta^2$

tends to shrink coefficients proportionally. This can be seen as an side effect of the type of penalizing function. The picture below helps with this:

enter image description here

The regularizing penalty function in practice gives a 'budget' for the parameters, as pictured above by the cyan area.

See that on the left, LASSO, the $SSE$ function is likely to hit the space on an axis; setting one of the coefficients to zero, and depending on the budget shrinking the other. On the right the function can hit of the axes, more or less spreading the budget over the parameters: leading to shrinkage of both of the parameters.

Picture taken from https://onlinecourses.science.psu.edu/stat857/node/158

Summarizing: regularization penalizes adding extra parameters, and depending on the type of regularization will shrink all coefficients (ridge), or will set a number of coefficients to 0 while maintaining the other coefficients as far as the budget allows (lasso)

$\endgroup$
  • 1
    $\begingroup$ You are just explaining the difference between lasso and ridge regression but the question is asking about the reason why regularization leads to lower complexity. $\endgroup$ – Sobi Dec 31 '15 at 19:52
  • $\begingroup$ Please read this section: "Adding an extra feature now results in an extra penalty: the sum of absolute coefficients gets larger! The reduction in SSE should outweigh the added extra penalty. It is no longer possible to add extra features without cost." $\endgroup$ – spdrnl Jan 1 '16 at 10:47
  • $\begingroup$ This explanation only works for the $L_1$ regularizer and there has to be more to it than just sparsity. For example, $\exists \lambda$ for which all the parameter values in the learned model are non-zero. But still $\lambda$ controls the complexity of the model in that regime too. How would you explain that? Similarly, for $L_2$ regularization. $\endgroup$ – Sobi Jan 2 '16 at 1:14
  • $\begingroup$ The gist is that the type of penalty for adding parameters is going to affect the parameters in different ways. In practice you get a model with parameters that fit the training data less precise: that was sort of the goal. $\endgroup$ – spdrnl Jan 2 '16 at 21:02
0
$\begingroup$

By adding Guassian noise to the input, the learning model will behave like an L2-penalty regularizer.

To see why, consider a linear regression where i.i.d. noise is added to the features. The loss will now be a function of the errors + contribution of the weights norm.

see derivation: https://www.youtube.com/watch?v=qw4vtBYhLp0

$\endgroup$
0
$\begingroup$

I remember in a university class my teacher said penalizing large parameters can reduce overfitting because it prevents the model from putting too much weight on specific features in data, which causes overfitting since the model is just remembering some specific characteristics of the data and relate it to the label instead of trying to learn general rules.

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