Over fitting and association with regularization

Question

Heard and read lot about regularization helps in reducing over fitting. But I'm not sure how exactly regularization works in reducing over fitting issue and whats the maths behind it? Appreciate if can somebody provide a concrete example?

Answer 1

The short answer is that regularization penalizes model complexity. It does this by adding some function of your parameters to your basic cost function as a regularization term. This forces a compromise between a good fit (low error) on your training data and model simplicity by driving the parameters closer to zero. This reduces overfitting because large parameters (in terms of magnitude) are the main culprit behind overfitting.

For example, L1 regularization uses the sum of the absolute values of your weights, while L2 regularization uses the squares of your weights. More detailed comparison here.

For mathematical details, have a look at this answer.

Answer 2

It depends on what regularization you have in mind, as there are many forms.

Taking the simple example of ridge regression, which adds an L2 penalty on weights, $\lambda\sum_i\omega_i^2$. It's obvious that constrains weights towards zero, but maybe you are asking where that comes from.

I prefer the Bayesian interpretation of it, that this corresponds to a Gaussian prior on the weights. It will mean that all you think you know about the weights beforehand is that they're most likely 0 (mean 0), that as far as you know they're not related (independent), and they are more likely to be near 0 than far from it, in the same way (standard deviation $\sigma$ where choosing smaller $\sigma$ means you think the weights are more likely to be near 0).

This comes from thinking of regression as finding the parameters that are most likely given the data, $P(\omega|X)$, which is proportional to $P(X|\omega)P(\omega)$ by Bayes's rule. Maximizing this probability means maximizing its logarithm too, or $\log(P(X|\omega)) + \log(P(\omega))$. It's the second term that results in the regularization term.

If $P(\omega)$ is multivariate Gaussian, or $N(0, \Sigma)$ then its distribution is (ignoring the big multiplicative constant in front which won't matter): $e^{-\frac{1}{2}\omega^T\Sigma^{-1}\omega}$. Its log, throwing away constants again that won't matter, is $-\omega^T\Sigma^{-1}\omega$, and maximizing it means minimizing $\omega^T\Sigma^{-1}\omega$.

The covariance matrix $\Sigma$ is however simple here; because the prior probabilities are independent, it's a diagonal matrix, and because we assume equal variance, they just have the same value on the diagonal, which we'll call $\frac{1}{\lambda}$. Its inverse is a diagonal matrix with $\lambda$ on the diagonal ($\lambda I$). $\omega^T\omega$ would just be the dot of $\omega$ with itself, which is its L2 norm, or $\sum_i\omega_i^2$. And the $\Sigma^{-1}$ in the middle just ends up meaning the whole thing is multiplied by $\lambda$. Hence we minimize $\lambda\sum_i\omega_i^2$ as desired.

That's the connection between the regularization and what it "means": you don't believe all weights are likely, you believe they're near 0 with higher $\lambda$ meaning smaller variance $\frac{1}{\lambda}$ and thus implying you believe more strongly the weights are near 0. Adding this term makes the computation balance the likelihood of the data with the prior likelihood of the weights it would take to achieve that likelihood.