Random forest
A random forest is an ensemble learning method that constructs many decision trees and combines their predictions. For classification, the forest ordinarily predicts the class selected by the largest number of trees. For regression, it ordinarily returns the arithmetic mean of the trees’ numerical outputs. Randomization enters both through the training data presented to each tree and through the candidate variables considered at each split.
The method belongs to the broader family of randomized algorithms and extends bootstrap aggregating, commonly called bagging. Its central statistical effect is the reduction of prediction variance through aggregation. Individual trees can respond strongly to small changes in a training sample, whereas an average over partially decorrelated trees is generally less sensitive to those changes.
Mathematical formulation
Let the training data be
[ \mathcal{D}={(x_i,y_i)}_{i=1}^{n}, ]
where (x_i\in\mathbb{R}^{p}) is a vector of predictor values and (y_i) is either a class label or a numerical response. A random forest contains (B) trees,
[ T_1(x),T_2(x),\ldots,T_B(x), ]
each generated using an independent stream of algorithmic randomness.
For a regression forest, the combined predictor is
[ \hat{f}(x)=\frac{1}{B}\sum_{b=1}^{B}T_b(x). ]
For a classification forest, each tree produces a class prediction, and the forest applies a plurality rule:
[ \hat{C}(x)=\operatorname*{arg,max}{c} \sum{b=1}^{B}\mathbf{1}{T_b(x)=c}. ]
A probability estimate can instead be formed from the fraction of trees assigning the observation to each class. Some implementations average class proportions stored in terminal nodes rather than averaging discrete tree votes, so nominally similar forests can yield different probability estimates while retaining the same predicted class.
Tree construction
Each tree is usually fitted to a bootstrap sample drawn from the original observations. Sampling with replacement causes some observations to appear more than once in a tree’s training set, while approximately (36.8%) are omitted from that sample when the data set is large. The omitted observations form the tree’s out-of-bag set.
At each nonterminal node, the algorithm selects a random subset of the available predictor variables. A split is then chosen from that subset according to an impurity or loss criterion. Classification implementations commonly measure node impurity using the Gini coefficient or an entropy-based quantity, whereas regression implementations commonly minimize within-node squared error.
The random restriction on candidate predictors distinguishes a random forest from ordinary bagging of trees. If a highly influential predictor were examined at every node, many trees would choose similar early splits and would consequently remain strongly correlated. Random feature selection reduces that correlation, although it can also weaken individual trees by excluding informative predictors from particular split decisions. Forest behavior therefore depends on the interaction between tree strength and inter-tree dependence.
Trees are generally grown to substantial depth without pruning. Their terminal nodes may contain only a small number of observations, subject to implementation-specific minimum-size constraints. Although such trees individually have low bias and high variance, aggregation suppresses much of the variance that would otherwise make them unstable predictors.
Statistical interpretation
For regression, the variance of an average of (B) identically distributed tree predictors can be expressed schematically as
[ \operatorname{Var}\left(\frac{1}{B}\sum_{b=1}^{B}T_b(x)\right)
\sigma^2\left(\rho+\frac{1-\rho}{B}\right), ]
when every tree has variance (\sigma^2) and each pair has correlation (\rho). Increasing the number of trees reduces the component proportional to (1/B), but it does not remove the component associated with common correlation. The randomization of split variables is consequently as important to the ensemble construction as the number of trees.
A random forest can also be interpreted as an adaptive neighborhood method. Two observations are treated as similar when they repeatedly occupy the same terminal nodes across the ensemble. The resulting proximity relation depends on the partition structure learned from the response, unlike a distance measure fixed in advance. This interpretation connects forests with nearest-neighbor methods, kernel-like estimators, and data-dependent partitioning models.
The consistency of particular forest variants has been established under specified assumptions concerning tree construction, subsampling, and the regularity of the underlying response function. These results do not apply uniformly to every implementation called a random forest because practical systems differ in split selection, bootstrap use, stopping rules, and treatment of categorical variables.
Out-of-bag estimation
An observation omitted from a tree’s bootstrap sample can be predicted by that tree without participating in its fitting. Aggregating predictions only from trees for which an observation was omitted produces an out-of-bag prediction for that observation. The collection of such predictions yields an internal estimate of generalization error.
Out-of-bag estimation is related to cross-validation, but its partitions arise from the bootstrap samples already used to construct the ensemble. It therefore does not require fitting a separate collection of cross-validation models. The resulting estimate can differ from conventional cross-validation when the sample is small, observations are dependent, or the sampling design is not represented by ordinary bootstrap resampling.
For classification, out-of-bag predictions support an estimated confusion matrix and class-specific error measurements. For regression, they support residual-based estimates such as mean squared prediction error. These quantities describe performance under the resampling structure of the fitted forest rather than under every possible form of distributional change.
Variable importance and interpretation
Random forests support several measures of feature importance, but these measures represent different statistical quantities. Impurity-based importance sums the reductions in node impurity attributed to a predictor across the forest. Its value is influenced by how often the predictor can be selected and by the number of candidate split points available to it.
Permutation importance measures the change in predictive performance after the values of a predictor are permuted. The permutation disrupts the predictor’s association with the response while leaving the fitted forest unchanged. When predictors are strongly correlated, one predictor can substitute for another, causing the measured importance of either variable to depend on whether the other remains intact.
Conditional permutation schemes preserve selected dependence relationships during permutation. They address a different question from unrestricted permutation importance and require additional modeling of the predictor distribution. Neither form of importance is equivalent to a causal effect, because predictive contribution does not by itself establish the consequences of an intervention.
Partial dependence plots summarize the average fitted response as one or more predictors vary over their observed range. Their averages can include combinations of predictor values that are rare or absent when predictors are dependent. Individual conditional expectation curves retain observation-level variation and can reveal heterogeneity that the average partial dependence function conceals.
Historical development
The intellectual ancestry of random forests includes randomized tree construction, bagging, and random-subspace methods. Tin Kam Ho introduced random decision forests during the 1990s by constructing tree ensembles in randomly selected feature subspaces. Yoav Freund and Robert Schapire developed AdaBoost during the same decade, establishing a separate but closely related approach in which sequentially fitted learners receive changing observation weights.
Leo Breiman formulated the modern random-forest framework by combining bootstrap aggregation with random predictor selection at each node. His 2001 account also developed the margin function, an ensemble error analysis, and out-of-bag estimation within a unified description. During this period, Adele Cutler and You Watanabe participated in the implementation and empirical evaluation of the classification and regression software associated with Breiman’s formulation. The name “Random Forests” was subsequently used for both the general statistical method and software derived from that implementation.
Later software broadened access to the method and introduced implementation-level variations. Andy Liaw and Matthew Wiener developed the randomForest package for the R programming language, adapting Breiman and Cutler’s code to R’s statistical interface. Other libraries incorporated alternative tree representations, parallel execution models, and probability-estimation conventions while retaining the defining combination of randomized trees and prediction aggregation.
Computational characteristics
Forest construction can be distributed across processors because trees are conditionally independent once their random samples and random-number streams have been assigned. Prediction cost grows with both the number of trees and the average path length traversed within each tree. Memory consumption depends on the stored node structures, which can become substantial when many deep trees are fitted.
Increasing the number of trees ordinarily causes the ensemble prediction to approach a stable Monte Carlo average rather than producing the overfitting pattern associated with increasing the depth of a single tree. This stabilization does not eliminate errors caused by inappropriate sampling, uninformative predictors, mislabeled outcomes, or a mismatch between the training distribution and the prediction population.
Standard decision-tree partitions are piecewise constant, so a regression forest generally does not extrapolate linearly beyond the response patterns represented in its training data. Its predictions are combinations of terminal-node averages and therefore remain constrained by the fitted leaves. Specialized forest variants alter leaf models or splitting objectives when the target problem requires a different structure.
Extensions
Extremely randomized trees introduce additional randomness by selecting split thresholds at random rather than optimizing every threshold over the node sample. Quantile regression forests retain the distribution of training responses associated with forest leaves, allowing conditional quantiles to be estimated instead of only conditional means.
Survival forests adapt the ensemble to censored time-to-event data through survival-specific splitting criteria and terminal-node estimators. Causal forests use related tree ensembles to estimate heterogeneous treatment effects, with construction rules designed to separate nuisance estimation from treatment-effect estimation. These methods share forest-like partitioning and aggregation but target statistical functionals that differ from ordinary classification or regression.