Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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 –  Gerhard Paseman Jun 22 '12 at 18:21
3  
add comment

4 Answers 4

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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".

share|improve this answer
add comment

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

share|improve this answer
    
You can edit this to make it community-wiki (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 –  Gerhard Paseman Jun 24 '12 at 19:17
    
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. –  Doug Summers-Stay Jun 25 '12 at 11:59
    
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 –  Gerhard Paseman Jun 27 '12 at 4:47
add comment

Your Answer

 
discard

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.