Random Forests

The paper and its question

The paper Random Forests was published by Leo Breiman in the journal Machine Learning in October 2001, in volume 45, pages 5-32. Breiman was in the Statistics Department at the University of California, Berkeley.^[1] The paper concerns a classifier made from many tree predictors rather than a single decision tree. Its question is how to define a forest in which randomness is part of how the trees are built, and how to analyze the error of the resulting combination.^[1] A tree predictor is a model that makes a prediction through a sequence of splits; the forest combines many such predictors.^[1]

How the forest is defined

The abstract defines a random forest as a combination of tree predictors such that each tree depends on the values of a random vector sampled independently and with the same distribution for all trees in the forest.^[1] In plain terms, every tree receives its own random draw from the same distribution; that draw controls randomized choices in the construction of that tree. The trees are therefore not identical copies. The paper also uses a random selection of features to split each node.^[1] A node is a place in a tree where the data are divided; at such a split, the features considered are selected randomly. The forest is the combination of the resulting trees.^[1]

Error, strength, and correlation

The paper states that the generalization error for forests converges almost surely to a limit as the number of trees in the forest becomes large.^[1] Generalization error is error on new data rather than on the data used to build the trees; the convergence result says that with many trees the forest's error settles toward a stable value. The generalization error of a forest of tree classifiers depends on the strength of the individual trees and on the correlation between them.^[1] Strength refers to how well an individual tree performs as a classifier; correlation refers to how similarly the trees behave, including whether they tend to make errors together. The forest's error is thus not simply the average error of its members: it also reflects their collective agreement.^[1]

Results and internal estimates

Using a random selection of features to split each node yields error rates that compare favorably to Adaboost but are more robust with respect to noise.^[1] The paper compares the resulting error rates with Adaboost and reports that they compare favorably while being more robust with respect to noise. The paper also reports that internal estimates monitor error, strength, and correlation, and that these estimates are used to measure variable importance.^[1] Internal estimates are estimates produced within the forest; the paper uses them as diagnostics and as a way to rank variables by importance. The paper states that these ideas are also applicable to regression.^[1]

Why the paper matters

The paper's contribution is to give random forests a precise definition, to analyze their generalization error through strength and correlation, and to include internal diagnostics.^[1] These pieces connect the behavior of a large ensemble to measurable properties of its trees. Random feature selection is part of the definition that the paper analyzes, not merely an implementation detail. The internal estimates add a practical side: the same forest can be monitored for error, strength, and correlation, and its variables can be ranked by importance.^[1] Because the paper states that the ideas also apply to regression, the framework is not limited to classification.^[1] For a reader learning machine learning, the paper shows how an ensemble method can be defined, analyzed, and diagnosed within one framework.