Exercises — Random forest algorithm

(c). Plain bagging already does (a), (b), and usually (d). The defining extra is the random feature subset considered at each split, which de-correlates the trees (lowers $\rho$).

Rule of thumb $m=\sqrt{p}$. Here $\sqrt{16}=4$. So $m=4$.

${\left(1-\frac{1}{n}\right)}^n\to e^{-1}\approx 0.368$, so about $==36.8\%==$ of rows are OOB per tree.

Plug into $\mathrm{Var}(\bar{f})=\rho {\sigma }^2+\frac{1-\rho }{B}{\sigma }^2$.

• $B=10$: $0.25\cdot 4+\frac{1-0.25}{10}\cdot 4=1+\frac{0.75}{10}\cdot 4=1+0.3=1.3$.
• $B\to \infty$: the second term $\to 0$, leaving the floor $\rho {\sigma }^2=0.25\cdot 4=1.0$.

So even infinite trees cannot beat variance $1.0$ — that floor is set by $\rho$.

• $B=10$: $0.05\cdot 4+\frac{1-0.05}{10}\cdot 4=0.2+\frac{0.95}{10}\cdot 4=0.2+0.38=0.58$.
• Floor: $0.05\cdot 4=0.20$.

Lowering $\rho$ from $0.25$ to $0.05$ dropped the achievable floor from $1.0$ to $0.2$ — a 5× improvement that no amount of extra trees could have delivered. This is the variance-reduction engine of RF.

Each of the 5 draws misses the target row with probability $\frac{4}{5}$; draws are independent: $P(\text{OOB})={\left(\frac{4}{5}\right)}^5=\frac{1024}{3125}=\mathrm{0.32768.}$ Compare $e^{-1}\approx 0.3679$. Small $n$ gives a slightly lower fraction; the limit $0.368$ is approached from below as $n$ grows.

Step 1 — split the variance of a sum. For $\bar{f}=\frac{1}{B}{\sum }_{b=1}^B{f}_b$, $\mathrm{Var}\left({\sum }_b{f}_b\right)={\sum }_b\mathrm{Var}(f_b)+{\sum }_{i\ne j}\mathrm{Cov}(f_i,f_j).$ WHAT: wrote the variance of a sum as diagonal (own variances) plus off-diagonal (all covariance pairs). WHY: this is the definition of variance applied to a sum — nothing assumed yet.

Step 2 — use identical variance and correlation. Each $\mathrm{Var}(f_b)={\sigma }^2$ (there are $B$ of them). Each covariance pair equals $\mathrm{Cov}=\rho {\sigma }^2$ (there are $B(B-1)$ ordered pairs, since correlation $\rho =\frac{\mathrm{Cov}}{{\sigma }^2}$): $\mathrm{Var}\left({\sum }_b{f}_b\right)=B{\sigma }^2+B(B-1)\rho {\sigma }^2.$ WHAT: replaced every abstract $\mathrm{Var}(f_b)$ with the single number ${\sigma }^2$ and every $\mathrm{Cov}(f_i,f_j)$ with the single number $\rho {\sigma }^2$, then counted how many of each there are ($B$ diagonal, $B(B-1)$ off-diagonal). WHY: the trees are identically distributed (same variance) and share one common pairwise correlation, so we can count identical terms instead of tracking $B^2$ separate ones.

Step 3 — divide by $B^2$ and simplify. Because $\bar{f}=\frac{1}{B}\sum f_b$ and $\mathrm{Var}(aX)=a^2\mathrm{Var}(X)$ with $a=\frac{1}{B}$: $\mathrm{Var}(\bar{f})=\frac{1}{B^2}[B{\sigma }^2+B(B-1)\rho {\sigma }^2]=\frac{{\sigma }^2}{B}+\frac{(B-1)}{B}\rho {\sigma }^2.$ WHAT: pulled the $\frac{1}{B}$ out front as $\frac{1}{B^2}$ and distributed it over both counted terms. WHY divide by $B^2$: the average multiplies the sum by $\frac{1}{B}$, and variance scales by the square of any constant factor, so $\frac{1}{B}$ becomes $\frac{1}{B^2}$ — this is the only way to turn the variance of the sum into the variance of the average. Now rewrite $\frac{B-1}{B}=1-\frac{1}{B}$: $\mathrm{Var}(\bar{f})=\rho {\sigma }^2+\frac{1-\rho }{B}{\sigma }^2.■$ WHY rewrite $\frac{B-1}{B}$ as $1-\frac{1}{B}$: this algebraic step separates the correlation contribution into a $B$-independent floor ($\rho {\sigma }^2$, from the constant $1$) plus a decaying remainder ($-\frac{\rho }{B}{\sigma }^2$, which merges with $\frac{{\sigma }^2}{B}$ into $\frac{1-\rho }{B}{\sigma }^2$). Without this rewrite the floor and the decaying part stay tangled together and the punchline is hidden. WHAT IT LOOKS LIKE: the figure below plots exactly this split — a flat amber floor ($\rho {\sigma }^2$) plus a cyan decaying piece that dies as $B$ grows.

Floor $=\rho {\sigma }^2=0.2$. "Within $10\%$" means the extra term $\frac{1-\rho }{B}{\sigma }^2\le 0.10\times 0.2=0.02$. $\frac{(1-0.05)\cdot 4}{B}\le 0.02\Rightarrow \frac{3.8}{B}\le 0.02\Rightarrow B\ge \frac{3.8}{0.02}=190.$ So $B=190$ trees. Interpretation: a couple hundred trees essentially exhausts the benefit of adding more — matching the "diminishing returns plateau."

• A: $0.30\cdot 1+\frac{0.70}{500}\cdot 1=0.30+0.0014=0.3014$.
• B: $0.10\cdot 1+\frac{0.90}{50}\cdot 1=0.10+0.018=0.118$.

Forest B wins ($0.118<0.3014$) despite having 10× fewer trees. Lesson: lowering $\rho$ beats piling on trees. A's floor ($0.30$) is already worse than B's total variance.

• A: $0.30\cdot 1+\frac{0.70}{500}\cdot 1=0.30+0.0014=0.3014$.
• B: $0.10\cdot 1+\frac{0.90}{50}\cdot 1=0.10+0.018=0.118$.

Forest B wins ($0.118<0.3014$) despite having 10× fewer trees. Lesson: lowering $\rho$ beats piling on trees. A's floor ($0.30$) is already worse than B's total variance.

There are two competing effects as $m$ changes:

1. Small $m$ → trees forced onto different features → lower $\rho$ → lower variance floor. (good)
2. Small $m$ → at each split the tree is only allowed to see a random handful of features, so with high probability the truly predictive feature is not among the $m$ candidates at many nodes. The tree is then forced to split on weaker, noisier features. This has two consequences per tree: its splits are less aligned with the true signal, so it fits the signal worse (higher bias), and because which weak feature it lands on is itself random from node to node, its predictions swing more from one bootstrap sample to the next (higher ${\sigma }^2$). Concretely, ${\sigma }^2$ here is the variance of one tree's prediction across resamples; starving the tree of the good feature makes that prediction more erratic, so ${\sigma }^2$ rises. (bad)

On very noisy data the signal is fragile; too-small $m$ makes individual trees too weak (effect 2 dominates), so raising $m$ can improve OOB error even though $\rho$ rises. This is precisely the Bias-Variance Tradeoff playing out through $m$: you tune $m$ to balance de-correlation (lower $\rho$) against per-tree strength (lower bias and ${\sigma }^2$). Use Cross-Validation or the free OOB error to pick $m$.

• Random forest builds trees in parallel and independently, then averages. The averaging is exactly the $\mathrm{Var}(\bar{f})=\rho {\sigma }^2+\frac{1-\rho }{B}{\sigma }^2$ mechanism: it drives down variance. So each tree is deliberately low-bias / high-variance (deep, unpruned), and averaging cleans up the variance. See Bagging (Bootstrap Aggregating).
• Gradient boosting builds trees sequentially, each new tree fitting the residual errors of the current ensemble. That fixes systematic under-fitting → it reduces bias. Its base learners are typically shallow (high-bias / low-variance), the opposite choice. See Gradient Boosting.

One sentence: RF averages many strong-but-jittery trees to kill variance; boosting stacks many weak-but-steady trees to kill bias.

MDI sums the impurity reduction (Gini/entropy drop) a feature causes across splits. A high-cardinality feature (many distinct values) can slice the data into tiny near-pure buckets, producing large apparent impurity reductions even on noise — it is biased toward such features. A more reliable measure is permutation importance: shuffle the feature's values and measure the drop in OOB accuracy. If the ID column were truly useless, shuffling it wouldn't hurt OOB accuracy, exposing MDI's inflation. See Feature Importance.

Scenario: all trees are already highly correlated — e.g. one feature is so dominant that every tree splits on it first regardless of the subset ($\rho \approx 0.9$). Then $\mathrm{Var}(\bar{f})\approx 0.9{\sigma }^2$ almost independent of $B$; the $\frac{1-\rho }{B}{\sigma }^2$ term is already tiny. More trees change nothing.

Fix 1 — lower $\rho$: shrink $m$ (fewer features considered per split) so trees are forced off the dominant feature onto alternative ones; this drops the correlation and hence the floor $\rho {\sigma }^2$. Grounded in de-correlation. Fix 2 — attack ${\sigma }^2$ (and bias) directly: engineer or remove the single dominant/noisy feature, or gather more training data; both shrink each tree's prediction variance ${\sigma }^2$, which lowers the floor $\rho {\sigma }^2$ multiplicatively (the floor is the product of $\rho$ and ${\sigma }^2$, so cutting either factor cuts the floor). Validate any such change with the free OOB error.

Both fixes target the product $\rho {\sigma }^2$, which is the only lever left once $B$ is large — extra trees only touch the already-vanished $\frac{1-\rho }{B}{\sigma }^2$ term.

Set $\rho =0$ in $\mathrm{Var}(\bar{f})=\rho {\sigma }^2+\frac{1-\rho }{B}{\sigma }^2$: $\mathrm{Var}(\bar{f})=0+\frac{1-0}{B}{\sigma }^2=\frac{{\sigma }^2}{B}.$ This is the textbook variance of an average of $B$ independent estimators — it $\to 0$ as $B\to \infty$. Why RF can't reach it: real trees are trained on overlapping bootstrap samples of the same dataset and share the same predictive signal, so their predictions are positively correlated ($\rho >0$). Feature subsampling reduces $\rho$ but cannot make it $0$ — hence a nonzero floor $\rho {\sigma }^2$ always remains. The gap between $\frac{{\sigma }^2}{B}$ (ideal) and $\rho {\sigma }^2$ (reality) is literally the cost of correlation.

Baseline ($B=100,\rho =0.20,{\sigma }^2=2$): $0.20\cdot 2+\frac{0.80}{100}\cdot 2=0.4+0.016=\mathrm{0.416.}$ (A) $B=400$, $\rho =0.20$: $0.20\cdot 2+\frac{0.80}{400}\cdot 2=0.4+0.004=0.404$. Reduction from baseline $=0.416-0.404=0.012$. (B) $B=100$, $\rho =0.12$: $0.12\cdot 2+\frac{0.88}{100}\cdot 2=0.24+0.0176=0.2576$. Reduction from baseline $=0.416-0.2576=0.1584$.

(B) wins by a landslide — lowering $\rho$ cut variance by $\approx 0.158$ versus $\approx 0.012$ for quadrupling trees, roughly a 13× larger improvement. General lesson: once you are past a few hundred trees, the $\frac{1-\rho }{B}{\sigma }^2$ term is already small, so extra trees buy almost nothing; spend your effort on de-correlation (lowering $\rho$) — feature engineering, smaller $m$, less-redundant features — because that is the only lever that moves the floor $\rho {\sigma }^2$. See figure.