AI Engineering Foundations 26: Decision Trees and Random Forests — One Tree Memorizes, a Hundred Trees Vote
*Translated and condensed study note from Lesson 04 of Phase 2 of AI Engineering from Scratch (Rohit Ghumare, MIT License).*
Key points
- Decision trees cut instead of draw lines. Where logistic regression draws a boundary line, a tree slices the feature space into rectangles by asking yes/no questions (age < 30? income > 50k? → approve loan). This interpretability plus tolerance for mixed numeric/categorical features is why gradient-boosted trees (XGBoost, LightGBM) dominate Kaggle tabular competitions, not neural networks.
- Splitting criteria are interchangeable in practice. A 60/40 cat-dog box has Gini impurity 1 − (0.6² + 0.4²) = 0.48; entropy gives 0.971 bits. Across three depth settings, trees trained with either criterion differed by only 2.5–5 percentage points in accuracy — both are monotonic "more mixed = bigger" functions. Gini is preferred for speed (no logarithms).
- Greedy growth needs brakes. Finding the globally optimal tree is NP-hard, so trees grow greedily by maximizing information gain (impurity before minus weighted impurity after). Without stopping conditions, a tree memorizes the training set. The course implements max depth and min-samples-per-leaf but not min-gain — visible evidence: a depth-3 demo tree contains a useless node ("feature 0 < −1.71") whose both leaves predict the same class, because tiny positive gains pass the "gain ≤ 0" cutoff.
- Bootstrap (bagging): each tree trains on a with-replacement sample; ~63.3% of distinct samples appear on average (1 − 1/e ≈ 0.632; measured 0.6335 over 2000 runs). The remaining ~37% are out-of-bag — a free validation set.
- Feature randomization: each split only considers a random subset (√p for classification, p/3 for regression per the 2001 paper). Note: scikit-learn's regression forest defaults to all features, so out-of-the-box you only get bagging, not the paper's second ingredient.
- A hand-written forest reached 0.88 vs 0.95 for scikit-learn at identical hyperparameters — the unimplemented production details are worth ~6–7 points.
- "More trees never hurt" depends on sample size. With only 60 test samples, accuracy dropped from 0.95 (10 trees) to 0.8833 (50 trees) — one flipped sample is worth 1.67 points. With 1200 test samples, the same code shows a monotonic climb: 0.783, 0.870, 0.903, 0.906, 0.921.
- "Forests are more stable" needs scrutiny. Over 5 perturbation rounds, single-tree and forest standard deviations were identical (0.0200). Over 30 rounds: 0.049 vs 0.046 — barely different. What improved was mean accuracy, 0.903 → 0.938. Bagging averages out sampling noise within one dataset, not the noise of changing the training data itself; here the forest buys accuracy, not a flatter curve.
- Deep trees overfit in regression, not always in classification. The fully-grown classification tree hit 100% train accuracy and the best test score (0.85), while in regression, depth 5→10 pushed train error 0.029→0.003 but test error 0.043→0.060. Voting forgives useless deep splits; squared loss does not.
- MDI (Mean Decrease in Impurity) is biased toward high-cardinality features. On a crafted dataset where a binary feature truly determines the label and a 300-valued feature is pure noise, MDI assigned the noise 25% (27% via scikit-learn). More distinct values = more candidate thresholds = more lottery tickets to accidentally reduce impurity. With a perfectly clean label, the noise steals 0.0 — the bias needs both high cardinality and residual impurity.
- Permutation importance must be measured on unseen data. Shuffling the noise feature on the training set drops accuracy by 4 points (destroying memorized answers); on held-out data it drops only 1.6, versus 37.8 for the true feature. Training-set permutation measures memorization; held-out permutation measures understanding.
- The course's Exercise 5 (both rulers + one high-cardinality noise feature + untouched fresh data) packs all these pitfalls and remedies into a single exercise.