Random forest algorithm

WHAT is a Random Forest?

The two sources of randomness (rows + features) are the whole trick. They make the trees disagree in their errors so that averaging helps.

WHY does averaging help? (Derive from first principles)

Suppose we have $B$ trees, each producing a prediction that is a random variable with variance $\sigma^2$ . Let $\rho$ be the average pairwise correlation between two trees' predictions. What is the variance of the average $\bar{f} = \frac{1}{B}\sum_{b=1}^{B} f_b$ ?

Step 1 — variance of a sum. For any random variables, $\operatorname{Var}\!\Big(\sum_{b} f_b\Big) = \sum_b \operatorname{Var}(f_b) + \sum_{i\neq j}\operatorname{Cov}(f_i,f_j).$ Why this step? Variance of a sum splits into individual variances plus every covariance pair — this is the definition of variance applied to a sum.

Step 2 — plug in identical variances and correlations. There are $B$ diagonal terms each $\sigma^2$ , and $B(B-1)$ off-diagonal terms each $\operatorname{Cov}=\rho\sigma^2$ : $\operatorname{Var}\!\Big(\sum_{b} f_b\Big) = B\sigma^2 + B(B-1)\rho\sigma^2.$

Step 3 — divide by $B^2$ (because $\bar f = \frac1B\sum f_b$ , and $\operatorname{Var}(aX)=a^2\operatorname{Var}(X)$ ): $\boxed{\operatorname{Var}(\bar f) = \rho\sigma^2 + \frac{1-\rho}{B}\sigma^2}$

HOW to build one (the algorithm)

Worked example Random Forest training loop

Given data $\{(x_i,y_i)\}_{i=1}^{n}$ , $p$ features, $B$ trees:

for b = 1 ... B:
    1. Draw a bootstrap sample D_b of size n (rows sampled WITH replacement)
    2. Grow a tree T_b on D_b:
         at each node:
           - pick m of the p features at random
           - choose the best split only among those m
         grow FULLY (no/low pruning)
Predict:
    classification -> majority vote of {T_b(x)}
    regression     -> average of {T_b(x)}

Typical $m = \sqrt{p}$ (classification) or $m = p/3$ (regression). Why this step? Small $m$ ⇒ trees forced onto different features ⇒ lower $\rho$ ; but too small ⇒ each tree too weak. $\sqrt p$ is the empirical sweet spot.
Trees are grown deep & unpruned. Why? We want high-variance/low-bias individuals; averaging fixes the variance.

Free lunch: Out-of-Bag (OOB) error

Probability a given row is NOT in a bootstrap sample. Each of the $n$ draws misses that row with probability $\frac{n-1}{n}$ . Independently over $n$ draws: $P(\text{row left out}) = \Big(1-\tfrac1n\Big)^{n} \xrightarrow{n\to\infty} e^{-1}\approx 0.368.$ Why this step? $(1-1/n)^n$ is the classic limit definition of $e^{-1}$ .

Feature importance (bonus interpretability)

Two common measures:

Mean Decrease in Impurity (MDI): sum the impurity reduction (Gini/entropy) each feature causes, averaged over all trees.
Permutation importance: shuffle one feature's values and measure how much OOB accuracy drops. Big drop ⇒ important feature.

Common Mistakes (Steel-man + fix)

Active Recall

Recall What are the TWO randomness sources and what does each achieve?

(1) Bootstrap rows → bagging, reduces variance via averaging. (2) Random feature subset per split → de-correlates trees, lowers $\rho$ , shrinks the variance floor $\rho\sigma^2$ .

Recall Why grow trees deep and unpruned?

We want low-bias, high-variance learners; averaging over many trees kills the variance, so bias is what we minimize per tree.

Recall Derive the variance of the averaged ensemble.

$\operatorname{Var}(\bar f)=\rho\sigma^2+\frac{1-\rho}{B}\sigma^2$ ; second term → 0 as $B\to\infty$ , leaving floor $\rho\sigma^2$ .

Recall What fraction of data is OOB per tree and why?

$\approx 36.8\%$ , because $(1-1/n)^n\to e^{-1}$ .

Recall Feynman: explain a random forest to a 12-year-old.

Imagine one really clever friend who sometimes gets carried away and gives weird answers. Instead of trusting just her, you ask 100 friends, but you only let each friend peek at some of the clues and some of the past examples. Then you go with whatever most of them say. Because they each looked at different things, their silly mistakes don't line up — so the crowd's answer is steadier and usually right. That crowd of decision-tree "friends" is a random forest.

80/20 — the vital few

Two randomnesses: rows (bagging) + features per split (de-correlation).
Variance law: $\operatorname{Var}(\bar f)=\rho\sigma^2+\frac{1-\rho}{B}\sigma^2$ → lowering $\rho$ matters most.
Deep unpruned trees; average/vote; ~37% OOB for free validation.

Connections

Decision Trees — the base learner inside every forest.
Bagging (Bootstrap Aggregating) — the row-sampling half of RF.
Bias-Variance Tradeoff — why averaging low-bias/high-variance trees works.
Gradient Boosting — contrasting ensemble: sequential, bias-reducing, not variance-reducing.
Cross-Validation — replaced for free by OOB error.
Feature Importance — MDI & permutation importance.
Gini Impurity & Entropy — split criteria used inside each tree.

What defines a Random Forest beyond plain bagging?

Random feature-subset selection at each split, which de-correlates the trees (lowers ρ).

Variance of an averaged ensemble of B trees with variance σ² and pairwise correlation ρ?

Var = ρσ² + (1−ρ)/B · σ².

As B→∞, what does ensemble variance approach?

ρσ² — the irreducible floor set by tree correlation.

Why do we grow forest trees deep and unpruned?

To keep bias low; averaging over many trees handles the variance.

What fraction of rows is out-of-bag for each tree and why?

≈36.8%, since (1−1/n)^n → e⁻¹.

Typical m (features per split) for classification vs regression?

√p for classification, p/3 for regression.

Two ways to measure feature importance in RF?

Mean Decrease in Impurity (MDI) and permutation importance.

How does a RF predict for classification vs regression?

Majority vote of trees / average of tree outputs.

Why can't adding more trees drive error to zero?

Variance floor ρσ² is independent of B; only lowering ρ helps.

Purpose of OOB error?

Built-in validation using rows each tree didn't train on — free CV-like estimate.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, ek single decision tree bahut smart hota hai par thoda "moody" — wo training data ke chote chote quirks bhi yaad kar leta hai, isliye uski predictions me variance zyada hota hai. Random forest ka funda simple hai: ek tree pe bharosa mat karo, bahut saare trees banao aur unka vote (classification) ya average (regression) le lo. Jab bahut saare thodi-thodi galti karne wale experts ki galtiyan alag-alag directions me hoti hain, to average lene pe wo galtiyan cancel ho jaati hain aur asli signal bach jaata hai.

Ab do randomness ka role samjho. Pehla: har tree ko bootstrap sample milta hai — rows ko with replacement uthate hain (isko bagging bolte hain). Dusra, aur ye asli magic hai: har split pe tree ko sirf kuch random features (m out of p, usually √p) dekhne dete hain. Kyu? Kyunki agar sab trees ko saare features de do, to sab ke sab wahi ek strong feature top split pe use karenge aur sab trees ek jaise (correlated) ban jaayenge — averaging ka fayda kam. Random features force karte hain ki trees alag-alag socho, yani correlation ρ kam.

Variance ka formula yaad rakho: $\operatorname{Var}(\bar f)=\rho\sigma^2+\frac{1-\rho}{B}\sigma^2$ . Jaise-jaise trees B badhao, dusra term $\frac{1-\rho}{B}$ gayab ho jaata hai, par pehla term $\rho\sigma^2$ ek floor hai jise sirf trees badha ke tod nahi sakte. Isliye "aur trees dalo" se accuracy infinite tak nahi badhti — ρ kam karna hi real game hai. Ye ek badi galti hai jo students karte hain.

Ek aur cool cheez — OOB error. Bootstrap me har tree ke liye lagbhag $36.8\%$ rows chhoot jaati hain ( $(1-1/n)^n \to e^{-1}$ ). Wo left-out rows free ki validation set ban jaati hain, to alag se cross-validation ki zarurat hi nahi. Aur haan — forest me trees ko deep aur unpruned rakho, kyunki hume low-bias individuals chahiye; variance to averaging khud sambhal legi.

WHAT is a Random Forest?

WHY does averaging help? (Derive from first principles)

HOW to build one (the algorithm)

Free lunch: Out-of-Bag (OOB) error

Feature importance (bonus interpretability)

Common Mistakes (Steel-man + fix)

Active Recall

80/20 — the vital few

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Tree-Based & Instance Methods

Connections