Random Forest is an ensemble learning method that builds many decision trees and aggregates their predictions to produce a more accurate and stable result. It combines Bagging (Bootstrap Aggregating) with random feature selection at each split. The method was formally proposed by Leo Breiman in 2001.
The key insight is that by introducing randomness in both the data (bootstrap) and the features (random subspace), the individual trees become decorrelated, and their aggregation yields a powerful reduction in variance without increasing bias.
The Random Forest algorithm proceeds as follows:
Draw \(B\) bootstrap samples (sampling with replacement, same size as original) from the training data \(\{(x_i, y_i)\}_{i=1}^n\).
For each bootstrap sample, grow an unpruned decision tree. At each node split, instead of considering all \(p\) features, randomly select \(m\) features and find the best split among those only.
Typical choices for \(m\):
Combine the predictions of all \(B\) trees:
\[\hat{f}(x) = \frac{1}{B}\sum_{b=1}^{B} T_b(x)\]
where \(T_b(x)\) is the prediction of the \(b\)-th tree.
The purpose of the random feature restriction is to decorrelate the individual trees. Consider a dataset where one feature is a very strong predictor. In standard Bagging, every tree would use that strong predictor at or near the root, making all trees structurally similar — i.e., highly correlated.
When trees are correlated, averaging them provides limited variance reduction. By forcing each split to choose from a random subset of features, we ensure that different trees explore different parts of the feature space, breaking the dominance of any single strong predictor.
The smaller \(m\) is, the more decorrelated the trees become (but each individual tree becomes weaker). The default values (\(\sqrt{p}\) or \(p/3\)) strike an effective balance.
The variance of the average of \(B\) identically distributed (but not independent) random variables, each with variance \(\sigma^2\) and pairwise correlation \(\rho\), is:
\[\text{Var}\left(\frac{1}{B}\sum_{b=1}^B T_b(x)\right) = \rho\,\sigma^2 + \frac{1-\rho}{B}\,\sigma^2\]
As \(B \to \infty\), the second term vanishes, leaving \(\rho\,\sigma^2\) as the irreducible lower bound. Random Forests reduce \(\rho\) (the pairwise correlation between trees) through the random feature selection mechanism, thereby achieving lower ensemble variance than standard Bagging.
This explains why:
Each bootstrap sample includes approximately 63.2% of the original observations (since \(P(\text{observation included}) = 1 - (1-1/n)^n \approx 1 - e^{-1} \approx 0.632\)).
The remaining ~36.8% not selected in a given bootstrap sample are called Out-of-Bag (OOB) samples for that tree. For each observation \(x_i\), we can form its OOB prediction by averaging only the trees for which \(x_i\) was OOB:
\[\hat{f}^{\text{OOB}}(x_i) = \frac{1}{|S_i|}\sum_{b \in S_i} T_b(x_i)\]
where \(S_i = \{b : x_i \notin \text{bootstrap sample } b\}\).
The OOB error is computed from these predictions and provides a nearly unbiased estimate of the test error — no separate cross-validation is needed. This is a significant practical advantage of Random Forests.
More trees are always better — Random Forests do not overfit as \(B\) increases (the variance formula shows the second term shrinks monotonically). Typical values: 500–1000+. The only cost is computational.
Controls the correlation-variance trade-off. Smaller \(m\) means more decorrelated but individually weaker trees. Defaults: \(\sqrt{p}\) (classification), \(p/3\) (regression). Can be tuned via OOB error.
For each feature, sum the impurity reductions (e.g., Gini or RSS decrease) at every node where that feature is used for splitting, weighted by the proportion of samples reaching that node, and averaged across all trees:
\[\text{Importance}(x_j) = \frac{1}{B}\sum_{b=1}^B \sum_{t \in T_b} \mathbb{1}(v(t)=j)\;\frac{n_t}{n}\;\Delta i(t)\]
where \(v(t)\) is the splitting variable at node \(t\), \(n_t\) is the number of samples at that node, and \(\Delta i(t)\) is the impurity decrease.
For each feature \(x_j\), randomly permute (shuffle) its values in the OOB samples and measure the increase in OOB error. A large increase indicates the feature is important:
\[\text{Importance}(x_j) = \frac{1}{B}\sum_{b=1}^B \frac{\text{Error}^{\text{OOB},\pi_j}_b - \text{Error}^{\text{OOB}}_b}{|\text{OOB}_b|}\]
Permutation importance is generally more reliable than MDI, especially when features are correlated or have different scales.