Random forests: Strength from uncorrelated trees

The paper and the narrow claim

In October 2001 the journal Machine Learning published "Random Forests", a paper by Leo Breiman of the statistics department at the University of California, Berkeley, filling pages 5 to 32 of volume 45 ( the journal record of Random Forests). The ideas were already in circulation. Berkeley lists Technical Report 567, Random Forests, Random Features, dated September 1999, whose abstract states the core results, and Breiman posted a revised version dated January 2001 whose abstract adds internal measures of variable importance. The 1999 report is the announcement; the 2001 journal article is the archival version the field cites, which is why Chronicle dates the event to 2001.

The paper defines a random forest in one sentence: a classifier made of many tree-structured classifiers, each grown using its own random vector drawn independently from the same distribution, each casting one vote for the most popular class. The narrow, documented claim is specific. Trees grown on bootstrap samples, with a small random set of input variables considered at each split, rivaled AdaBoost, the strongest ensemble method of the day, on test error across twenty datasets. They suffered far less from mislabeled training data, ran faster, and supplied internal estimates of their own error and of each variable's importance. The broader judgment, that this became one of the most used methods in applied machine learning, rests on the two decades that followed, and the two levels of claim should be kept apart.

Why single trees needed rescuing

Breiman came to this problem from decision trees he had helped invent. With Jerome Friedman, Richard Olshen and Charles Stone he wrote Classification and Regression Trees, the 1984 book behind the CART method, as Adele Cutler recounts in her remembrance of Breiman in the Annals of Applied Statistics. Cutler also describes his unusual route: he resigned a tenured probability post and spent about thirteen years as a consultant, and a classification tree first occurred to him while sorting ship types from radar profiles. Berkeley's obituary adds that the consulting covered freeway traffic, court bottlenecks and next-day ozone levels in the Los Angeles basin before he joined the Berkeley faculty in 1980.

Trees are readable and handle mixed numeric and categorical inputs, but they are unstable: a small change in the training data can produce a very different tree. Breiman's 1994 technical report on bagging predictors, published in Machine Learning in 1996, turned that weakness into a lever. Bagging, short for bootstrap aggregating, draws repeated samples of the training set with replacement, fits a predictor to each, and lets them vote or averages them. The report argued that the gain depends on instability, naming neural networks, trees and subset selection in regression as unstable and nearest-neighbor methods as stable. On its test datasets, bagged classification trees cut misclassification by 20 to 47 percent and bagged regression trees cut mean squared error by 22 to 46 percent.

Bagging was not the end of the story. By the late 1990s boosting, which reweights the training cases each new tree gets wrong, usually beat it. Thomas Dietterich's comparison of bagging, boosting and randomization for C4.5 trees found that with little label noise, randomizing the tree was competitive with bagging but not as accurate as boosting, while with substantial noise bagging did much better than boosting. That was the bar the 2001 paper set out to clear: boosting's accuracy without boosting's fragility.

Three earlier ways to randomize a tree

Random forests were a synthesis, and the paper says so. Tin Kam Ho presented Random Decision Forests at the 1995 document analysis conference in Montreal and developed it into the random subspace method for constructing decision forests in 1998, in which each tree is built on a pseudorandomly chosen subset of the feature components, so that the forest can keep growing in complexity while its accuracy on unseen data improves.

Yali Amit and Donald Geman reached a related idea from handwriting recognition. In their 1997 Neural Computation paper on randomized trees the candidate features were spatial arrangements of local image tags, a family so large that no tree could search it. They sampled a small random set of queries at each node, grew several trees, and classified an image by sending it down every tree and pooling the results, reporting state-of-the-art error rates on the NIST handwritten digits. Dietterich's randomized C4.5 took a third route: at each node it computed the 20 best splits and picked one uniformly at random, tested on 33 UCI datasets.

Breiman's paper names Ho's random subspace work and Dietterich's random split selection, and calls the Amit and Geman paper influential in his thinking ( Berkeley version). In the Berkeley version, his reference list cites Ho's 1998 journal article rather than the 1995 conference paper that first put the phrase random decision forests into print. What Breiman added was not the idea of a randomized tree. It was a general definition covering all these schemes, a theory of why they work, a particular recipe (bootstrap samples plus per-node random feature selection) tuned and benchmarked against AdaBoost, and diagnostics that made the forest inspect itself.

How the algorithm works

The basic version, which Breiman called Forest-RI, takes three steps. Draw a bootstrap sample the size of the training set. Grow a tree on it with the CART method to its maximum size, without pruning, but at every node consider only F input variables chosen at random and split on the best of those. Repeat many times, then let the trees vote for a class, or average their outputs for regression. Breiman tried two values of F: a single random variable, or the integer part of log2 M + 1, where M is the number of inputs. For a dataset with 1,000 inputs that second rule gives 10 variables per node. A variant, Forest-RC, split instead on random linear combinations of three inputs with coefficients drawn uniformly between minus one and one.

Later software settled the defaults that most users now meet. Andy Liaw and Matthew Wiener's randomForest package for R, described in R News in December 2002 as an interface to Breiman and Cutler's Fortran programs, tries the square root of the number of predictors at each node for classification and a third of them for regression. The scikit-learn ensemble documentation notes one quiet departure from the paper: its forests average the trees' class probabilities instead of counting single votes.

Speed was part of the case. Searching F variables instead of all M scales the work of growing each tree by roughly F times log2 N divided by M, where N is the number of cases. On the zip code digits, with 256 inputs and F set to 1, Breiman computed a ratio of 0.025, about 40 times faster, and reported that 100 trees took 4.0 minutes on a 250 MHz Macintosh against almost three hours for AdaBoost ( Berkeley version).

Strength, correlation, and the no-overfitting theorem

The theory section is what lifted the paper above a bag of tricks. Using the strong law of large numbers, Breiman showed that as trees are added the forest's generalization error converges almost surely to a limit, so adding more trees cannot make the forest overfit. He then bounded that limiting error by the mean correlation between trees multiplied by one minus the strength squared, divided by the strength squared, where strength measures how far, on average, the correct class out-votes the strongest wrong one. He called the bound likely loose but suggestive, much as VC bounds are for other classifiers ( journal record). The design principle followed: inject randomness that lowers the correlation between trees while keeping each tree reasonably strong.

The experiments made the principle concrete. On the sonar data, with 60 inputs, Breiman varied F from 1 to 50 over 80 repetitions, about 400,000 trees in all. Past roughly F equal to 4 the strength stopped rising while the correlation kept climbing, so error fell slightly from F of 1 to about 4 to 8 and then crept upward. A synthetic problem with 1,000 weak binary inputs and ten classes showed the extreme case. With F at 25, individual trees misclassified about 60 percent of test cases, yet the forest reached 2.8 percent error against a Bayes rate of 1.0 percent and 6.2 percent for naive Bayes. AdaBoost could not be run at all, because its base classifiers were too weak ( Berkeley version).

The forest grades itself

Bagging supplied a free test set. Each bootstrap sample leaves out about one-third of the cases, so every training case can be predicted by the trees that never saw it. Aggregating those out-of-bag votes gives an estimate of the forest's error, which Breiman, citing his earlier study, said was as accurate as a test set the size of the training set, removing the need to hold data aside. Liaw and Wiener put the figure at about 36 percent of the trees for each point ( R News).

The same machinery measured importance. After each tree is grown, the values of one variable are randomly permuted among its out-of-bag cases, the cases are run down the tree again, and the rise in misclassification is recorded. On voting records of 435 members of Congress across 16 issues, scrambling the vote on issue 4 tripled the error, and a forest given only that vote reached 4.3 percent error, about the same as with all 16 ( Berkeley version). Breiman flagged the catch himself: two variables carrying the same information each look important when scrambled alone, yet the second adds nothing once the first is in.

This was the practical core of an argument he made in the same year. In Statistical Modeling: The Two Cultures, published in Statistical Science in August 2001, he contrasted statisticians who assume a stochastic data model, an approach he put at 98% of all statisticians, with an algorithmic culture that judges models by predictive accuracy. Random forests were his preferred method. He graded them A+ predictors that rate an F on interpretability, and offered variable importance as the way to extract reliable information from such a black box. On the 16 by 16 pixel ZIP Code digits long used at AT&T Bell Labs, he reported 6.2 percent error for a standard forest against 5.1 percent for a neural network handcrafted for the data.

What the 2001 experiments did and did not show

The main benchmark used 13 smaller datasets from the UCI repository, 3 larger ones with fixed training and test sets, and 4 synthetic problems. On the small sets, 10 percent of the data was held out, a forest of 100 trees was compared with AdaBoost combining 50 trees, and the exercise was repeated 100 times. Forest-RI's errors compared favorably with AdaBoost's, and Forest-RC did better still ( Berkeley version).

The most striking table concerned noise. Following Dietterich, Breiman flipped 5 percent of the training labels to a wrong class. On the breast cancer data AdaBoost's test error rose by 43.2 percent and Forest-RI's by 1.8 percent; on the voting data the rises were 48.9 and 6.3 percent. His explanation was mechanical: boosting keeps raising the weight on cases it misclassifies, mislabeled cases stay misclassified, and the ensemble warps around them, while a forest weights no case specially.

The limits of this evidence are plain. The tests were the author's own, mostly on small datasets, with two preset values of F, no significance tests, and AdaBoost as the main comparator. The paper's conjecture that AdaBoost in its later stages is emulating a random forest was offered with suggestive evidence, not proof. The strength of the paper was not that it settled which classifier is best, but that it gave a fast, robust, nearly tuning-free method with a theory and built-in diagnostics.

From Fortran to every toolkit

The method spread through software. Cutler collaborated with Breiman on the Fortran code and its documentation, and notes that graphical software for trees and forests was available commercially from Salford Systems ( Cutler's remembrance). The free R package of 2002 put forests into the R environment widely used by statisticians, and Python's scikit-learn later made them a few lines of code for anyone ( scikit-learn documentation).

A prominent consumer deployment came a decade later. Microsoft's CVPR 2011 paper on real-time human pose recognition, which won the conference's best paper award, labeled every pixel of a depth image with a body part using a randomized decision forest, the body part recognition behind Kinect. The full paper cites both Breiman and Amit and Geman, trains 3 trees to depth 20 from 1 million synthetic images in about a day on a 1000 core cluster, and runs in under 5 milliseconds per frame on the Xbox 360 GPU. Its trees choose among random candidate splits on fresh synthetic images rather than bootstrap samples, closer to Amit and Geman's scheme than to Forest-RI.

Citation counts give a rough measure of reach. Nature's 2025 analysis of the 25 most-cited papers published since 2000 includes Breiman's paper, which t3n's summary of the list places sixth, describing the method as well suited to large tables whose variables are of unknown relevance. Breiman did not see most of this. He died at his Berkeley home on July 5, 2005, aged 77 ( obituary), and Cutler writes that he viewed random forests as the culmination of his work.

A family of descendants

The framework invited variants. Pierre Geurts, Damien Ernst and Louis Wehenkel's extremely randomized trees of 2006 randomized the cut-points as well as the variables and grew trees on the whole sample, with computational efficiency as the main gain. Nicolai Meinshausen's quantile regression forests showed that a forest holds information about the whole conditional distribution of a response, not just its mean. Hemant Ishwaran and colleagues' random survival forests adapted the splitting rules to right-censored survival data. Stefan Wager and Susan Athey's causal forests estimated how a treatment's effect varies across people and proved the estimates asymptotically Gaussian, which they described as the first results allowing random forests to be used for provably valid statistical inference.

The honest limits

The importance measures that made forests attractive to scientists can mislead. Carolin Strobl and colleagues showed in BMC Bioinformatics in 2007 that they are unreliable when predictors differ in scale or number of categories, because split selection in the individual trees favors some variable types and bootstrap sampling with replacement adds further effects; they proposed unbiased conditional trees with subsampling without replacement. The scikit-learn documentation warns that its default impurity-based importances favor high-cardinality features and recommends permutation importance instead.

The no-overfitting result is narrower than its slogan. It says the error converges as trees are added; it does not say a forest of fully grown trees cannot fit noise, and out-of-bag estimates run high when too few trees are grown, as Liaw and Wiener cautioned. The theory also lagged the practice for years. Erwan Scornet, Gérard Biau and Jean-Philippe Vert opened their 2015 consistency proof by noting how little was known about the procedure's mathematics, and proved consistency for Breiman's original algorithm only in the setting of additive regression models.

Claims that forests are simply the best classifier are contested. Manuel Fernández-Delgado and colleagues tested 179 classifiers from 17 families on 121 datasets and found a random forest best, at 94.1 percent of the maximum accuracy, with a Gaussian-kernel support vector machine close behind at 92.3 percent and no significant difference between them. Michael Wainberg, Babak Alipanahi and Brendan Frey replied that the study lacked a held-out test set and excluded failed trials, and that by its own tests forests were not significantly better than support vector machines or neural networks. Gradient boosting, published by Jerome Friedman the same year, is often the stronger tabular learner: the 2025 Nature paper on TabPFN describes gradient-boosted decision trees as dominant on tabular data for twenty years. Forests are better described as the robust default than the reliable winner.

Still competitive on tables, provisionally

Deep learning transformed work on images and text after 2012, but its edge on spreadsheets was never clear. Léo Grinsztajn, Edouard Oyallon and Gaël Varoquaux benchmarked deep networks against tree-based models, including XGBoost and random forests, on 45 tabular datasets and found the trees still state of the art on medium-sized data of around 10,000 samples. They traced the gap to inductive biases: tree models shrug off uninformative features and fit irregular functions that networks smooth over.

That verdict is now being tested. The TabPFN model, a transformer trained across millions of synthetic datasets, reported outperforming all previous methods on datasets of up to 10,000 samples, in one classification setting beating in 2.8 seconds an ensemble of strong baselines tuned for 4 hours ( Nature, 2025). Whether such models displace tree ensembles in everyday practice is too recent to judge.

How to place random forests in AI history

Random forests belong to the statistical branch of machine learning that ran alongside neural networks through the 1990s and 2000s, next to support vector machines and boosting. Their conceptual novelty was moderate: randomized trees and bagging existed, and Ho, Amit and Geman, and Dietterich had each shown that randomness could improve tree ensembles. Breiman's contribution was to unify these schemes under one definition, explain them through strength and correlation, and package the result with out-of-bag error and variable importance into a method that needed almost no tuning.

Its influence came through use rather than through a single benchmark moment. Free implementations carried forests into chemoinformatics, ecology, bioinformatics and air quality prediction and into a living-room motion sensor, and the 2001 paper became one of the most cited of the century. The open questions it left, about trustworthy importance measures, theory, and when boosting or neural networks do better, are the research it started. A fair placement is as the workhorse that let practitioners get strong predictions from ordinary tables of data without becoming specialists, at the moment Breiman was urging statistics to judge models by how well they predict.

References

• Breiman (2001). Random Forests.
• Breiman (2001). Random Forests, Berkeley version dated January 2001.
• UC Berkeley Department of Statistics (1999). Random Forests, Random Features: Technical Report 567.
• Cutler (2010). Remembering Leo Breiman.
• UC Berkeley (2005). Obituary: Leo Breiman.
• Breiman (1994). Bagging Predictors, Technical Report 421.
• Dietterich (2000). An Experimental Comparison of Three Methods for Constructing Ensembles of Decision Trees: Bagging, Boosting, and Randomization.
• Ho (1995). Random Decision Forests.
• Ho (1998). The Random Subspace Method for Constructing Decision Forests.
• Amit and Geman (1997). Shape Quantization and Recognition with Randomized Trees.
• Liaw and Wiener (2002). Classification and Regression by randomForest.
• scikit-learn developers (2026). Ensembles: Gradient boosting, random forests, bagging, voting, stacking.
• Breiman (2001). Statistical Modeling: The Two Cultures.
• Shotton et al. (2011). Real-Time Human Pose Recognition in Parts from a Single Depth Image.
• Shotton et al. (2011). Real-Time Human Pose Recognition in Parts from Single Depth Images, full paper.
• Pearson, Ledford, Hutson and Van Noorden (2025). Exclusive: the most-cited papers of the twenty-first century.
• Honsel (2025). Top 10 der meistzitierten Paper: Die einflussreichsten Forschungsarbeiten seit 2000.
• Geurts, Ernst and Wehenkel (2006). Extremely randomized trees.
• Meinshausen (2006). Quantile Regression Forests.
• Ishwaran, Kogalur, Blackstone and Lauer (2008). Random survival forests.
• Wager and Athey (2018). Estimation and Inference of Heterogeneous Treatment Effects using Random Forests.
• Strobl, Boulesteix, Zeileis and Hothorn (2007). Bias in random forest variable importance measures: Illustrations, sources and a solution.
• Scornet, Biau and Vert (2015). Consistency of random forests.
• Fernández-Delgado, Cernadas, Barro and Amorim (2014). Do we Need Hundreds of Classifiers to Solve Real World Classification Problems?.
• Wainberg, Alipanahi and Frey (2016). Are Random Forests Truly the Best Classifiers?.
• Friedman (2001). Greedy function approximation: A gradient boosting machine.
• Hollmann et al. (2025). Accurate predictions on small data with a tabular foundation model.
• Grinsztajn, Oyallon and Varoquaux (2022). Why do tree-based models still outperform deep learning on tabular data?.