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 hundreddimensional 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 tendimensional 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.

$\begingroup$ I imagine it has too, but I also do not know the name. Perhaps partial training or retraining? Anyway, a good machine learning text with a decent index and table of contents might help. Try browsing some of those. Gerhard "Ask Me About System Design" Paseman, 2012.06.22 $\endgroup$ – Gerhard Paseman Jun 22 '12 at 18:21

3$\begingroup$ en.wikipedia.org/wiki/Bootstrap_aggregating $\endgroup$ – R Hahn Jun 22 '12 at 18:25
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, mdlresearch.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.
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.
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".
I think the best answer to what I wanted to know was the term "bootstrap aggregating" in the comment by R. Hahn. Thanks!

$\begingroup$ You can edit this to make it communitywiki (CW). Although hardly anyone cares, it is considered polite not to get reputation points for others answers. Also, you could improve on this answer by saying a little more about why it answers your question. In any case, your update is appreciated. Gerhard "Ask Me About System Design" Paseman, 2012.06.24 $\endgroup$ – Gerhard Paseman Jun 24 '12 at 19:17

$\begingroup$ I guess I should have written this as a comment instead of an answer? I modified the question to be community wiki because you suggested it, though I don't know what that is for. $\endgroup$ – Doug SummersStay Jun 25 '12 at 11:59

$\begingroup$ I meant that the answer be made CW. I apologize for not making that clear. Gerhard "Ask Me About System Design" Paseman, 2012.06.26 $\endgroup$ – Gerhard Paseman Jun 27 '12 at 4:47