4 ms·

I would have assumed the opposite, with enough trees you are guaranteed to overfit your data? Boosting increases the VC dimension of the aggregate model, which

by yters 7y ago

I would have assumed the opposite, with enough trees you are guaranteed to overfit your data? Boosting increases the VC dimension of the aggregate model, which makes it more prone to overfitting.

pplonski86 7y ago
Random Forest doesn't increase overfit error when adding more trees. I did the experiment on toy dataset to check it https://mljar.com/blog/random-forest-overfitting/ https://mljar.com/blog/random-forest-overfitting/ What is more, Leo Breimain wrote on his website: "Random forests does not overfit. You can run as many trees as you want" https://www.stat.berkeley.edu/~breiman/RandomForests/cc_home.htm#remarks https://www.stat.berkeley.edu/~breiman/RandomForests/cc_home...
- rq1 7y ago
  These are (false) claims, therefor not proofs. Deep trees will fortunately overfit your dataset. Any binary tree of depth log2(P) can completely separate your P points.
  - ramraj07 7y ago
    But we are merging hundreds of trees each of which has been handicapped by removal of multiple features and a fraction of the data. Sounds to me like overfitting is not easy (no single data point or feature contributes to every tree so it can't be represented all the time). False claims as they maybe, these are claims I've seen in at least two of the most commonly studied statistical learning text books, so given that it makes sense and that it's in the text books, it seems reasonably not false to me. Someone else posted that if too many features or data points are very similar then it will overfit, and that totally makes sense. Whatever you say doesnt. Clarification would be useful.
    - yters 7y ago
      Adding bunches of trees will overfit the accidental patterns in your data. I have an explanation here why reducing variance is not the same as reducing overfitting: https://news.ycombinator.com/item?id=20089890 https://news.ycombinator.com/item?id=20089890
  - thom 7y ago
    Yeah, at a certain point it's just playing 20 questions with your data.
olooney 7y ago
Random Forest doesn't use boosting. Tree models like XGBoost which do use boosting are indeed very prone to overfitting.
gbrown 7y ago
Nope, RF works very different to boosting. RF trees give unbiased fits, but they're high variance. Bootstrapping is used to reduce the variance of the parallel tree fits. Boosting is sequential, and relies on early stopping to control the magnitude of bias.
- rq1 7y ago
  > RF trees give unbiased fits, but they're high variance. Sounds like overfitting.
  - olooney 7y ago
    Individual trees are high variance. The random forest itself is an ensemble of many trees - a "forest" if we've being cute. Each tree in the forest is randomized training on a bootstrap sample. This is sometimes called "bagging", a portmanteau of "bootstrap" and "aggregating." Each tree may be further randomized by selecting a different subset of dimensions to consider each time we split a node. The end result is that each tree uses very different rules to make its prediction. When all of these predictions are combined (by voting for classification, or by averaging for regression) error due to overfitting tends to cancel out, while signal due to the same true pattern being discovered independently by many trees is amplified. Thus we can continue to add trees indefinitely without worrying about over-fitting. Other hyperparameters of random forest, such as max tree depth or the minimum number of samples in a node necessary for splitting, can result in overfitting or underfitting so need to be tuned. However, because forest will eventually fit the data set even if we use so-called "stump" learners (max tree depth=1) we can choose very conservative parameters like max-depth=3 which makes trees less likely to overfit. And if they underfit, well, that's not a problem, the ensemble will take care of that. The number of trees in a forest can be cranked up as high as we want without worrying about overfitting; the only downside is that training takes longer, the model takes more space on disk and in memory, and predictions take longer to run.
    - yters 7y ago
      Ensemble models increase VC dimension so they are more prone to overfitting. Example, you could have a tree that individually segments each data point and memorize your dataset. That's the definition of overfitting.

by yters 7y ago

I would have assumed the opposite, with enough trees you are guaranteed to overfit your data? Boosting increases the VC dimension of the aggregate model, which makes it more prone to overfitting.

pplonski86 7y ago

Random Forest doesn't increase overfit error when adding more trees. I did the experiment on toy dataset to check it https://mljar.com/blog/random-forest-overfitting/ https://mljar.com/blog/random-forest-overfitting/ What is more, Leo Breimain wrote on his website: "Random forests does not overfit. You can run as many trees as you want" https://www.stat.berkeley.edu/~breiman/RandomForests/cc_home.htm#remarks https://www.stat.berkeley.edu/~breiman/RandomForests/cc_home...

rq1 7y ago
These are (false) claims, therefor not proofs. Deep trees will fortunately overfit your dataset. Any binary tree of depth log2(P) can completely separate your P points.
- ramraj07 7y ago
  But we are merging hundreds of trees each of which has been handicapped by removal of multiple features and a fraction of the data. Sounds to me like overfitting is not easy (no single data point or feature contributes to every tree so it can't be represented all the time). False claims as they maybe, these are claims I've seen in at least two of the most commonly studied statistical learning text books, so given that it makes sense and that it's in the text books, it seems reasonably not false to me. Someone else posted that if too many features or data points are very similar then it will overfit, and that totally makes sense. Whatever you say doesnt. Clarification would be useful.
  - yters 7y ago
    Adding bunches of trees will overfit the accidental patterns in your data. I have an explanation here why reducing variance is not the same as reducing overfitting: https://news.ycombinator.com/item?id=20089890 https://news.ycombinator.com/item?id=20089890
- thom 7y ago
  Yeah, at a certain point it's just playing 20 questions with your data.

olooney 7y ago

Random Forest doesn't use boosting. Tree models like XGBoost which do use boosting are indeed very prone to overfitting.

gbrown 7y ago

Nope, RF works very different to boosting. RF trees give unbiased fits, but they're high variance. Bootstrapping is used to reduce the variance of the parallel tree fits. Boosting is sequential, and relies on early stopping to control the magnitude of bias.

rq1 7y ago
> RF trees give unbiased fits, but they're high variance. Sounds like overfitting.
- olooney 7y ago
  Individual trees are high variance. The random forest itself is an ensemble of many trees - a "forest" if we've being cute. Each tree in the forest is randomized training on a bootstrap sample. This is sometimes called "bagging", a portmanteau of "bootstrap" and "aggregating." Each tree may be further randomized by selecting a different subset of dimensions to consider each time we split a node. The end result is that each tree uses very different rules to make its prediction. When all of these predictions are combined (by voting for classification, or by averaging for regression) error due to overfitting tends to cancel out, while signal due to the same true pattern being discovered independently by many trees is amplified. Thus we can continue to add trees indefinitely without worrying about over-fitting. Other hyperparameters of random forest, such as max tree depth or the minimum number of samples in a node necessary for splitting, can result in overfitting or underfitting so need to be tuned. However, because forest will eventually fit the data set even if we use so-called "stump" learners (max tree depth=1) we can choose very conservative parameters like max-depth=3 which makes trees less likely to overfit. And if they underfit, well, that's not a problem, the ensemble will take care of that. The number of trees in a forest can be cranked up as high as we want without worrying about overfitting; the only downside is that training takes longer, the model takes more space on disk and in memory, and predictions take longer to run.
  - yters 7y ago
    Ensemble models increase VC dimension so they are more prone to overfitting. Example, you could have a tree that individually segments each data point and memorize your dataset. That's the definition of overfitting.