The encyclopedia · R&D & Science · Technical decision · 2001
Random forests averaged many noisy trees into a robust predictor
Breiman grew thousands of randomized trees and averaged them, cutting variance while keeping each tree strong.
University of California, Berkeley
The solution
Decision trees were accurate but unstable: small changes in data changed the whole tree, and a single tree overfit. Leo Breiman's 2001 paper, 'Random Forests', attacked both problems by building a forest instead of a tree.
Every tree is grown on a bootstrap sample of the data, and each split considers only a random subset of features. The randomness makes trees different; the bootstrap makes them strong. Averaging their votes cancels individual errors.
Breiman proved the generalization error converges as the forest grows and depends on the strength of individual trees and the correlation between them. Out-of-bag samples provide internal error, strength and importance estimates, and the method matched AdaBoost's accuracy while resisting noise better.
Why it worked
- Bootstrap samples make every tree different
- Random feature subsets decorrelate the errors
- Averaging cancels variance without raising bias
- Out-of-bag data give free error estimates
What can be applied
If one model is brittle, stop hunting for a perfect one: average many deliberately randomized versions. Noise per tree is fine when the ensemble cancels it, and randomness is cheaper than tuning.
Aftermath
Random forests became one of the most widely used off-the-shelf machine-learning methods, staying competitive long after deep learning took over image and text tasks, and its ideas shaped the gradient-boosting ensembles that followed.
Sources
spotted an error? The archive wants to know.