Random Forest

A Random Forest is a non-parametric supervised ensemble learning method in computation and algorithms used for classification, regression, and survival analysis. Formalized by American statistician Leo Breiman in 2001, the algorithm synthesizes two variance-reduction concepts: Breiman's 1996 bootstrap aggregating (bagging) procedure and the random subspace method introduced by Tin Kam Ho in 1995 (alongside randomized split selection studied by Yali Amit and Donald Geman in 1997). Individual deep decision trees exhibit low bias but high variance because small perturbations in the training sample can alter the top split and cascade through the partition hierarchy. By training B unpruned Classification and Regression Trees (CART) on independent bootstrapping replicates and restricting each internal node split to a randomly sampled subset of m_try candidate features, a Random Forest decorrelates the constituent trees so that ensemble averaging suppresses variance without inflating bias.

Binary Recursive Partitioning

Each base learner T_b (b = 1, ..., B) is a binary tree constructed top-down via greedy recursive partitioning of R^p. At an internal node m representing region R_m with N_m observations, a candidate split consists of a predictor variable X_j and a threshold s ∈ R that partition R_m into R_L(j, s) = {x ∈ R_m : x_j ≤ s} and R_R(j, s) = {x ∈ R_m : x_j > s}, selecting (j^*, s^*) to maximize the weighted impurity drop:

ΔI(m, j, s) = I(R_m) − (N_L / N_m) I(R_L) − (N_R / N_m) I(R_R)

Gini Impurity, Shannon Entropy, and Residual Variance

The impurity functional I(R_m) is matched to the prediction task:

1. Classification — Gini Impurity: Let p̂_mk denote the proportion of class k ∈ {1, ..., K} in node m. The Gini index measures expected misclassification probability under random node labeling:

I_Gini(R_m) = ∑_k=1^K p̂_mk (1 − p̂_mk) = 1 − ∑_k=1^K p̂_mk²

1. Classification — Information Gain (Shannon Entropy): Node heterogeneity can also be quantified by information entropy:

I_Entropy(R_m) = − ∑_k=1^K p̂_mk log₂(p̂_mk)

1. Regression — Within-Node Variance (MSE): For continuous responses y_i ∈ R, the node prediction is the sample mean ȳ_m and impurity is I_MSE(R_m) = (1/N_m) ∑_xi∈Rm (y_i − ȳ_m)². Trees are grown deep (n_min = 1 for classification, n_min = 5 for regression) without post-pruning.

Bootstrap Aggregating and Random Subspaces

Training B trees on D = {(x_i, y_i)}_i=1ⁿ combines two randomization stages:

1. Row-Wise Bootstrap Resampling: Draw D_b^* of size n uniformly with replacement from D.
2. Column-Wise Random Feature Subspace: At each node split, draw M_node ⊂ {1, ..., p} of size m_try ≤ p without replacement (m_try = ⌊√p⌋ for classification; m_try = ⌊p/3⌋ for regression) and optimize (j^*, s^*) only over j ∈ M_node.

The ensemble aggregates predictions at a test point x by majority vote or arithmetic averaging: f̂_RF(x) = (1/B) ∑_b=1^B T_b(x).

Mathematical Decomposition of Ensemble Variance

For B identically distributed trees each having variance σ² and pairwise correlation ρ > 0, the variance of the ensemble average is:

Var(f̂_RF(x)) = ρ σ² + [ (1 − ρ) / B ] σ²

As B → ∞, the second term vanishes, leaving ρσ². In standard bagging (m_try = p), dominant predictors are selected at the root of almost every tree, producing strongly correlated trees (large ρ). Restricting each node to m_try ≈ √p random features excludes dominant predictors from (1 − m_try/p) of splits, lowering inter-tree correlation ρ and reducing ensemble variance.

Out-of-Bag Error and 1 − e⁻¹ Coverage

Because each bootstrap sample D_b^* draws n times with replacement, the probability that observation i is omitted from D_b^* is:

P(i ∉ D_b^*) = (1 − 1/n)ⁿ → e⁻¹ ≈ 0.3679 as n → ∞

Each tree trains on ~63.2% of the data, leaving ~36.8% as an Out-of-Bag (OOB) validation set. Predicting each observation x_i using only the ~B/3 trees for which i was out-of-bag yields an unbiased internal validation error during training. By the Strong Law of Large Numbers, as B → ∞ the generalization error converges almost surely to a limiting bound without overfitting.

Gini Importance vs. Permutation Feature Importance

Random Forests rank predictor relevance via two primary metrics:

1. Mean Decrease Impurity (MDI / Gini Importance): Sums weighted impurity reductions (N_m/n)ΔI(m, j, s) across all nodes splitting on X_j, averaged over B trees. MDI is fast but favors continuous or high-cardinality variables with more cut-points.
2. Permutation Importance (Mean Decrease Accuracy, MDA): Permutes the values of X_j within the OOB sample of each tree b and measures the resulting drop in OOB accuracy (or rise in MSE). Permutation importance provides an unbiased ranking for genome-wide association studies and ecological modeling.

Can a Random Forest overfit if the number of trees B is made too large?

No. Because the trees are conditionally independent and identically distributed given the training set, increasing B computes a more precise Monte Carlo approximation to E_Θ[T(x; Θ)], driving the finite-sample term (1 − ρ)σ²/B toward zero without increasing model capacity.

Why do Random Forests struggle to extrapolate linear trends outside the training domain?

Every leaf predicts the local average ȳ_m of training responses within that box, so a Random Forest prediction is always bounded within [y_min, y_max] and predicts a flat plateau outside the training domain rather than extrapolating a slope as in Linear Regression.

Why is permutation importance preferred over Gini importance in bioinformatics?

When binary genetic variants (SNPs) are analyzed alongside continuous clinical covariates, Gini importance inflates continuous features because they offer more candidate split thresholds s; OOB permutation importance removes this selection bias.

1. Ho, T. K. (1995). Random decision forests. Proceedings of the 3rd International Conference on Document Analysis and Recognition, 1, 278–282. https://doi.org/10.1109/ICDAR.1995.598994
2. Breiman, L. (1996). Bagging predictors. Machine Learning, 24(2), 123–140. https://doi.org/10.1007/BF00058655
3. Amit, Y., & Geman, D. (1997). Shape quantization and recognition with randomized trees. Neural Computation, 9(7), 1545–1588. https://doi.org/10.1162/neco.1997.9.7.1545
4. Breiman, L. (2001). Random forests. Machine Learning, 45(1), 5–32. https://doi.org/10.1023/A:1010933404324
5. Strobl, C., Boulesteix, A.-L., Zeileis, A., & Hothorn, T. (2007). Bias in random forest variable importance measures: Illustrations, sources and a solution. BMC Bioinformatics, 8, 25. https://doi.org/10.1186/1471-2105-8-25