Image: Mywood, public domainHow a random forest makes a decision
Take the Palmer penguins: 344 birds, three species, and four measurements of each. A decision tree for the species asks a question about one measurement, splits the birds into two groups by the answer, and asks another question of each group. Flipper length above 206 mm? Nearly every bird that answers yes is a gentoo. Among the rest, bill length above 43 mm? Mostly chinstraps; below, mostly Adelies. Three questions, and about 95 per cent of the penguins are correctly classified. The tree can be drawn on a napkin and explained to anyone.
A random forest is several hundred such trees, each slightly different, voting. It gives up the napkin and gains accuracy, and the reason it gains accuracy is worth understanding, because it is the same reason that a sample mean is more precise than a single observation.
How one tree is grown
At each step the tree considers every variable and every possible cut point and chooses the split that makes the two resulting groups purest. Purity is measured by the Gini index: for a group in which the three species have proportions \(p_1, p_2, p_3\), the index is \(1 - p_1^2 - p_2^2 - p_3^2\), which is zero when the group is all one species and largest when the species are evenly mixed. The split that reduces the total Gini index most is taken, and the procedure repeats in each half until the groups are pure or too small to split. This is the CART algorithm of Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone, published in 1984.
A fully grown tree classifies its training data perfectly and new data poorly. It has memorized the penguins it saw, including the ones that were odd for their species, and its lower branches encode noise. Trees are also unstable: change a few penguins and the first split may move from flipper length to bill depth, and the whole tree below it changes. Instability is a fault in a single tree. It turns out to be the raw material of the forest.
Many trees, and the arithmetic of averaging
Breiman's first idea, in 1996, was bagging, short for bootstrap aggregating. Draw a bootstrap resample of the data, 344 penguins drawn with replacement from the 344, grow a full tree on it, and repeat a few hundred times. To classify a new penguin, let every tree vote and take the majority. Each tree is overfitted to its own resample, but the resamples differ, so the trees overfit in different directions, and the errors partly cancel in the vote.
The gain is the one that averaging always gives. The variance of the average of \(B\) quantities with variance \(\sigma^2\) and pairwise correlation \(\rho\) is
\[ \rho\sigma^2 + \frac{1 - \rho}{B}\sigma^2. \]The second term vanishes as the number of trees grows. The first does not, and it is the problem with bagging: trees grown on overlapping resamples of the same data are strongly correlated, since they tend to pick the same dominant variable for their first split, and correlated trees do not average away.
The random forest, Breiman's 2001 paper, attacks \(\rho\). At every split, each tree is allowed to consider only a random subset of the variables, typically the square root of their number, so with four penguin measurements two of them, and with 20,000 genes about 140. A tree that is not permitted to look at flipper length at its first split must find another way, and the trees become different from one another in a way that bagging alone does not achieve. The correlation drops, the first term shrinks, and the vote improves. The method is almost absurdly simple, has essentially one tuning parameter, and on most problems with tabular data is close to the best that can be done. The paper is in the journal Machine Learning and is free to read.
The error that comes free
Each tree is grown on a bootstrap resample, and a bootstrap resample leaves out about 37 per cent of the observations, as the article on the bootstrap explains. For every penguin, then, roughly a third of the trees never saw it. Classify each penguin by the votes of only those trees and compare with its true species: the resulting error rate is an honest estimate of how the forest will do on new penguins, obtained without setting aside any data. Breiman called it the out-of-bag error, and it agrees closely with cross-validation at no extra cost.
The same trick measures which variables matter. Scramble one variable's values among the out-of-bag penguins and see how much the error rises; a variable the forest relies on produces a large rise, a useless one none. Variable importance of this kind is the main reason forests are used in fields like genomics and ecology, where the question is as often "which measurements carry the information" as "what is the prediction". Breiman's own page describing the method, written for users, is still online at Berkeley.
Boosting, the other way to combine trees
A forest grows its trees independently and averages them. Boosting grows them in sequence, each one fitted to the errors of the ensemble so far, and adds them up with small weights. Freund and Schapire's AdaBoost of 1997 did this for classification by reweighting the misclassified cases; Friedman's gradient boosting of 2001 generalized it to any loss function by treating the sequence as a slow descent, and implementations such as XGBoost and LightGBM have won most prediction competitions on tabular data since. Boosting is usually a little more accurate than a forest and much easier to overfit, since it keeps fitting the residuals until stopped. Both are in Unit 15 of the Statistics Masterclass, with Friedman and Peter Bühlmann as the research spotlights.
What is lost
The napkin. A single tree can be read; five hundred trees cannot, and a forest's decision about one penguin is the sum of a thousand small rules nobody will inspect. Variable importance and partial dependence plots recover some of the picture. For a decision that must be explained to the person it affects, a loan, a diagnosis, a sentence, the loss matters, and the choice between the tree that can be read and the forest that is right more often is not a statistical one.
Unit 15 of the Statistics Masterclass grows the penguin tree by hand, derives the variance formula above, and builds a small forest on the same data so that the out-of-bag error can be computed and compared with the truth. The dataset of the week is OpenML, where the recorded results of forests and boosted models on hundreds of datasets can be compared without running either.


