Definition
A random forest is an ensemble of many decision trees whose predictions are combined — a majority vote for classification, an average for regression. The whole idea rests on two independent injections of randomness: every tree is grown on a bootstrap resample of the rows, and at each split the tree may only choose among a random subset of the features. Those two knobs make the trees disagree with one another, and averaging predictors that disagree is what cancels error.
The problem it solves is variance. A single decision tree grown deep enough will memorize its training set almost perfectly, so a small change in the data produces a very different tree and very different predictions — high variance, the classic face of overfitting. You cannot fix that by averaging copies of the same overfit tree, because identical mistakes average to the same mistake. The forest's contribution is to make the trees different on purpose, so that their individual errors point in different directions and mostly cancel when you pool them, while the signal they all agree on survives. The method was introduced by Leo Breiman in "Random Forests" (Machine Learning, 45(1):5–32, 2001).
How It Works
Building a forest means repeating one recipe a few hundred times and pooling the results.
Bootstrap the rows. For each tree, draw a training set the same size as the original by sampling rows with replacement. Some rows appear several times, others not at all. The arithmetic of that is worth doing once: the chance a given row is missed in a single draw is 1 − 1/n, so the chance it is missed across all n draws is (1 − 1/n)ⁿ, which converges to 1/e ≈ 0.368 as n grows. So each bootstrap sample leaves out about 37% of the rows — a third of the data, every time. Breiman states it plainly: "In each bootstrap training set, about one-third of the instances are left out."
Subsample the features at every split. This is the ingredient that separates a random forest from plain bagged trees. When a normal decision tree looks for the best split at a node, it considers all p features. A random forest picks a fresh random subset of them at each node and is only allowed to split on those. The standard default is √p features for classification and p/3 for regression — with p = 30, that is about 5 candidates per split. Restricting the choice this way stops one or two dominant features from being chosen at the top of every tree, which is precisely what would make the trees correlated. Decorrelated trees are the point: averaging T predictors each with variance σ² and pairwise correlation ρ leaves variance ρσ² + (1−ρ)σ²/T, so the term you can drive down by adding trees is gated by how uncorrelated they are. More trees never hurt accuracy; they only cost compute.
Grow each tree deep and leave it unpruned. Individual trees are meant to have low bias and high variance — the averaging is there to remove the variance, so pruning each tree would throw away signal for a job the ensemble already handles.
Aggregate. To predict, run the input through all the trees. For classification the forest returns the majority vote (or averages the trees' class probabilities); for regression it averages the numeric outputs.
Out-of-bag error: validation for free
The one-third of rows omitted from each bootstrap sample are its out-of-bag (OOB) rows, and they are a free test set. For any training row, gather the trees that did not see it — roughly a third of the forest — and let just those trees predict it. Do this for every row and you get an honest generalization estimate without ever holding data out or running cross-validation, because each prediction only ever uses trees that never trained on that row. In scikit-learn this is a single flag, oob_score=True, and on well-sized data the OOB estimate tracks the held-out test score closely.
Real-World Applications
The most visible deployment is Microsoft's original Kinect. Shotton et al., "Real-Time Human Pose Recognition in Parts from Single Depth Images" (CVPR 2011), turned skeleton tracking into a per-pixel classification problem — which body part does this depth pixel belong to? — solved by a randomized decision forest running on the Xbox at 30 frames per second. The forest was chosen precisely because evaluating a bag of shallow trees is cheap and parallel, which is what real-time on 2010 console hardware demanded.
On ordinary tabular data — the spreadsheet-shaped rows most organizations actually have — the random forest remains a serious default rather than a historical one. Grinsztajn et al., "Why do tree-based models still outperform deep learning on typical tabular data?" (NeurIPS 2022), benchmarked tree ensembles against modern neural networks across many datasets and found the tree-based models still state-of-the-art on medium-sized problems, even before accounting for their far lower tuning and compute cost. This is why a random forest is the standard first model on a new tabular problem: it needs no feature scaling, tolerates irrelevant features, gives an OOB error estimate for free, and ranks feature importance out of the box, so it sets a strong baseline before anyone reaches for something heavier.
That feature-importance output is itself a working application. In genomics and other high-dimensional settings, a forest is routinely used less as a predictor than as a variable-ranking tool: fit it on thousands of candidate inputs and read off which ones the trees actually split on, as a fast, model-based way to shortlist features for downstream analysis.
Key Concepts
- Bagging (bootstrap aggregating) — the parallel "train on resamples and average" scheme a random forest is built on. A forest is bagging plus per-split feature subsampling; the feature trick is the difference that matters.
- Decorrelation, not just averaging — the reason the feature subset exists. Averaging correlated trees barely helps; the
ρσ² + (1−ρ)σ²/Tvariance formula shows the payoff is capped by tree correlation, so the method spends its randomness on making trees disagree. - Extremely Randomized Trees (Extra-Trees) — a genuine variant that pushes the randomness further: instead of searching for the best threshold on each candidate feature, it picks the split thresholds at random too. Faster to train and sometimes lower-variance still.
- Feature importance — how often, and how usefully, a feature was split on across the forest (mean impurity decrease). Cheap and informative, but it inflates the apparent importance of high-cardinality features; permutation importance is the more honest measure when the ranking matters.
Challenges
The model is large and the predictions are slow. A forest is literally hundreds of full trees; it stores and evaluates all of them. Where a single tree gives an instant, human-readable if-then path, a 300-tree forest is a black box that must poll 300 trees per prediction — a real cost for low-latency serving or memory-constrained edge devices, and the reason the Kinect work cared so much about keeping the trees shallow.
Bias does not average away. Averaging attacks variance, not bias. If every tree systematically under- or over-shoots the same way — smooth extrapolation beyond the training range, for instance, where trees can only predict values they saw — the forest inherits that bias unchanged. A random forest cannot predict a trend outside the range of its training targets, no matter how many trees you add.
It is a variance-reduction tool, so it wins least where variance is not the problem. On a task where a single well-regularized model is already low-variance, or where the ceiling is set by bias, the forest's core mechanism has little to do and boosting's bias reduction (see gradient boosting) tends to pull ahead. Reaching for a forest assumes overfitting single trees is your actual failure mode.
Impurity-based importances mislead. As noted above, the default feature-importance numbers favor high-cardinality and continuous features and can rank a noise column above a useful binary one. Treat them as a hint, not a measurement, and use permutation importance when the ranking drives a decision.
Code Example
This fits a forest on scikit-learn's breast-cancer dataset (30 features, so √30 ≈ 5 candidate features per split) and prints both the out-of-bag estimate and the held-out test accuracy, so you can see the free OOB score track the real one.
import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import train_test_split
X, y = load_breast_cancer(return_X_y=True)
n_features = X.shape[1]
X_train, X_test, y_train, y_test = train_test_split(
X, y, test_size=0.2, random_state=42
)
rf = RandomForestClassifier(
n_estimators=300, # number of trees to average over
max_features="sqrt", # each split sees only sqrt(p) features
oob_score=True, # score on the ~1/3 of rows each tree never saw
bootstrap=True,
random_state=42,
n_jobs=-1,
)
rf.fit(X_train, y_train)
print(f"features p = {n_features}")
print(f"features per split (sqrt) = {int(np.sqrt(n_features))}")
print(f"OOB accuracy = {rf.oob_score_:.3f}")
print(f"test accuracy = {rf.score(X_test, y_test):.3f}")
Output:
features p = 30
features per split (sqrt) = 5
OOB accuracy = 0.965
test accuracy = 0.965
The OOB and test accuracies land on the same value here because the out-of-bag rows are a legitimate held-out sample — every OOB prediction comes only from trees that never trained on that row. That is the practical payoff of the one-third-left-out arithmetic: a validation number without spending any data on validation.
Two further ensemble methods sit next to this one and are worth keeping distinct: plain bagging (a forest without the per-split feature subsampling) and gradient boosting, which trains trees in sequence to cut bias rather than in parallel to cut variance.