A compact reference for the formulas, algorithms, and knobs used throughout the book.

Impurity and split criteria

Criterion Formula Used by
Gini impurity \(1-\sum_k p_k^2\) CART classification (default)
Entropy \(-\sum_k p_k\log_2 p_k\) ID3, C4.5
Information gain \(I(\text{parent})-\sum_c \frac{n_c}{n}I(c)\) all classification trees
Variance / MSE \(\frac1n\sum_i (y_i-\bar y)^2\) regression trees
Cost-complexity \(R_\alpha(T)=R(T)+\alpha|T|\) CART pruning

Gradient boosting in one page

  1. Initialize \(F_0(x)=\arg\min_c \sum_i L(y_i,c)\) (e.g. mean for MSE, log-odds for log-loss).

  2. For \(m=1,\dots,M\):

    1. Pseudo-residuals \(r_i=-\big[\partial L(y_i,F(x_i))/\partial F(x_i)\big]_{F=F_{m-1}}\).

    2. Fit a regression tree \(h_m\) to \(\{(x_i,r_i)\}\).

    3. (XGBoost) optimal leaf weight \(w_j^\star=-\dfrac{\sum_{i\in j}g_i}{\sum_{i\in j}h_i+\lambda}\) using gradients \(g_i\), Hessians \(h_i\).

    4. Update \(F_m(x)=F_{m-1}(x)+\nu\,h_m(x)\) with learning rate \(\nu\).

  3. Output \(F_M(x)\); choose \(M\) by early stopping on a validation set.

Hyperparameter cheat-sheet

Parameter Effect Typical range
n_estimators / trees more trees: RF stabilizes, GBM can overfit RF 200–1000; GBM via early stop
learning_rate (\(\nu\)) step size; smaller = more trees 0.01–0.1 (GBM)
max_depth tree complexity 3–8 (GBM), deeper/None (RF)
num_leaves LightGBM complexity \(<2^{\text{max\_depth}}\)
min_child_samples min data per leaf; regularizes 10–100
subsample row sampling per tree 0.6–1.0
colsample_bytree / max_features column sampling; decorrelates 0.6–1.0; \(\sqrt p\) or \(p/3\) (RF)
reg_lambda / reg_alpha L2 / L1 on leaf weights 0–10
gamma / min split gain minimum gain to split 0–5

Method selection at a glance

Method Strength Use when
Single tree interpretable flowchart you need one readable rule set
Random forest robust, low-tuning, OOB strong baseline, little tuning time
Gradient boosting highest tabular accuracy you can tune + validate carefully
Isolation forest unsupervised anomalies outlier/fraud/defect detection
EBM / GA\(^2\)M glass-box accuracy accuracy and full interpretability
Stacking (trees+NN) top accuracy competitions, max performance

Key references

  • Breiman, Friedman, Olshen, Stone, Classification and Regression Trees (1984).

  • Breiman, “Bagging Predictors” (1996); “Random Forests” (2001).

  • Freund & Schapire, AdaBoost (1997); Friedman, “Greedy Function Approximation: A Gradient Boosting Machine” (2001).

  • Chen & Guestrin, “XGBoost” (2016); Ke et al., “LightGBM” (2017); Prokhorenkova et al., “CatBoost” (2018).

  • Lundberg & Lee, “A Unified Approach to Interpreting Model Predictions” (SHAP, 2017).

  • Grinsztajn et al., “Why do tree-based models still outperform deep learning on tabular data?” (2022).

  • Hastie, Tibshirani, Friedman, The Elements of Statistical Learning; James et al., An Introduction to Statistical Learning.