7
$\begingroup$

So I've been trying to algebraically prove that overfitting a model leads to greater variance values for the parameter estimates. I've gotten close (reduced the problem to showing a certain matrix is positive definite) but I don't really like the approaches I've taken and I'd like to see if there's a simpler way.

If anyone knows of a good strategy to use, or a pre-existing proof it would be appreciated, thanks!

Improve this question
$\endgroup$
3
  • $\begingroup$ what exactly do you mean by overfitting? $\endgroup$
    – Aksakal
    Commented Mar 2, 2014 at 19:46
  • 1
    $\begingroup$ @Aksakal, that's essentially right--we usually define overfitting in terms of the model's performance in out of sample prediction. So this is a non-standard use of the term. However, used in this way, it is true that the variance of a parameter estimate will increase as more variables are added w/o increasing N (ie, as the number of variables, p, goes to N). $\endgroup$
    – gung - Reinstate Monica
    Commented Mar 2, 2014 at 20:55
  • $\begingroup$ @user2891466, I didnt read your question right. thought you meant the error variance, not the variance of parameter estimates, sorry. On a related note, I read just recently that overfitting in practice is not as bad as it seems theoretically, that it basically a benign problem. I'll try to find that reference $\endgroup$
    – Aksakal
    Commented Mar 2, 2014 at 20:56

3 Answers 3

Reset to default
2
$\begingroup$

Both answers posted so far are useful (+1) but let me present this in a slightly different way using the Minimum description length principal. The basic idea behind MDL is related to Kolmogorov Complexity and the concept of the minimum sized program required to reproduce a sequence. The MDL principle states that one should prefer models that can communicate the data in the smallest number of bits Hastie09. As Shannon's source coding theorem has shown the expected code message length for a given prefix code (ie. model) is : $L = -\Sigma_{a\epsilon A} P(a) \log_2 P(a)$ where $A$ is the set of all possible messages we would like to transmit; if we write this for an infinite set of messages (effectively something in $R$) $L = -\int P(a) \log_2 P(a) da$. One can therefore see that in terms of bits we need $-\log_2P(a)$ bits to transmit a random variable $a$ with probability density function $P(a)$. Now given that when transmitting a dataset $y$ of model outputs one effectively has to transmit it by sending the best fit parameters of the model $m_i$, $\theta^*$, as well as the discrepancy between the original data and the fitted data, one can write the total length as : \begin{align} L = (-\log_2 Pr(\theta^*|m_i)) + (- \log_2 Pr(y|\theta^*,m_i)) \end{align} So while you will decrease the second term by over-fitting, you will increase your first term by adding "redundant" information. In essence you will increase the variance of $\theta^*$ unnecessarily.

This is by no means a (formal) proof but I thought it might be fun to consider. :)

Improve this answer
$\endgroup$
5
$\begingroup$

The references you want is The Analysis of Market Demand (JSTOR) by Richard Stone, Journal of the Royal Statistical Society, Vol. 108, No. 3/4 (1945), pp. 286-391. I can't find an ungated link, so here's the gist of it.

He gives a formula for the estimated variance of OLS regressor $\beta_k$ in a regression of $y$ on $K$ variables as $$ \frac{1}{N-K}\cdot\frac{\sigma^2_y}{\sigma^2_k}\cdot\frac{1-R^2}{1-R^2_k}, $$ where $\sigma^2_y$ is the estimated variance of $y$, $\sigma^2_k$ is the estimated variance of $x_k$, $R_k^2$ is from the regression of $x_k$ on $K-1$ remaining independent variables, and $N$ is the sample size. The set of $K$ already includes a constant.

Now we make L'Hospital and the Bernoullis spin in their tombs with some terrible math.

To overfit, fix $N$ and start adding variables ($K \rightarrow N$). As you do this, both of the $R^2$s approach 1 since they are a monotonic function of $K$. The middle fraction remains constant since $N$ is fixed. The first fraction grows since you're dividing by something closer and closer to zero.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ The denominator of the right fraction is the tolerance associated w/ $x_k$. If the variables are orthogonal, the tolerances will all be 0, so in that case, the right fraction would stay constant at $1-R^2$. All the action would be in the denominator of the left fraction going to zero. $\endgroup$
    – gung - Reinstate Monica
    Commented Mar 2, 2014 at 20:48
  • 2
    $\begingroup$ Keep in mind that one byproduct of overfitting can be the gross underestimation of standard errors of parameter estimates. So you should concentrate on real variances and not apparent variances. $\endgroup$
    – Frank Harrell
    Commented Mar 2, 2014 at 20:49
  • $\begingroup$ @gung Do you mean to say that $R^2$ is weakly increasing with $K$? I am unfamiliar with the term tolerance. $\endgroup$
    – dimitriy
    Commented Mar 2, 2014 at 20:53
  • 1
    $\begingroup$ See #4 here. It is possible (in an experiment) for a variable to be perfectly independent of other variables, even as the number of variables grows. (In observational research, that will essentially never happen.) The right fraction is an important part of the result, but the most general piece is the left fraction. $\endgroup$
    – gung - Reinstate Monica
    Commented Mar 2, 2014 at 21:00
  • $\begingroup$ I didn't know there was a word for that! Any idea on the etymology? $\endgroup$
    – dimitriy
    Commented Mar 3, 2014 at 21:35
3
$\begingroup$

Basically, you are asking for an interpretation of Occam's razor in therms of probability; quoting from wikipedia, Occam's razor:

is a principle of parsimony, economy, or succinctness used in problem-solving. It states that among competing hypotheses, the one with the fewest assumptions should be selected.

I can direct you to this paper[0]. There, the authors generalize and quantify the original formulation's "assumptions" concept as

the degree to which a proposition is unnecessarily accommodating to possible observable data

In a nutshell, given an equal fit, simpler prior have higher posteriors. Again, quoting from wikipedia;

all assumptions introduce possibilities for error; if an assumption does not improve the accuracy of a theory, its only effect is to increase the probability that the overall theory is wrong.

In essence, given an equal fit of the observed data, simpler models are preferred over models which would have accommodated a wide range of other possible data because they have a higher probability of being true.

[0]:Jefferys W. H. and Berger J. O. (1991). Sharpening Ockham's Razor On a Bayesian Strop.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.