Core ML2001intermediate10 min read

Random Forests

الغابات العشوائية

Breiman, L. — Machine Learning

The problem

A single is easy to interpret but fragile: small changes in the data produce a completely different tree (high ). Deep trees overfit, shallow trees underfit, and pruning only gets you so far. (bootstrap aggregation) reduces variance by averaging many trees, but when one dominates, every bootstrapped tree splits on it first — making the trees correlated and limiting the variance reduction.

The contribution

Random Forests inject a second layer of randomness on top of bagging: at each , only a random subset of m features (typically √p for ) is considered. This decorrelates the trees so their averaged vote has much lower variance. The paper also introduced the error estimate — a free, built-in cross-validation that uses the ~⅓ of samples each tree never saw — and two measures of : (Gini importance) and . The error converges as trees are added, so Random Forests do not overfit by growing more trees.

The impact

Random Forests became the default "first serious " across virtually every applied domain — genomics, remote sensing, finance, medicine, ecology. They require almost no tuning, handle mixed data types, scale to high dimensions, and come with built-in feature importance. They remain the strongest baseline for and directly inspired XGBoost, which replaced bagging with boosting but kept the tree- framework.

Imagine you need to judge a cooking contest. A single judge may have blind spots — maybe she hates cilantro or over-values presentation. Now imagine a panel of a hundred judges, each one tasting only a random selection of dishes and scoring based on a random subset of criteria (flavor, texture, plating…). No single judge sees the full picture, but their majority vote is remarkably fair and robust.

A works the same way: hundreds of decision trees, each trained on a different random slice of the data and considering only a random handful of features at each split. Individually they are weak and quirky. Together, their vote is one of the most reliable predictions in all of machine learning.

The problem: one tree is fragile

A decision tree (CART) is a powerful idea: split the data recursively on the feature and threshold that best separate the classes (or reduce variance for ). The result is a flowchart anyone can read. But trees have a fatal flaw — high variance. Change a few training examples and the tree may pick entirely different splits, producing a wildly different model. This is the instability that makes a single tree unreliable on its own.

Deeper trees memorize noise (). Shallower trees miss patterns (). Pruning helps, but the core instability remains. The question Breiman asked was: Can we keep the power of trees while taming their variance?

Open in Lab

Click "Resample" to draw a new bootstrap sample and watch how drastically the tree changes. Same data, wildly different structure.

The demo wakes as you arrive…

From bagging to Random Forests: injecting double randomness

Bagging was Breiman's first answer (1996): draw many bootstrap samples (sample N rows with replacement), grow a full tree on each, and average their predictions (regression) or take a majority vote (classification). Averaging reduces variance without increasing — as long as the trees' errors are not too correlated.

But here is the catch: if one feature is extremely predictive, every bagged tree splits on it first. The trees end up correlated, and averaging correlated predictions reduces variance much less than averaging independent ones. This is where the key formula enters.

The variance of the average of B identically distributed (but possibly correlated) predictions is:

\text{Var}\!\left(\bar{X}\right) = \bar{\rho}\,\sigma^2 + \frac{1 - \bar{\rho}}{B}\,\sigma^2

Variance of the ensemble average — ρ̄ = average pairwise correlation between trees · σ² = variance of a single tree · B = number of trees. When ρ̄ is high, the first term dominates — more trees barely help. Reducing ρ̄ is the key.

Random Forests solve this by adding a second injection of randomness: at every split, the tree considers only a random subset of m features (out of the total p). This prevents any single dominant feature from appearing at the top of every tree, decorrelating them. The result: ρ̄ drops, the first term shrinks, and the ensemble achieves much lower variance.

Think of it as a hiring committee: if every interviewer asks the same questions, they'll all form the same opinion. Force each interviewer to pick from a random pool of questions, and you get genuinely independent assessments.

Open in Lab

Compare bagging (all features) vs Random Forest (random feature subset). Notice how RF trees differ more from each other — lower correlation.

The demo wakes as you arrive…

The algorithm: how a Random Forest grows

The full Random Forest algorithm has elegant simplicity. For each of B trees:

Bootstrap: draw N samples with replacement from the training set. About ⅓ of the data is left out — the out-of-bag (OOB) samples.
Grow: at each , randomly select m features (out of p total), find the best split among only those m, and split. Keep growing until nodes are pure (or reach a minimum size). No pruning.
Predict: for classification, each tree casts one vote. The forest output is the majority vote. For regression, it's the average.

The only critical hyperparameter is m — the number of candidate features per split. The default heuristic is $m = \lfloor\sqrt{p}\rfloor$ for classification and $m = \lfloor p/3 \rfloor$ for regression. Breiman showed the algorithm is remarkably robust to this choice.

Open in Lab

Watch a forest grow tree by tree. Each tree sees a different bootstrap sample and random features at each split.

The demo wakes as you arrive…

Free cross-validation: the out-of-bag trick

Each bootstrap sample uses about 63.2% of the training data (the rest are duplicates). The remaining ~36.8% — the out-of-bag (OOB) samples — are data that tree never trained on. To estimate generalization error: for each training example, collect predictions only from trees whose bootstrap sample did not include it, then average or vote. This gives an unbiased estimate of test error without ever needing a separate validation set.

Breiman showed the OOB error is nearly as accurate as but comes completely free — no extra training runs needed. For practitioners, this was transformative: you could tune m, select features, and assess generalization from a single training run.

Open in Lab

Each row is a training example. Green cells = tree trained on it. Empty cells = OOB for that tree. The OOB prediction uses only the empty-cell trees.

The demo wakes as you arrive…

Which features matter? Two importance measures

Random Forests don't just predict — they explain what drives the . Breiman introduced two complementary importance measures:

Mean Decrease Impurity (MDI / Gini importance): for each feature, sum the total reduction in (or variance for regression) across all splits that use that feature, across all trees. Features that produce cleaner splits accumulate higher scores. It's fast to compute but can be biased toward high-cardinality features.

Permutation importance (Mean Decrease ): after training, take the OOB samples, randomly shuffle one feature's values, and re-predict. The drop in accuracy measures how much the forest relies on that feature. If accuracy barely changes, the feature is unimportant. This measure is model-agnostic and more reliable, but slower.

Think of MDI as asking "how often did the forest use this feature?" and permutation importance as asking "how much would it hurt if this feature were scrambled?"

Open in Lab

Toggle between Gini importance and permutation importance. Notice how rankings can differ, especially for correlated or high-cardinality features.

The demo wakes as you arrive…

Why doesn't it overfit?

One of the most counter-intuitive results in the paper: Random Forests do not overfit as you add more trees. Each individual tree overfits wildly — it is grown to full depth with no pruning. But the ensemble converges. Breiman proved using the Strong Law of Large Numbers that the generalization error of the forest converges almost surely to a limit:

PE^* = P_{X,Y}\!\left(P_\Theta(h(X,\Theta)=Y) - \max_{j \ne Y} P_\Theta(h(X,\Theta)=j) < 0\right)

Generalization error upper bound — PE* = generalization error · h(X,Θ) = prediction of a random tree with random parameter Θ · As B → ∞, the forest error converges to PE*, never beyond. More trees = more stable, never worse.

Breiman then bounded this error using two intuitive quantities:

Strength (s): how accurate each individual tree is on average.
(ρ̄): how similar different trees' predictions are.

The bound is $PE^* \le \bar{\rho}\,(1 - s^2) / s^2$ . A good forest maximizes strength and minimizes correlation. The parameter m controls this tradeoff: smaller m → lower correlation but weaker individual trees. The sweet spot is typically near $\sqrt{p}$ .

Open in Lab

Drag the m slider to see how the number of candidate features per split trades off tree strength vs. tree correlation, and their effect on forest error.

The demo wakes as you arrive…

The same idea in code

Random Forest from scratch — the core looppython

Simplified to show the idea — not the real implementation.

import numpy as np
from collections import Counter

def bootstrap_sample(X, y):
    """Draw N samples with replacement. Return in-bag and OOB indices."""
    n = len(y)
    idxs = np.random.choice(n, n, replace=True)
    oob = list(set(range(n)) - set(idxs))
    return X[idxs], y[idxs], oob

def best_split(X, y, feature_indices):
    """Find the best (feature, threshold) among the given subset."""
    best_gini, best_feat, best_thr = float('inf'), None, None
    for f in feature_indices:
        thresholds = np.unique(X[:, f])
        for t in thresholds:
            left = y[X[:, f] <= t]
            right = y[X[:, f] > t]
            g = (len(left) * gini(left) + len(right) * gini(right)) / len(y)
            if g < best_gini:
                best_gini, best_feat, best_thr = g, f, t
    return best_feat, best_thr

def gini(y):
    """Gini impurity: 1 - Σ(pᵢ²)"""
    counts = np.bincount(y)
    probs = counts / counts.sum()
    return 1 - (probs ** 2).sum()

def random_forest(X, y, n_trees=100, m=None):
    """Train a random forest. m = features per split (default √p)."""
    n, p = X.shape
    if m is None:
        m = int(np.sqrt(p))
    trees = []
    oob_preds = {i: [] for i in range(n)}

    for _ in range(n_trees):
        X_boot, y_boot, oob_idxs = bootstrap_sample(X, y)
        tree = grow_tree(X_boot, y_boot, m, p)  # recursive CART
        trees.append(tree)
        # OOB predictions — free cross-validation
        for i in oob_idxs:
            oob_preds[i].append(predict_tree(tree, X[i]))

    # OOB error estimate
    oob_error = np.mean([
        Counter(preds).most_common(1)[0][0] != y[i]
        for i, preds in oob_preds.items() if preds
    ])
    return trees, oob_error

The bias-variance lens: where Random Forests sit

Understanding Random Forests through the makes the design choices click:

Individual trees have low bias (they can fit complex boundaries) but high variance (they change wildly with different data).
Bagging averages many trees, reducing variance without touching bias. But correlated trees limit the reduction.
Random decorrelates the trees, pushing variance down further. It slightly increases bias (each tree sees fewer features) but the variance reduction far outweighs it.

The net effect: Random Forests achieve accuracy close to the best possible (low bias) with much more stability (low variance). They sit in a sweet spot that single trees and even bagged trees cannot reach.

Open in Lab

Slide from 1 tree to 200. Watch how variance drops rapidly while bias stays nearly constant — the classic Random Forest signature.

The demo wakes as you arrive…

Why it mattered

Random Forests are often the first algorithm a data scientist reaches for on a new tabular dataset — and frequently the last one needed. They dominate in fields from bioinformatics (gene selection) to ecology (species distribution) to finance (credit scoring). Breiman showed that a conceptually simple idea — decorrelating bagged trees — could match or beat far more complex methods.

The tree-ensemble idea also paved the way for XGBoost and gradient-boosted trees, which replaced the parallel bagging strategy with sequential boosting but kept the fundamental insight: many weak trees, combined wisely, are stronger than any single sophisticated model.

1984
CART
Breiman, Friedman, Olshen & Stone publish Classification and Regression Trees — the foundation for all tree-based methods.
1996
Bagging
Breiman introduces bootstrap aggregation — averaging multiple trees to reduce variance. The direct predecessor of Random Forests.
2001
Random Forests
Adding random feature selection decorrelates trees and dramatically improves on bagging. Feature importance and OOB error introduced.
2006
Extremely Randomized Trees
Geurts et al. push randomness further — random thresholds, not just random features — trading a bit of bias for even lower variance.
2016
XGBoost dominates Kaggle
XGBoost brings gradient boosting to tree ensembles — sequential correction instead of parallel averaging — and wins most tabular competitions.
2024
Tabular data persists
Despite deep learning advances, tree ensembles (Random Forests, XGBoost, LightGBM) remain the best-performing family for structured tabular data, consistently outperforming neural networks.

CitationBreiman, L.. Random Forests. Machine Learning, 2001.

Terms in this paper

Random Forestالغابة العشوائية خوارزمية
Baggingالتجميع المتوازي للعينات العشوائية
Bootstrap Samplingالمعاينة التمهيدية
Ensembleالنماذج التجميعية الهجينة
Decision Treeشجرة القرار الإحصائية
Out-of-Bag (OOB)العيّنات غير المُستخدَمة
Feature Importanceأهمية السمات
Permutation Importanceأهمية التبديل
Mean Decrease Impurity (MDI)متوسط انخفاض الشائبة
Gini Impurityشائبة جيني
Decorrelationفكّ الارتباط
Tree Strengthقوة الشجرة