Decision trees and random forests

The idea

A decision tree predicts by asking a sequence of threshold questions — is income below 40k? is age above 30? — until it reaches a leaf, which outputs the majority class (or mean) of the training points that landed there. Training is greedy recursive partitioning: at each node, try every feature and threshold, score each candidate by how much it reduces impurity, take the best, recurse.

$G = 1 - \sum_k p_k^2 \qquad\qquad H = -\sum_k p_k \log_2 p_k$

Gini and entropy agree almost always; Gini skips the logarithm. The split's score is the impurity decrease: parent impurity minus the child impurities weighted by the fraction of samples each child receives.

Trees are loved for the wrong reason in production and the right reason in interviews: no scaling needed (splits are monotone-invariant), native handling of mixed feature types and interactions, and total interpretability — but grown unconstrained they are low-bias, high-variance learners. Greediness makes it worse: perturb the data, an early split flips, and everything below it reshuffles.

Random forests: average away the variance. Train $B$ deep trees, each on a bootstrap resample (bagging), each split restricted to a random feature subset (max_features / mtry), and average (or vote). The payoff is the one formula worth memorizing — variance of an average of identically distributed trees with variance $\sigma^2$ and pairwise correlation $\rho$ :

$\text{Var}\big(\bar{f}\big) = \rho\sigma^2 + \frac{1-\rho}{B}\,\sigma^2$

$B \uparrow$ kills the second term — so more trees never overfit; error converges.
The floor $\rho\sigma^2$ is untouched by $B$ — the only way past it is decorrelating the trees, which is the entire purpose of bootstrap noise and feature subsampling. Restrict features per split and a dominant feature can no longer captain every tree.
Bias stays roughly that of a single deep tree (low). Bagging is a pure variance play — which is why it does little for already-stable learners like linear regression.

Two freebies: OOB error (each tree misses ~36.8% of rows in its bootstrap; validate on those — a built-in CV substitute) and feature importances (impurity-based ones are biased toward high-cardinality features; prefer permutation importance on held-out data).

Worked example

A node holds 10 samples: 6 positive, 4 negative.

$G_{\text{parent}} = 1 - (0.6^2 + 0.4^2) = 1 - 0.52 = 0.48$

Candidate split: left child gets 4 samples (4+, 0−), right child gets 6 samples (2+, 4−).

\begin{aligned} G_{\text{left}} &= 1 - (1^2 + 0^2) = 0, \\ G_{\text{right}} &= 1 - \left[ \left(\tfrac{1}{3}\right)^2 + \left(\tfrac{2}{3}\right)^2 \right] \\ &= 1 - \tfrac{5}{9} \approx 0.444. \end{aligned}

Weighted child impurity and gain:

$G_{\text{split}} = \tfrac{4}{10}(0) + \tfrac{6}{10}(0.444) \approx 0.267, \qquad \Delta G = 0.48 - 0.267 = 0.213$

The tree computes this $\Delta$ for every feature-threshold candidate and keeps the max. (Entropy version: $H_{\text{parent}} = -(0.6\log_2 0.6 + 0.4\log_2 0.4) \approx 0.971$ bits — same ranking of splits here.)

Forest arithmetic: suppose single deep trees have test-MSE variance $\sigma^2 = 1.0$ and average pairwise correlation $\rho = 0.3$ . With $B = 100$ trees:

$\text{Var} = 0.3 + \frac{0.7}{100} = 0.307$

A 3.3x variance cut — but notice 0.3 of it is the correlation floor. Doubling to $B = 200$ gives 0.3035 (nothing); cutting $\rho$ to 0.15 via stronger feature subsampling gives $0.15 + 0.0085 = 0.1585$ — decorrelation is worth more than tree count once $B$ is large.

Cheat sheet

Impurity: Gini $1 - \sum p_k^2$ ; entropy $-\sum p_k \log_2 p_k$ ; split gain = parent − weighted children. Regression trees: variance / MSE reduction.

Forest variance: $\rho\sigma^2 + \frac{1-\rho}{B}\sigma^2$ → trees kill the right term, decorrelation (bagging + max_features) kills the left.

Knob	Moves	Direction
max_depth, min_samples_leaf	per-tree bias/variance	shallower = more bias, less variance
max_features (mtry)	tree correlation $\rho$	smaller = less correlated, sometimes more per-tree bias
n_estimators $B$	uncorrelated variance term only	more never overfits; returns diminish
ccp_alpha (pruning, single tree)	tree size	CV-tune it

Defaults worth knowing: classification mtry $\approx \sqrt{p}$ , regression $\approx p/3$ .
Trees need no feature scaling; handle interactions natively; extrapolate FLAT outside the training range (regression gotcha).
Greedy = locally optimal splits; XOR-style patterns can be missed.
OOB error $\approx$ CV estimate, free ( $e^{-1} \approx 36.8\%$ of rows out-of-bag per tree).
Impurity importance is biased (high-cardinality features win by chance); use permutation importance on validation data.
Bagging reduces variance, not bias — pair with LOW-bias base learners (deep trees). Boosting is the bias-reducing counterpart.
Class imbalance: forests inherit it — use class_weight or balanced bootstraps.