On this page
The random forest algorithm is credited to Leo Breiman, a statistician at the University of California, Berkeley. You can try his idea with a pencil.
Who invented the random forest algorithm?
Leo Breiman published “Random Forests” in the journal *Machine Learning* in October 2001, says the Crossref record for the paper. His own preprint defines a random forest as a collection of tree classifiers in which “each tree casts a unit vote for the most popular class”. The paper also credits earlier work, such as Tin Kam Ho's “random subspace” method and a paper by Amit and Geman that Breiman says “has been influential in my thinking”.
The University of California memorial records that he was born in New York City on 27 January 1928, earned a PhD in mathematics at Berkeley in 1954, taught probability at UCLA, and then worked as a consultant for government and industry for 18 years. He joined Berkeley's Department of Statistics in 1980, was elected to the National Academy of Sciences, and died at his Berkeley home on 5 July 2005.
He co-wrote *Classification and Regression Trees* (CART) with Jerome Friedman, Richard Olshen and Charles Stone, so decision trees were his building block. The Random Forests page at Berkeley names Adele Cutler as co-holder of the trademark.
What is bagging, and why did it work?
Bagging came first. In a 1994 Berkeley technical report, “Bagging Predictors”, published in *Machine Learning* in August 1996 (Crossref record), Breiman described building many versions of one predictor and combining them. The name is short for “bootstrap aggregating”.
A bootstrap sample is a new data set of the same size, drawn at random from the original *with replacement*, so some cases appear twice and some not at all. This is the resampling behind Bradley Efron's bootstrap for estimating uncertainty. In bagging, each sample trains its own tree, and the trees vote on a class or are averaged for a number.
Using 50 bootstrap replicates, bagged classification trees cut test-set misclassification rates by 20% to 47% across the data sets Breiman tried, his report says. He explained when it helps: “If perturbing the learning set can cause significant changes in the predictor constructed, then bagging can improve accuracy.” For stable methods, it can slightly hurt.
How does a random forest make a decision?
Random forests add one more dose of randomness: at each split, only a small random set of input variables is considered, and the best split among those is used, the Berkeley Random Forests guide explains. Trees are grown fully, with no pruning. Breiman's 2001 paper showed that a forest's accuracy depends on how strong each tree is and how correlated the trees are; random splits make the trees less alike.
The same guide notes that about one-third of the cases are left out of each bootstrap sample. These “out-of-bag” cases act as a built-in test set.
Worked example: will it rain tomorrow?
Say you have 10 days of weather data (humidity, cloud cover, pressure) and whether it rained the next day.
Resample. For Tree 1, draw 10 days with replacement. One draw gives days 1, 2, 2, 4, 5, 7, 7, 7, 9 and 10. Days 3, 6 and 8 were never picked: they are out-of-bag.
Grow with random splits. At each split, Tree 1 tries one randomly picked variable.
Repeat for Trees 2 to 5. In our five draws, 15 of the 50 day-slots were out-of-bag, or 30%, close to Breiman's “about one-third”.
Vote. For tomorrow's readings, Trees 1, 3 and 4 say “rain” and Trees 2 and 5 say “dry”. The forest predicts rain, 3 votes to 2.
Check. For each day, let only the trees that never saw it vote; the share of days where that vote is wrong is your out-of-bag error estimate.
To see how one tree picks its splits, build a decision tree on paper first. If sampling with replacement or majority voting still feels shaky, the Fermi Concept Library has a lesson for every concept in mathematics and computing, each with its place in the map.
Why does Breiman's work still matter?
In “Statistical Modeling: The Two Cultures”, published in *Statistical Science* in 2001, Breiman urged statisticians to look beyond assumed data models to algorithmic models that treat how the data was made as unknown, the kind random forests are.
The Berkeley forest guide measures variable importance by shuffling one variable's values in the out-of-bag cases and seeing how much the votes get worse. It also answers a common worry: “Random forests does not overfit. You can run as many trees as you want.” That is about adding trees; new to overfitting? Try the past-paper analogy for overfitting.
How can you try it yourself?
Do the rain example above by hand with three trees.
Then try a machine learning library on a small data set you know.
If you are not sure where to start, Fermi's AI tutor can work out what you already know and build a plan for the session, so you begin with the right step.
