How Random Forest Works

A complete mechanical walkthrough of Random Forest's training and prediction process — bootstrap sampling, random feature subsets, and the "out-of-bag" samples this randomness leaves behind almost for free.

The Algorithm, As Explicit Steps

Bootstrap Sampling, Visually

Python Implementation of Bootstrap Sampling

import numpy as np

data = np.array([1,2,3,4,5,6,7,8])
rng = np.random.default_rng(42)

bootstrap_sample = rng.choice(data, size=len(data), replace=True)
print(bootstrap_sample)   # e.g. [7 4 8 5 7 3 7 8] -- some rows repeated, some missing

Out-of-Bag (OOB) Samples — A Free Validation Set

Because each bootstrap sample is drawn with replacement and is the same size as the original data, some rows are never selected for a given tree — these are that tree's out-of-bag samples. The probability any specific row is left out of one bootstrap sample of size \(n\) works out to:

In other words, roughly 36.8% of the original data is left out of any single tree's training sample — and since every tree leaves out a different random subset, every row ends up "out-of-bag" for some trees. This lets Random Forest estimate its own validation accuracy without a separate held-out test set:

from sklearn.ensemble import RandomForestClassifier

model = RandomForestClassifier(n_estimators=200, oob_score=True, random_state=42)
model.fit(X_train, y_train)
print(model.oob_score_)   # an accuracy estimate computed from each tree's left-out samples

Random Feature Subsets at Each Split

# For classification, scikit-learn defaults max_features="sqrt" --
# each split considers only sqrt(total_features) features, chosen randomly
from sklearn.ensemble import RandomForestClassifier

model = RandomForestClassifier(n_estimators=100, max_features="sqrt", random_state=42)
# For a dataset with 100 features, each split considers only ~10 random features,
# not all 100 -- this is what decorrelates trees beyond what bagging alone achieves

Without this second layer of randomness, every tree would tend to split on the same few strongest features first, making the trees highly correlated with each other — and correlated errors don't cancel out nearly as well when averaged.

Practical Use Cases

• Using oob_score_ as a free, built-in estimate of generalization performance during model development
• Understanding why max_features is a meaningful tuning knob, not just an arbitrary default

Common Mistakes

• Believing "bagging alone" (random rows, but every feature considered at every split) gives the same decorrelation benefit as full Random Forest's random feature subsets — it doesn't; the two randomizations are complementary, not redundant.
• Treating oob_score_ as a full replacement for a proper held-out test set in every situation — it's a useful, nearly-free estimate, but a genuine test set is still the standard for final reported performance.

Interview Relevance

Q: "What is an out-of-bag sample, and why is it useful?" The roughly 36.8% of training rows not selected in a given tree's bootstrap sample — since every row is out-of-bag for some subset of trees, Random Forest can average each row's predictions from only the trees that never saw it during training, providing a built-in, nearly free validation estimate.

Practice Question

With 8 original rows and bootstrap sampling, roughly how many unique original rows would you expect in a single bootstrap sample of size 8? (Hint: use the 36.8% out-of-bag figure.)

Related ML Notes

• Bagging
• Random Forest Classification
• Random Forest in Python