Random Forests

What is a Random Forest?

Single decision trees suffer from high variance: small changes in training data produce wildly different tree predictions.

Random Forest (Leo Breiman, 2001) solves this by building an ensemble of hundreds of deep decision trees and averaging their predictions:

  Input Data Sample x
        │
        ├─► [ Decision Tree 1 ] ──► Class A
        ├─► [ Decision Tree 2 ] ──► Class A
        ├─► [ Decision Tree 3 ] ──► Class B   ──► [ MAJORITY VOTE ] ──► Final Prediction: Class A!
        │   ...
        └─► [ Decision Tree N ] ──► Class A

Two Keys to Decorrelation

If all 100 trees in a forest are identical, averaging them provides zero reduction in variance.

Random Forest decorrelates individual trees using two layers of randomness:

┌──────────────────────────┬──────────────────────────┐
│ 1. BOOTSTRAP RESAMPLING  │ 2. RANDOM FEATURE SPLIT  │
├──────────────────────────┼──────────────────────────┤
│ Each tree trains on a    │ At EVERY split node,     │
│ random bootstrap sample  │ evaluate only a random   │
│ of N rows drawn WITH     │ subset of m = sqrt(d)    │
│ replacement.             │ features.                │
└──────────────────────────┴──────────────────────────┘

1. Bootstrap Data Aggregation (Bagging)

For each tree, draw a random bootstrap sample of $N$ rows with replacement from the training dataset.

2. Random Feature Subspacing

In standard trees, every split evaluates all $d$ features, causing strong dominant features to appear at the root of every tree.

Random Forest forces every node split to consider only a random subset of $m = \sqrt{d}$ features (for classification) or $m = d/3$ (for regression).

This prevents strong features from dominating every tree, creating diverse decorrelated trees across the forest.

Out of Bag (OOB) Error: Free Validation

Because bootstrap sampling draws $N$ samples with replacement, the probability that a specific row is never selected for a tree is:

$$\lim_{N \to \infty} \left(1 - \frac{1}{N}\right)^N = \frac{1}{e} \approx 36.8%$$

Roughly 36.8 percent of training data is left out (Out of Bag) for each individual tree!

Evaluating each training sample using only the trees where that sample was Out of Bag provides an unbiased validation score (OOB Error) without needing a separate validation split.

Say this out loud

Random Forest combines hundreds of deep decision trees using Bagging and Random Feature Subspacing. Each tree is trained on a bootstrap sample of rows, evaluating only a random subset of sqrt(d) features at each split node. Averaging predictions across decorrelated trees reduces variance without increasing bias, producing robust predictions without overfitting.

Followups to expect

1. How is Feature Importance calculated in Random Forest? Mean Decrease in Impurity (MDI) measures total impurity reduction contributed by a feature across all trees, or Permutation Importance measures accuracy drop when a feature values are randomly shuffled.
2. Why can't Random Forest extrapolate beyond training ranges in Regression? Individual tree leaf nodes predict constant mean values. Random forest predictions are bounded by the minimum and maximum target values observed in training data.