Decision Trees and Random Forests: From Information Gain to Why Bagging Reduces Variance

Decision trees are the most interpretable non-linear model. Random forests take a collection of overfit trees and average their variance away. Gradient boosted trees (XGBoost) take a collection of underfit trees and reduce their bias iteratively. Understanding why these ensemble methods work requires understanding variance decomposition — and that starts with a single tree.

Decision trees and their ensembles are the most widely deployed ML models in tabular data across industry. Not because they are theoretically elegant (though they are), but because they handle mixed types, missing values, outliers, and non-linear relationships with little preprocessing, and because their predictions can be explained.

Decision trees: structure and splitting

A decision tree recursively partitions the feature space with axis-aligned splits. At each node, we choose a feature j and a threshold t and split: left child gets samples where xⱼ ≤ t; right child gets samples where xⱼ > t. A leaf predicts the majority class (classification) or the mean outcome (regression). The recursive partitioning continues until a stopping criterion: maximum depth, minimum samples per leaf, or impurity below threshold.

Impurity measures: what we actually optimise

The split is chosen to maximise the reduction in impurity. Gini impurity: Gini(S) = 1 - Σₖ pₖ² where pₖ is the proportion of class k in set S. Intuition: if you randomly pick two samples from S, what is the probability they have different labels? Gini = 0 for pure nodes (all same class); Gini = 1-1/K for maximum disorder. Entropy: H(S) = -Σₖ pₖ log pₖ (information entropy from Post 104). Both measure disorder; Gini is cheaper to compute (no log) and preferred by CART. Information gain: IG(S, j, t) = H(S) - [|S_L|/|S| H(S_L) + |S_R|/|S| H(S_R)]. We subtract the weighted average entropy of the two child nodes from the parent's entropy. The best split maximises information gain. For regression: replace entropy/Gini with variance reduction.

The bias-variance view of a single tree

An unpruned decision tree grown to full depth can perfectly memorise the training set (zero bias, very high variance). Different random training sets would produce very different trees. A shallow tree has high bias (underfits) but low variance. This is the fundamental bias-variance trade-off made concrete in a single model.

Bagging: why averaging reduces variance

Bagging (Bootstrap Aggregation, Breiman 1994): train B models on independently bootstrapped datasets (sample n with replacement from training set), average their predictions. Mathematical result: if each model has variance σ² and models are uncorrelated, the average has variance σ²/B. Correlation between models (they all see similar data) reduces the variance reduction — you can never get better than the average of B identical models: Var(average) = σ²/B + ((B-1)/B) ρ σ² where ρ is the pairwise correlation. The key to bagging is decorrelating the trees. This is what randomness buys you.

Random Forests: decorrelating the trees

Random Forests (Breiman, 2001) add feature randomness on top of bootstrap sampling: at each node, only a random subset of features (m ≪ d, typically m = √d for classification) are considered as split candidates. This decorrelates the trees because they can no longer all pick the same dominant feature. Effect: ρ decreases → more variance reduction from averaging. Typically m = √d for classification, m = d/3 for regression. Out-of-bag error (OOB): for each training sample, it is not included in ≈37% of bootstrap samples. Use those B*0.37 trees that didn't see this sample to predict it — gives a free validation estimate without a holdout set.

Feature importance in Random Forests

Mean Decrease Impurity (MDI): average the impurity decrease from each split on feature j, weighted by the number of samples reaching that node, across all trees. Fast but biased toward high-cardinality features and sensitive to correlated features. Mean Decrease Accuracy (MDA / permutation importance): for each tree's OOB samples, permute feature j's values and measure the drop in accuracy. Average across all trees. Slower but more robust and model-agnostic. SHAP TreeExplainer computes exact Shapley values for tree ensembles in O(T L d) time — the preferred method for interpretable RF.

Boosting vs bagging

Bagging: parallel training, reduces variance, works best with low-bias high-variance base learners (deep trees). Boosting: sequential training, reduces bias, works best with high-bias low-variance base learners (shallow trees / stumps). In gradient boosting (XGBoost, LightGBM), each new tree fits the residuals (negative gradient of the loss) of the current ensemble — see Post 73. Random Forests almost always underperform well-tuned gradient boosted trees on tabular data, but are faster to train and require less hyperparameter tuning.

Interview questions on this topic

"Why do Random Forests not overfit as you add more trees?" — Adding more trees reduces variance (each tree's noise averages out) but does not increase bias. You can keep adding trees until variance is negligible. You can overfit by growing very deep trees (high individual variance) but the averaging prevents the ensemble from overfitting in the same way a single deep tree does.

"What is the difference between Gini impurity and entropy as splitting criteria? When does it matter?" — Gini is cheaper to compute. Entropy can produce slightly different splits in theory but in practice the trees look nearly identical and performance differences are negligible. Neither is reliably better.

"A feature has very high MDI (mean decrease impurity) importance but near-zero MDA (permutation importance). What does this mean?" — The feature is correlated with other informative features. MDI is inflated because the tree uses the feature as a proxy for the correlated features. Permutation importance captures the unique contribution of the feature — since correlated features can substitute, shuffling one doesn't hurt accuracy much.

"Why does Random Forest use √d features per split? What happens if you use all d features?" — With all d features, trees are correlated (all tend to split on the same dominant features), reducing the variance benefit of averaging. √d is a heuristic that balances individual tree quality (more features = better individual splits) and decorrelation (fewer features = less correlated trees). Tuning m is often worthwhile.

Try on Colab: grow a single decision tree to depth 1, 3, 5, unlimited on the Wisconsin Breast Cancer dataset. Plot training vs test accuracy as a function of depth. Then train a Random Forest with 10, 100, 1000 trees. Show that test accuracy stops improving and never degrades as tree count increases. Compare MDI vs MDA feature importances for the top 5 features.