Why do smaller weights result in simpler models in regularization?

Question

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.

Answer 1

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.

Answer 2

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).

Answer 3

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.

Answer 4

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:

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)

Answer 5

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