Random Forest

Overview#

Random Forest takes the single decision tree from the previous notebook and fixes its biggest weakness — high variance and instability — by combining many trees together. This notebook goes deep into exactly how and why this works: the bootstrap sampling process, random feature subsetting, the mathematics of why averaging reduces variance, out-of-bag evaluation, feature importance computation, and a thorough look at tuning and limitations.

1. The Two Sources of Randomness#

Random Forest is a specific application of bagging (Bootstrap Aggregating) to decision trees, with one crucial addition. Understanding both sources of randomness is key to understanding why it works.

Python
CopyAsk AI
from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split

X, y = load_wine(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

forest = RandomForestClassifier(n_estimators=100, max_features="sqrt", random_state=42)
forest.fit(X_train, y_train)

print(f"Test accuracy: {forest.score(X_test, y_test):.3f}")

text
Ask AICopy
Source of randomness 1 — BOOTSTRAP SAMPLING (the "bagging" part):
  Each tree is trained on a random sample of the training data, drawn
  WITH REPLACEMENT, the same size as the original training set. Some
  original samples appear multiple times in a given tree's training set;
  others don't appear at all.

Source of randomness 2 — RANDOM FEATURE SUBSETTING (the extra twist
  that makes it a "Random" Forest, not just "Bagged Trees"):
  At EACH SPLIT within each tree, only a random subset of features is
  considered as candidates — not all of them. Typically sqrt(n_features)
  for classification, n_features/3 for regression.

2. Bootstrap Sampling, Demonstrated#

Python
CopyAsk AI
import numpy as np

np.random.seed(42)
original_data = np.arange(10)   # imagine 10 training samples, indices 0-9

bootstrap_sample = np.random.choice(original_data, size=10, replace=True)
print(f"Original:  {original_data}")
print(f"Bootstrap: {bootstrap_sample}")
print(f"Unique samples included: {len(set(bootstrap_sample))}")   # typically ~6-7, not 10

text
Ask AICopy
Original:  [0 1 2 3 4 5 6 7 8 9]
Bootstrap: [6 3 7 4 6 9 2 6 7 4]
Unique samples included: 6

Mathematically, as the sample size grows large, each bootstrap sample is expected to contain approximately 63.2% of the unique original samples (some appearing multiple times), leaving roughly 36.8% entirely unused for that particular tree — this leftover portion is called "out-of-bag" data, covered in section 5.

3. Why Random Feature Subsetting Matters (Not Just Bootstrap)#

Python
CopyAsk AI
# Without feature subsetting (bootstrap only — this is closer to
# plain "Bagging" rather than a true Random Forest)
forest_no_subset = RandomForestClassifier(n_estimators=100, max_features=None, random_state=42)

# With feature subsetting (the standard Random Forest approach)
forest_with_subset = RandomForestClassifier(n_estimators=100, max_features="sqrt", random_state=42)

text
Ask AICopy
Without feature subsetting: if one or two features are MUCH more
predictive than the rest, nearly every tree in the "forest" would
independently discover and use those same dominant features at the root
— making the trees highly CORRELATED with each other.

With feature subsetting: forcing each split to choose from only a random
subset of features means different trees are FORCED to sometimes rely on
different, less obviously-dominant features — deliberately DE-correlating
the trees from one another.

This decorrelation is the whole point, mathematically — it's what makes averaging actually effective (see the next section).

4. The Math: Why Averaging Reduces Variance#

Mathematical Formulation
Explain FormulaCopy
For a set of n identically distributed random variables (predictions
from n trees), each with variance σ², if the predictions were perfectly
INDEPENDENT, the variance of their average would be:

  Var(average) = σ² / n

This would mean variance shrinks toward zero as you add more trees.
HOWEVER, tree predictions are never fully independent — they're all
trained on samples of the same underlying data. If predictions have
pairwise correlation ρ, the actual formula becomes:

  Var(average) = ρ*σ² + (1-ρ)*σ²/n

As n → ∞, this converges to ρ*σ² — NOT zero. This means the residual
correlation ρ between trees puts a FLOOR on how much variance reduction
is achievable, no matter how many trees you add.

This is precisely why random feature subsetting matters so much: it directly reduces ρ (the correlation between trees), which lowers that variance floor — more trees alone (without decorrelation) hits diminishing returns much faster.

Python
CopyAsk AI
# Demonstrating diminishing returns from adding more trees
from sklearn.model_selection import cross_val_score

for n_trees in [1, 5, 10, 50, 100, 300]:
    forest = RandomForestClassifier(n_estimators=n_trees, random_state=42)
    scores = cross_val_score(forest, X_train, y_train, cv=5)
    print(f"n_estimators={n_trees}: CV accuracy = {scores.mean():.3f} (+/- {scores.std():.3f})")

text
Ask AICopy
n_estimators=1:   CV accuracy = 0.887 (+/- 0.042)
n_estimators=5:   CV accuracy = 0.937 (+/- 0.028)
n_estimators=10:  CV accuracy = 0.951 (+/- 0.019)
n_estimators=50:  CV accuracy = 0.972 (+/- 0.012)
n_estimators=100: CV accuracy = 0.972 (+/- 0.011)
n_estimators=300: CV accuracy = 0.972 (+/- 0.010)

Accuracy improves sharply at first, then plateaus — exactly matching the theoretical variance formula above: most of the benefit comes early, and beyond a certain point, adding more trees mostly reduces variance in the variance estimate itself (a smaller standard deviation across CV folds), not the accuracy itself.

5. Out-of-Bag (OOB) Evaluation: A Free Validation Set#

Since each tree only trains on ~63.2% of samples, the remaining ~36.8% ("out-of-bag" for that tree) can be used to evaluate that specific tree — and every sample ends up OOB for roughly a third of all trees, giving a full, essentially free validation estimate without needing a separate held-out set at all.

Python
CopyAsk AI
forest_oob = RandomForestClassifier(n_estimators=100, oob_score=True, random_state=42)
forest_oob.fit(X_train, y_train)

print(f"OOB score: {forest_oob.oob_score_:.3f}")
print(f"Actual test score: {forest_oob.score(X_test, y_test):.3f}")
# These two numbers are typically quite close — OOB score is a
# surprisingly reliable estimate of true generalization performance

text
Ask AICopy
For each training sample, OOB prediction works by:
1. Finding all trees for which this sample was NOT in the bootstrap
   sample (was "out-of-bag" for that tree)
2. Getting predictions from only those trees
3. Aggregating (majority vote / average) across just those trees'
   predictions for this one sample
4. Comparing against the true label, across all samples, to get an
   overall OOB accuracy

6. Feature Importance: How It's Actually Computed#

Python
CopyAsk AI
importances = forest.feature_importances_
feature_names = load_wine().feature_names

import pandas as pd
importance_df = pd.DataFrame({"feature": feature_names, "importance": importances})
importance_df = importance_df.sort_values("importance", ascending=False)
print(importance_df.head(5))

text
Ask AICopy
Mean Decrease in Impurity (MDI) — the DEFAULT method (feature_importances_):
For each feature, sum up how much it reduced impurity (Gini/entropy)
across every split, in every tree, where it was used — weighted by how
many samples reached that split. Normalize so all importances sum to 1.

The known bias of default feature importance, and a better alternative#

Python
CopyAsk AI
# MDI importance is biased toward high-cardinality (many distinct values)
# and continuous features — they simply have more OPPORTUNITIES to be
# selected for a good-looking split, purely by chance, even if not
# genuinely more predictive

from sklearn.inspection import permutation_importance

perm_result = permutation_importance(forest, X_test, y_test, n_repeats=10, random_state=42)
perm_importance_df = pd.DataFrame({
    "feature": feature_names,
    "importance": perm_result.importances_mean,
}).sort_values("importance", ascending=False)
print(perm_importance_df.head(5))

text
Ask AICopy
Permutation importance, conceptually:
1. Measure the model's baseline accuracy on a held-out set
2. For each feature, randomly SHUFFLE just that feature's values
   (breaking its relationship with the target) and re-measure accuracy
3. The drop in accuracy caused by shuffling IS that feature's importance
4. Repeat multiple times (n_repeats) and average, since shuffling
   introduces its own randomness

Permutation importance is generally considered more trustworthy than the default MDI-based feature_importances_, precisely because it directly measures the actual impact on held-out predictive performance, rather than an indirect proxy computed only from training-time impurity reduction.

7. Key Hyperparameters#

Python
CopyAsk AI
RandomForestClassifier(
    n_estimators=200,            # more trees = lower variance, diminishing returns, more compute
    max_depth=None,                 # individual trees can grow fully — bagging handles the resulting variance
    max_features="sqrt",              # feature subsetting strength — lower = more decorrelation, but weaker individual trees
    min_samples_leaf=1,                 # can increase to add a bit more regularization to each tree
    bootstrap=True,                       # False would disable bagging entirely, using the full dataset for every tree
    n_jobs=-1,                              # trees train independently — trivially parallelizable across CPU cores
    random_state=42,
)

Mathematical Formulation
Explain FormulaCopy
An important, sometimes counter-intuitive point: unlike a single
decision tree, individual trees within a Random Forest are typically
LEFT DEEP/UNPRUNED (max_depth=None) on purpose — each tree overfits its
own bootstrap sample somewhat, but since each overfits DIFFERENTLY (due
to bootstrap sampling + feature subsetting), averaging cancels out much
of that overfitting. This is a genuinely different tuning philosophy from
a standalone decision tree, where deep, unpruned growth is dangerous on
its own.

Tuning max_features: the key decorrelation knob#

Python
CopyAsk AI
for max_feat in ["sqrt", "log2", 0.5, None]:
    forest = RandomForestClassifier(n_estimators=100, max_features=max_feat, random_state=42)
    scores = cross_val_score(forest, X_train, y_train, cv=5)
    print(f"max_features={max_feat}: CV accuracy = {scores.mean():.3f}")

max_features is often the single most impactful hyperparameter to tune, precisely because of the correlation/decorrelation math covered in section 4 — it directly controls how independent the trees are from each other.

8. Random Forest for Regression#

Python
CopyAsk AI
from sklearn.ensemble import RandomForestRegressor

forest_reg = RandomForestRegressor(n_estimators=100, max_features=1/3, random_state=42)
# max_features defaults differently for regression (1.0, i.e. all
# features) vs classification (sqrt) in scikit-learn — worth checking
# and tuning explicitly rather than assuming the default is ideal

Everything covered above applies identically to regression — bootstrap sampling, feature subsetting, OOB evaluation, and feature importance all work the same way, with predictions averaged (rather than majority-voted) across trees.

9. Random Forest vs a Single Decision Tree vs Gradient Boosting#

text
Ask AICopy
Single Decision Tree: fast, maximally interpretable, but high variance
  and unstable — rarely the best choice for pure predictive accuracy.

Random Forest: trees trained INDEPENDENTLY and averaged — reduces
  VARIANCE specifically, is quite forgiving of hyperparameter choices,
  trains fast (parallelizable), and provides OOB validation for free.
  Generally an excellent, low-effort baseline.

Gradient Boosting (covered next): trees trained SEQUENTIALLY, each
  correcting previous errors — reduces BIAS primarily, often achieves
  higher peak accuracy with careful tuning, but is more prone to
  overfitting and requires more careful hyperparameter tuning
  (learning rate, early stopping) to get right.

10. Known Limitations#

text
Ask AICopy
1. LESS INTERPRETABLE than a single tree — you can't meaningfully read
   "the" decision path anymore, since there are hundreds of trees each
   contributing a vote/average.

2. LARGER MODEL SIZE — storing hundreds of full trees requires
   significantly more memory and disk space than a single tree or a
   linear model.

3. SLOWER PREDICTION than a single tree or linear model — every tree
   must be evaluated for every prediction (though this is still fast in
   absolute terms for most applications, and is parallelizable).

4. STILL FUNDAMENTALLY AXIS-ALIGNED — like individual decision trees,
   Random Forest splits are still all threshold-based on single features;
   it approximates diagonal/curved boundaries through many small steps
   rather than representing them directly.

5. CAN STRUGGLE TO EXTRAPOLATE — since predictions are essentially
   averages of training-data outcomes within learned regions, a Random
   Forest cannot predict values outside the range it saw during
   training, unlike linear regression, which can (reasonably or not)
   extrapolate beyond the training range.

Notes#

• Random Forest's power comes from combining two distinct sources of randomness — bootstrap sampling AND random feature subsetting — not just from having "many trees" alone.
• The variance-reduction math shows there's a hard floor on how much averaging can help, determined by the residual correlation between trees — this is precisely why feature subsetting (which reduces that correlation) matters as much as it does.
• Individual trees within a forest are typically left deep and unpruned on purpose, a different philosophy from tuning a standalone decision tree.
• Permutation importance is generally more trustworthy than the default feature_importances_ (Mean Decrease in Impurity), which is known to be biased toward high-cardinality features.
• OOB score provides an essentially free, reliable estimate of generalization performance, without needing to sacrifice data to a separate validation split.

Best Practices Checklist#

• Leave individual trees largely unconstrained (deep max_depth) — this is a different tuning philosophy than a standalone tree
• Tune max_features deliberately — it's often the single most impactful hyperparameter, via its effect on tree correlation
• Use oob_score=True to get a free validation estimate rather than always carving out a separate validation set
• Prefer permutation importance over default feature_importances_ when trustworthy importance rankings genuinely matter
• Use n_jobs=-1 to parallelize training across CPU cores, since trees are trained fully independently
• Expect diminishing returns from n_estimators beyond a certain point — more trees mainly stabilize the variance of the estimate, not raw accuracy, past that point
• Choose Random Forest as a strong, low-tuning-effort baseline before investing in more sensitive methods like Gradient Boosting
• Remember Random Forest, like any tree-based method, cannot extrapolate meaningfully beyond the range of values seen in training