Question

I was thinking about the problem of overfitting data. Suppose you have a hundred data points sampled from an unknown function (call this the training set). You could try fitting a hundred-dimensional polynomial to these points, but even though it fits all the sample points exactly, it probably wouldn't do a good job of fitting other points sampled from the same function (the test set). This is called overfitting the training set. So suppose you were to do this instead: choose ten points from the training set, and fit a ten-dimensional polynomial to them. Then do it again, with another ten random sampled points. Get a bunch of polynomials this way, and take an average of their predictions. Wouldn't that do a better job of avoiding overfitting? Surely someone else has had this idea before. I'm looking for what it is called, so I can read up on it.

Answer 1

The modern approach to avoid overfitting is to be found in Minimum Description Length, based on Bayesian probability (and closely linked with Kolmogorov Complexity). You can learn more about MDL at Wikipedia, Scholarpedia, mdl-research.org, or the wonderful book by Grünwald.

MDL basically gives you a principled way to trade off between model size (i.e. size of the polynomial used) and error.

Answer 2

A slightly more complicated method is called "early stopping." You split the data set into a training set and a validation set, and only train until the error on the validation set stops going down. Then you redivide the data. Repeat.

Answer 3

I doubt if that is a very good idea, but it may be related to "Boosting", which is a kind of comittee method: Use many weak predictors and combine their output. See chapter 10 of Haste, Tibshirani, Friedman: "The Elements of Statistical Learning".

Answer 4

I think the best answer to what I wanted to know was the term "bootstrap aggregating" in the comment by R. Hahn. Thanks!