Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

There are many examples in which making more "precise" predictions gives worse performance (e.g. Runge's phenomenon). My professor implied that there was a sound basis for choosing "simple" functions over complex ones in the general case, and that it had to do with information theory.

Does anyone know what he was referring to?

As an example: consider least square's. Obviously we could find a polynomial of very high degree which has zero error, but we prefer a linear equation with higher error. Why should this be?

(I am familiar with some basic notions like entropy, but not much more than that, so simpler explanations would be much preferred. Although I understand that if it's complex, it's complex.)

share|cite|improve this question
For doing what? – Qiaochu Yuan Dec 21 '10 at 0:51
@Qiaochu: The specific example was interpolation by a polynomial, and why splines are preferred to interpolating at a large number of points. I understood him to mean it was a general phenomenon though. – Xodarap Dec 21 '10 at 0:55
The problem with high-degree polynomials is that they tend to wiggle. A lot. – J. M. Dec 21 '10 at 1:08
Also, the adage "high order does not imply high accuracy" applies as well. – J. M. Dec 21 '10 at 1:08
This might be helpful. – user17762 Dec 21 '10 at 1:09
up vote 4 down vote accepted

Look up VC theory (named after Vapnik and Chervonenkis), and especially Structural Risk Minimization (SRM).

share|cite|improve this answer
1 for instance – isomorphismes May 18 '11 at 3:43

There's a fundamental tradeoff in inference between simplicity and accuracy. More accurate prediction require greater complexity, and are liable to 'overfit' - which is essentially learning something from small sample sizes that isn't actually there in the distribution itself (or large sample sizes).

In IT, the tradeoff is often canonicized by entropy - we shoot for a distribution that maximizes the entropy, subject to some constraints which we are willing to take (usually these come from the data). For example, suppose you are flipping a coin, and trying to decide whether the coin is fair. First flip its heads. Should you conclude at this point that the coin is biased to always land hands? Of course not! That would be major overfit. Now, if you flipped 10 times and it was heads every time, that would qualify as 'more constraints', thus allowing you to narrow down the true distribution (maybe its 90% heads, 10% tails).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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