Part II · Kernels and graphs | decision trees as rooted graphs, CART and impurity, pruning, bagging and random forests, variable importance, AdaBoost, gradient boosting, XGBoost and LightGBM, why trees win on tabular data, Shapley values and TreeSHAP, BART, causal forests and uplift | reading: Hastie, Tibshirani & Friedman, ESL, ch. 9.2, 10, 15; Chen & Guestrin (2016); Lundberg et al. (2020); Wager & Athey (2018)
This is the first of three lectures on graph-based methods. Here the graph is a tree: a rooted graph in which every internal node asks a yes-or-no question about one feature, every edge is an answer, and every leaf makes a prediction. Following a path from the root to a leaf applies a chain of rules, and the leaves partition feature space into boxes. A single tree is easy to read and easy to overfit. Two ideas turn trees into the most accurate methods we have for tabular data. Averaging many trees grown on resampled data (bagging, random forests) reduces variance. Adding trees one at a time, each correcting the errors of the sum so far (boosting, XGBoost), reduces bias. We will also see how to explain a boosted model's individual predictions with Shapley values from game theory, and how forests estimate who benefits from a treatment.
By the end of this lecture you should be able to grow a classification or regression tree by greedy impurity reduction and prune it; explain why trees are unstable and prove the variance formula behind random forests; derive AdaBoost's training-error bound and its link to exponential loss; describe gradient boosting as gradient descent in function space for any loss; derive XGBoost's leaf weights and split gain; compare tree ensembles with linear models and neural networks on tabular data; define the Shapley value and read a SHAP explanation, with its caveats; and estimate heterogeneous treatment effects with causal forests and meta-learners.
A (binary) decision tree is a rooted tree in which each internal node \(v\) carries a split "\(x_{j(v)}\le t_v\)?" on one feature, with one child for "yes" and one for "no", and each leaf \(\ell\) carries a prediction \(c_\ell\). The leaves define regions \(R_\ell\) of feature space (boxes, for numeric features), and the tree is the function
$$f(x)=\sum_{\ell}c_\ell\,\mathbb 1[x\in R_\ell].$$For classification \(c_\ell\) is the majority class in the leaf (or the class proportions); for regression it is the mean response.
Here is a depth-3 tree for the Palmer penguins of Lectures 1 and 3, using their four body measurements.
342 Adélie, Chinstrap and Gentoo penguins with bill length and depth, flipper length and body mass, from the Palmer Station Long Term Ecological Research program, Antarctica, 2007–2009 (Gorman, Williams and Fraser, 2014; palmerpenguins, CC0). Split 70/30, stratified by species, seed 0.
import numpy as np import pandas as pd from palmerpenguins import load_penguins from sklearn.model_selection import train_test_split from sklearn.tree import DecisionTreeClassifier, export_text feats = ['bill_length_mm', 'bill_depth_mm', 'flipper_length_mm', 'body_mass_g'] pen = load_penguins().dropna(subset=feats) Ptr, Pte = train_test_split(pen, test_size=0.3, stratify=pen['species'], random_state=0) tree = DecisionTreeClassifier(max_depth=3, random_state=0).fit(Ptr[feats], Ptr['species']) print(export_text(tree, feature_names=feats, show_weights=True)) print(f'train accuracy {tree.score(Ptr[feats], Ptr["species"]):.3f} test accuracy {tree.score(Pte[feats], Pte["species"]):.3f}' f' leaves {tree.get_n_leaves()}')
|--- flipper_length_mm <= 206.50 | |--- bill_length_mm <= 43.35 | | |--- bill_length_mm <= 42.35 | | | |--- weights: [96.00, 1.00, 0.00] class: Adelie | | |--- bill_length_mm > 42.35 | | | |--- weights: [5.00, 2.00, 0.00] class: Adelie | |--- bill_length_mm > 43.35 | | |--- body_mass_g <= 4175.00 | | | |--- weights: [0.00, 37.00, 0.00] class: Chinstrap | | |--- body_mass_g > 4175.00 | | | |--- weights: [3.00, 2.00, 1.00] class: Adelie |--- flipper_length_mm > 206.50 | |--- bill_depth_mm <= 17.65 | | |--- weights: [0.00, 0.00, 85.00] class: Gentoo | |--- bill_depth_mm > 17.65 | | |--- bill_depth_mm <= 18.95 | | | |--- weights: [2.00, 0.00, 0.00] class: Adelie | | |--- bill_depth_mm > 18.95 | | | |--- weights: [0.00, 5.00, 0.00] class: Chinstrap train accuracy 0.975 test accuracy 0.942 leaves 7
The tree reads like a field guide. Long flippers (over 206.5 mm) and a shallow bill: Gentoo, all 85 of them. Short flippers and a short bill: Adélie. Short flippers, long bill and light body: Chinstrap, all 37. Seven leaves, 97.5% training accuracy and 94.2% on unseen penguins. Each leaf's weights show how pure it is; the leaf with 3 Adélie, 2 Chinstrap and 1 Gentoo is a handful of hard cases.
At depth 1 the tree splits on flipper length at 206.5 mm and gets 79.2% right: it separates Gentoo from the rest but cannot tell Adélie from Chinstrap. Depth 2 adds a bill-length split on each side and jumps to 95.3%. Depth 3 adds three more leaves without changing a single prediction on the training data, because the splits make leaves purer without changing which class is in the majority. By depth 6 the boxes are carving out individual penguins.
Finding the best tree of a given size is NP-hard (Hyafil and Rivest, 1976), so every practical method grows the tree greedily: at each node, try every feature and every threshold between consecutive observed values, keep the split that most reduces impurity, and recurse. This is CART (Breiman, Friedman, Olshen and Stone, 1984).
For a node with class proportions \(p_1,\dots,p_K\) the Gini impurity and entropy are
$$G(p)=1-\sum_kp_k^2=\sum_kp_k(1-p_k),\qquad H(p)=-\sum_kp_k\log_2p_k.$$For regression the impurity is the variance of the responses in the node. A split sending a fraction \(w_L\) of the node's points left (proportions \(p^L\)) and \(w_R=1-w_L\) right (\(p^R\)) has impurity decrease
$$\Delta=I(p)-w_LI(p^L)-w_RI(p^R),\qquad p=w_Lp^L+w_Rp^R.$$Gini impurity is the probability that two penguins drawn at random from the node belong to different species; entropy is the information (in bits) needed to name the species. Both are zero for a pure node and largest when all classes are equally common. Why not just count mistakes? Because the misclassification rate often does not change when a split makes both children purer, as at depth 3 in the widget, and a greedy search guided by it stalls. Gini and entropy are strictly concave, which rewards any split that separates the classes at all.
For any concave impurity \(I\) (Gini, entropy, or variance), every split has \(\Delta\ge0\). For strictly concave \(I\), \(\Delta=0\) only if the two children have the same class proportions.
The parent's proportions are the weighted average \(p=w_Lp^L+w_Rp^R\). Concavity says
$$I(w_Lp^L+w_Rp^R)\ge w_LI(p^L)+w_RI(p^R),$$which is \(\Delta\ge0\), with equality for strictly concave \(I\) only when \(p^L=p^R\) (or one weight is 0).
For regression, the variance of the parent equals the weighted within-child variance plus the weighted between-child variance of the child means (the law of total variance), so \(\Delta\) is the between-child part, which is \(\ge0\). \(\square\)
A node contains 40 Adélie and 10 Chinstrap penguins. What is its Gini impurity?
A tree grown until every leaf is pure has zero training error and high variance. The classical fix is to grow a large tree and then prune it back.
For a tree \(T\) with \(|T|\) leaves and training loss \(R(T)\), and a penalty \(\alpha\ge0\), the cost-complexity is
$$R_\alpha(T)=R(T)+\alpha|T|.$$For each \(\alpha\), the subtree of the full tree minimising \(R_\alpha\) is unique and can be found by repeatedly collapsing the "weakest link", the internal node whose removal increases \(R\) least per leaf removed. As \(\alpha\) grows these subtrees are nested, and \(\alpha\) is chosen by cross-validation.
This is the lasso idea of Lecture 3 applied to tree size: a penalty per leaf, a path of solutions, and cross-validation to pick a point on the path. In practice, simpler limits (maximum depth, minimum leaf size) chosen by cross-validation work about as well, and ensembles make pruning largely unnecessary.
What is the largest number of leaves a binary tree of depth 5 can have?
Trees have low bias: deep enough, they can approximate any function. Their weakness is variance. Because each split depends on the ones above it, a small change in the data can change the root split, and with it everything below. Let us resample the training penguins with replacement (the bootstrap) and grow a tree on each resample.
from sklearn.ensemble import RandomForestClassifier rng = np.random.default_rng(0) preds = [] print('bootstrap root split test accuracy') for b in range(8): idx = rng.integers(0, len(Ptr), len(Ptr)) # resample the training penguins with replacement t = DecisionTreeClassifier(max_depth=3, random_state=0).fit(Ptr[feats].iloc[idx], Ptr['species'].iloc[idx]) f, thr = t.tree_.feature[0], t.tree_.threshold[0] preds.append(t.predict(Pte[feats])) print(f'{b:9d} {feats[f]:>18s} <= {thr:8.2f} {np.mean(preds[-1] == Pte["species"]):13.3f}') P = np.array(preds) disagree = np.mean([np.mean(P[i] != P[j]) for i in range(8) for j in range(i + 1, 8)]) print(f'two bootstrap trees disagree on {disagree:.1%} of test penguins on average') rf = RandomForestClassifier(500, random_state=0).fit(Ptr[feats], Ptr['species']) print(f'random forest of 500 trees: test accuracy {rf.score(Pte[feats], Pte["species"]):.3f}')
bootstrap root split test accuracy
0 bill_length_mm <= 42.40 0.932
1 bill_length_mm <= 43.25 0.971
2 bill_depth_mm <= 16.55 0.883
3 flipper_length_mm <= 207.00 0.971
4 flipper_length_mm <= 207.50 0.932
5 flipper_length_mm <= 206.50 0.922
6 flipper_length_mm <= 206.50 0.942
7 bill_length_mm <= 42.55 0.942
two bootstrap trees disagree on 7.3% of test penguins on average
random forest of 500 trees: test accuracy 0.990
Eight resamples of the same 239 penguins give three different root questions (flipper length, bill length or bill depth) and test accuracies from 88.3% to 97.1%. Two such trees disagree on 7.3% of new penguins. An analyst who reported "the" tree and its story would be reporting one draw from this lottery. A forest of 500 trees, built in the next section, gets 99.0%.
Averaging reduces variance. If we had many independent training sets we could grow a tree on each and average the predictions; the bootstrap fakes those training sets from the one we have. This is bagging, for bootstrap aggregating (Breiman, 1996): grow \(B\) deep trees on bootstrap resamples and average their predictions (or take a vote). But trees grown on resamples of the same data are not independent. How much does that matter?
Let \(T_1,\dots,T_B\) be identically distributed with variance \(\sigma^2\) and pairwise correlation \(\rho\ge0\). Then
$$\operatorname{Var}\Big(\frac1B\sum_{b=1}^BT_b\Big)=\rho\sigma^2+\frac{1-\rho}B\sigma^2.$$Divide by \(B^2\):
$$\frac{\sigma^2}B+\frac{B-1}B\rho\sigma^2=\rho\sigma^2+\frac{1-\rho}B\sigma^2.\qquad\square$$As \(B\to\infty\) the second term vanishes but the first does not: correlation sets a floor \(\rho\sigma^2\) that more trees cannot break. Breiman's random forest (2001) lowers \(\rho\) directly: at each split, only a random subset of the features (often a third of them for regression, \(\sqrt p\) for classification) is eligible. A dominant feature can then not appear at the top of every tree, the trees become more different, and their average is more stable, even though each individual tree gets slightly worse. We can check the formula on the California housing data of Lecture 3 by growing forests on 30 independent training sets.
20,433 California census block groups (after dropping 207 with missing bedroom counts) with median income, house age, rooms and bedrooms per household, population, occupancy, latitude and longitude; the response is median house value in units of $100,000, capped at $500,001 (Pace and Barry, 1997; Géron's copy, as in Lecture 3). Lecture 3's 80/20 split, seed 0.
import time raw = pd.read_csv('data/housing.csv').dropna() # the California housing data of Lecture 3 cal = pd.DataFrame({'MedInc': raw.median_income, 'HouseAge': raw.housing_median_age, 'AveRooms': raw.total_rooms / raw.households, 'AveBedrms': raw.total_bedrooms / raw.households, 'Population': raw.population, 'AveOccup': raw.population / raw.households, 'Latitude': raw.latitude, 'Longitude': raw.longitude, 'Value': raw.median_house_value / 1e5}) hf = list(cal.columns[:-1]) tr, te = train_test_split(cal, test_size=0.2, random_state=0) # Lecture 3's split Xtr, Xte, ytr, yte = tr[hf], te[hf], tr['Value'].to_numpy(), te['Value'].to_numpy() # Why forests decorrelate: 30 disjoint training sets of 500 districts, a forest of 50 trees on each from sklearn.ensemble import RandomForestRegressor R, m, B = 30, 500, 50 Xq = Xte.iloc[:300].to_numpy() # 300 fixed test districts for mf in [1.0, 0.33]: T = np.empty((R, B, len(Xq))) for r in range(R): sl = slice(r * m, (r + 1) * m) f = RandomForestRegressor(B, max_features=mf, random_state=r).fit(Xtr.iloc[sl], ytr[sl]) T[r] = np.array([e.predict(Xq) for e in f.estimators_]) s2 = T.reshape(-1, len(Xq)).var(axis=0) # variance of one tree over training sets and bootstraps D = T - T.mean(axis=(0, 1)) S = D.sum(axis=1) cov = ((S**2 - (D**2).sum(axis=1)) / (B * (B - 1))).mean(axis=0) # covariance of two trees grown on the same data rho = cov.mean() / s2.mean() print(f'max_features {mf}: single-tree variance {s2.mean():.4f}, correlation between trees rho = {rho:.3f}') for b in [1, 5, 50]: obs = T[:, :b].mean(axis=1).var(axis=0).mean() # variance of a forest of b trees print(f' {b:2d} trees: observed variance {obs:.4f} formula rho s2 + (1 - rho) s2 / B = {rho * s2.mean() + (1 - rho) * s2.mean() / b:.4f}')
max_features 1.0: single-tree variance 0.5221, correlation between trees rho = 0.112
1 trees: observed variance 0.4779 formula rho s2 + (1 - rho) s2 / B = 0.5221
5 trees: observed variance 0.1423 formula rho s2 + (1 - rho) s2 / B = 0.1513
50 trees: observed variance 0.0679 formula rho s2 + (1 - rho) s2 / B = 0.0679
max_features 0.33: single-tree variance 0.6740, correlation between trees rho = 0.044
1 trees: observed variance 0.6484 formula rho s2 + (1 - rho) s2 / B = 0.6740
5 trees: observed variance 0.1546 formula rho s2 + (1 - rho) s2 / B = 0.1584
50 trees: observed variance 0.0424 formula rho s2 + (1 - rho) s2 / B = 0.0424
With all features available at every split (bagging), a single tree's variance is 0.52 and two trees grown on the same data have correlation 0.11, so no forest can push the variance below about 0.058. Restricting each split to a third of the features makes each tree more variable (0.67) but cuts the correlation to 0.044, and the 50-tree forest's variance falls from 0.068 to 0.042. The formula tracks the measured variances at 5 and 50 trees.
Trees have variance \(\sigma^2=0.5\) and pairwise correlation \(\rho=0.1\). What is the variance of an average of 50 of them? (Three decimal places.)
One tree draws a jagged map full of islands, different with every resample. A hundred trees blur it into a smooth boundary with a wide band of uncertainty where the species overlap. On these penguins a 100-tree forest gets 74–76% of the 66 test penguins right, depending on the resamples, against 67–68% for the average single tree.
Bagging gives a free validation set. Each bootstrap resample leaves out about \(e^{-1}\approx37\%\) of the training points (Exercise 3), and each point can be predicted by the trees that did not see it. This out-of-bag error estimates test error without a separate holdout: for the California forest below it is 0.489, against a test RMSE of 0.491.
Forests also rank features. The default "impurity importance" adds up each feature's impurity decreases across all splits; "permutation importance" shuffles one feature in held-out data and measures how much worse the predictions get. They can disagree, and the first has a known bias (Strobl et al., 2007): features with many distinct values offer many candidate thresholds, and some split looks good by chance.
from sklearn.inspection import permutation_importance Xn_tr, Xn_te = Xtr.copy(), Xte.copy() rng = np.random.default_rng(0) Xn_tr['Noise'] = rng.standard_normal(len(Xn_tr)) # a feature that is pure noise Xn_te['Noise'] = rng.standard_normal(len(Xn_te)) rfn = RandomForestRegressor(200, max_features=0.33, min_samples_leaf=1, n_jobs=2, random_state=0).fit(Xn_tr, ytr) perm = permutation_importance(rfn, Xn_te, yte, n_repeats=5, random_state=0) imp = pd.DataFrame({'impurity': rfn.feature_importances_, 'permutation (test)': perm.importances_mean}, index=Xn_tr.columns).sort_values('impurity', ascending=False) print(imp.round(4).to_string())
impurity permutation (test) MedInc 0.3353 0.5024 Latitude 0.1387 0.3210 Longitude 0.1320 0.2511 AveOccup 0.1192 0.1561 AveRooms 0.1159 0.0647 HouseAge 0.0557 0.0468 AveBedrms 0.0437 0.0106 Population 0.0346 0.0076 Noise 0.0249 0.0009
A column of random numbers, unrelated to house values, receives 2.5% of the total impurity importance, about as much as Population, because deep trees split on it to separate a few points. Its permutation importance is essentially zero. Impurity importance also flatters Population and AveBedrms, which matter little for test predictions. Permutation importance on held-out data is the safer default, though it too misleads when features are strongly correlated (shuffling one creates impossible combinations).
Suppose
$$Y=\sum_jm_j(X_j)+\varepsilon$$with continuous component functions and \(X\) uniform on \([0,1]^p\).
Breiman's random forest, with trees grown on subsamples of size \(a_n\) to \(t_n\) leaves, is consistent (its mean squared error tends to the noise level) provided \(a_n\to\infty\), \(t_n\to\infty\) and
$$t_n(\log a_n)^9/a_n\to0$$(Scornet, Biau and Vert, 2015).
The conditions are technical and the additive model is restrictive, but the result was the first to prove consistency for the algorithm people actually use, with data-dependent splits. Proving things about greedy, data-dependent partitions is hard, which is why forest theory lagged forest practice by fifteen years.
Why can restricting each split to a random subset of features make a forest more accurate, even though each tree gets worse?
Forests average strong, deep, noisy trees. Boosting does the opposite: it combines many weak learners, each only slightly better than guessing, built in sequence so that each concentrates on the examples its predecessors got wrong. Kearns and Valiant asked in 1988 whether weak learnability implies strong learnability; Schapire (1990) proved it does, and Freund and Schapire's AdaBoost (1997) made it practical.
With labels \(y_i\in\{\pm1\}\), start with weights \(w_i=1/n\). For \(t=1,\dots,T\):
The final classifier is \(\operatorname{sign}F_T(x)\) with
$$F_T=\sum_t\alpha_th_t.$$The training error of AdaBoost after \(T\) rounds satisfies
$$\frac1n\sum_i\mathbb 1[\operatorname{sign}F_T(x_i)\ne y_i]\ \le\ \prod_{t=1}^T2\sqrt{\varepsilon_t(1-\varepsilon_t)}\ \le\ \exp\Big(-2\sum_{t=1}^T\gamma_t^2\Big),\qquad\gamma_t=\tfrac12-\varepsilon_t.$$So if every weak learner beats guessing by a margin \(\gamma_t\ge\gamma>0\), the training error falls below \(e^{-2\gamma^2T}\).
Let
$$Z_t=\sum_iw_ie^{-\alpha_ty_ih_t(x_i)}$$be the normaliser in round \(t\). Unrolling the updates, the final weights are
$$w_i^{(T+1)}=\frac1n e^{-y_iF_T(x_i)}/\prod_tZ_t,$$and they sum to 1, so
$$\frac1n\sum_ie^{-y_iF_T(x_i)}=\prod_tZ_t.$$A mistake has \(y_iF_T(x_i)\le0\), so \(\mathbb 1[\text{mistake}]\le e^{-y_iF_T(x_i)}\), and the training error is at most \(\prod_tZ_t\).
Now
$$Z_t=(1-\varepsilon_t)e^{-\alpha_t}+\varepsilon_te^{\alpha_t},$$which \(\alpha_t=\frac12\log\frac{1-\varepsilon_t}{\varepsilon_t}\) minimises, giving
$$Z_t=2\sqrt{\varepsilon_t(1-\varepsilon_t)}=\sqrt{1-4\gamma_t^2}\le e^{-2\gamma_t^2},$$using \(1-u\le e^{-u}\). \(\square\)
The proof contains a second result. AdaBoost is minimising \(\frac1n\sum_ie^{-y_iF(x_i)}\), the exponential loss of Lecture 5, one weak learner at a time.
Given \(F_{t-1}\), the pair \((\alpha,h)\) minimising
$$\sum_ie^{-y_i(F_{t-1}(x_i)+\alpha h(x_i))}$$is AdaBoost's \(h_t\) (minimising weighted error with weights \(\propto e^{-y_iF_{t-1}(x_i)}\)) and \(\alpha_t\) (Friedman, Hastie and Tibshirani, 2000).
Write \(w_i\propto e^{-y_iF_{t-1}(x_i)}\), exactly AdaBoost's weights. The objective is proportional to
$$\sum_iw_ie^{-\alpha y_ih(x_i)}=e^{-\alpha}\sum_{\text{correct}}w_i+e^{\alpha}\sum_{\text{wrong}}w_i=e^{-\alpha}+(e^\alpha-e^{-\alpha})\varepsilon(h).$$For any \(\alpha>0\) this is increasing in the weighted error \(\varepsilon(h)\), so the best \(h\) minimises weighted error.
Then minimising \((1-\varepsilon)e^{-\alpha}+\varepsilon e^\alpha\) over \(\alpha\) gives
$$\alpha=\frac12\log\frac{1-\varepsilon}\varepsilon.\qquad\square$$Since the population minimiser of exponential loss is \(F^*(x)=\frac12\log\frac{P(Y=1\mid x)}{P(Y=-1\mid x)}\) (Lecture 5), AdaBoost's score estimates half the log-odds. Here it is from scratch, with decision stumps (depth-1 trees) on the breast-cancer data.
from sklearn.datasets import load_breast_cancer bc = load_breast_cancer() Xb_tr, Xb_te, yb_tr, yb_te = train_test_split(bc.data, 1 - bc.target, test_size=0.3, stratify=1 - bc.target, random_state=0) t_tr, t_te = 2 * yb_tr - 1, 2 * yb_te - 1 # labels as +-1 def best_stump(X, t, w): """Weighted-error-minimising stump: predict s if x_f > thr, else -s.""" best = (np.inf, None) for f in range(X.shape[1]): order = np.argsort(X[:, f]); xs, ts, ws = X[order, f], t[order], w[order] # error of predicting +1 above the cut = weight of -1 above + weight of +1 at or below above_neg = np.cumsum((ws * (ts < 0))[::-1])[::-1] below_pos = np.cumsum(ws * (ts > 0)) err = np.concatenate([[above_neg[0]], below_pos + np.append(above_neg[1:], 0)]) for s, e in [(1, err), (-1, 1 - err)]: k = e.argmin() if e[k] < best[0]: thr = -np.inf if k == 0 else (xs[k - 1] + xs[k]) / 2 if k < len(xs) else np.inf best = (e[k], (f, thr, s)) return best w = np.full(len(t_tr), 1 / len(t_tr)); F_tr = np.zeros(len(t_tr)); F_te = np.zeros(len(t_te)); bound = 1.0 print('round weighted error eps_t train error bound prod 2 sqrt(eps(1-eps)) test error') for t in range(1, 201): eps, (f, thr, s) = best_stump(Xb_tr, t_tr, w) a = 0.5 * np.log((1 - eps) / eps) # the AdaBoost weight of this stump h_tr = s * np.where(Xb_tr[:, f] > thr, 1, -1); h_te = s * np.where(Xb_te[:, f] > thr, 1, -1) F_tr += a * h_tr; F_te += a * h_te w = w * np.exp(-a * t_tr * h_tr); w /= w.sum() # up-weight the mistakes bound *= 2 * np.sqrt(eps * (1 - eps)) if t in [1, 2, 5, 10, 20, 50, 100, 200]: print(f'{t:5d} {eps:20.4f} {np.mean(np.sign(F_tr) != t_tr):11.4f} {bound:29.4f} {np.mean(np.sign(F_te) != t_te):10.4f}')
round weighted error eps_t train error bound prod 2 sqrt(eps(1-eps)) test error
1 0.0653 0.0653 0.4942 0.1404
2 0.1132 0.0653 0.3132 0.1404
5 0.1813 0.0226 0.1400 0.0819
10 0.2985 0.0151 0.0886 0.0760
20 0.3194 0.0025 0.0354 0.0760
50 0.2995 0.0000 0.0048 0.0526
100 0.3290 0.0000 0.0002 0.0468
200 0.3162 0.0000 0.0000 0.0409
The first stump alone has 6.5% training error. The weighted errors \(\varepsilon_t\) rise toward 0.3 as AdaBoost concentrates on harder and harder cases, but the bound still collapses and the training error reaches zero by round 50. The striking column is the last one: test error keeps falling after training error hits zero, from 5.3% at round 50 to 4.1% at round 200. A theory that only counts training mistakes cannot explain this; the margin bound of Lecture 6 can. Continued boosting keeps widening the margins \(y_iF(x_i)/\sum_t\alpha_t\), and wider margins mean a smaller generalisation bound (Schapire et al., 1998).
A weak learner has weighted error \(\varepsilon_t=0.25\). What weight \(\alpha_t\) does AdaBoost give it? (Four decimal places.)
The first regression tree program, AID ("automatic interaction detection"), was written by James Morgan and John Sonquist at the University of Michigan's Survey Research Center in 1963 to find interactions in survey data. Leo Breiman, Jerome Friedman, Richard Olshen and Charles Stone's book Classification and Regression Trees (1984) gave the method its statistical foundations, while Ross Quinlan developed ID3 (1986) and C4.5 (1993) in machine learning. Robert Schapire's 1990 paper "The strength of weak learnability" answered a theoretical question of Kearns and Valiant and led to AdaBoost; Yoav Freund and Schapire won the 2003 Gödel Prize for it. Breiman introduced bagging in 1996 and random forests in 2001, building on Tin Kam Ho's random decision forests (1995). Friedman's gradient boosting machine (2001) recast boosting as optimisation. Tianqi Chen's XGBoost, released in 2014 and published with Carlos Guestrin in 2016, won so many data-science competitions that 17 of the 29 winning Kaggle solutions in 2015 used it.
Theorem 8.5 suggests a generalisation. AdaBoost adds the learner that most reduces exponential loss; why not any loss? Friedman (2001) saw that adding a small function \(h\) to the current model \(F\) is a step in function space, and the steepest step is in the direction of the negative gradient of the loss with respect to the predictions. We cannot add an arbitrary vector of values at the training points (that would not generalise), but we can fit a small tree to that vector and add the tree.
Given a differentiable loss \(\ell(y,F)\), a learning rate \(\nu\in(0,1]\) and a tree size:
For squared loss \(\frac12(y-F)^2\), the pseudo-residuals are the ordinary residuals \(y-F\): each tree fits what the model so far gets wrong. For absolute loss they are the signs of the residuals and the leaf values are medians; for log loss with \(p=\sigma(F)\) they are \(y-p\), label minus prediction, the negative of the gradient of Lecture 4. Every loss of Lecture 5 now has a boosting algorithm, including quantile and Poisson losses. The learning rate \(\nu\) (shrinkage) takes only part of each step; smaller steps need more trees but generalise better, the same trade-off as gradient descent with a small step and early stopping (Lecture 2).
Stumps are as weak as learners get, yet their sum builds the sharp dip and rebound of the crash curve. With \(\nu=0.1\), 50 rounds give a test RMSE of 30.9 and 200 rounds 25.1. With \(\nu=1\) the fit races ahead and then chases noise: its test error is lowest after 70 rounds and rises afterwards. The same happens on California housing with depth-3 trees.
# Gradient boosting from scratch for squared loss: each tree fits the current residuals (the negative gradient) from sklearn.tree import DecisionTreeRegressor from sklearn.ensemble import GradientBoostingRegressor rmse = lambda p: np.sqrt(np.mean((p - yte) ** 2)) def boost(X, y, Xtest, n_trees, lr, depth=3, loss='squared'): F, Ft = np.full(len(y), y.mean() if loss == 'squared' else np.median(y)), None Ft = np.full(len(Xtest), F[0]); hist = [] for m in range(n_trees): g = y - F if loss == 'squared' else np.sign(y - F) # negative gradient of the loss tree = DecisionTreeRegressor(max_depth=depth, random_state=0).fit(X, g) if loss == 'absolute': # best constant per leaf for absolute loss: a median leaf = tree.apply(X) for l in np.unique(leaf): tree.tree_.value[l, 0, 0] = np.median((y - F)[leaf == l]) F = F + lr * tree.predict(X); Ft = Ft + lr * tree.predict(Xtest); hist.append(Ft.copy()) return hist print('rounds lr=1.0 lr=0.3 lr=0.1 (test RMSE, squared loss, depth-3 trees)') H = {lr: boost(Xtr.to_numpy(), ytr, Xte.to_numpy(), 300, lr) for lr in [1.0, 0.3, 0.1]} for m in [1, 10, 30, 100, 300]: print(f'{m:6d} ' + ' '.join(f'{rmse(H[lr][m - 1]):6.4f}' for lr in [1.0, 0.3, 0.1])) sk = GradientBoostingRegressor(n_estimators=300, max_depth=3, learning_rate=0.1, random_state=0).fit(Xtr, ytr) print(f'scikit-learn GradientBoostingRegressor, same settings: {rmse(sk.predict(Xte)):.4f}') Ha = boost(Xtr.to_numpy(), ytr, Xte.to_numpy(), 300, 0.1, loss='absolute') print(f'absolute loss, lr=0.1, 300 rounds: test RMSE {rmse(Ha[-1]):.4f}, test mean absolute error {np.mean(np.abs(Ha[-1] - yte)):.4f}' f' (squared loss: {np.mean(np.abs(H[0.1][-1] - yte)):.4f})')
rounds lr=1.0 lr=0.3 lr=0.1 (test RMSE, squared loss, depth-3 trees)
1 0.7941 0.9875 1.0970
10 0.5816 0.6169 0.8030
30 0.5305 0.5379 0.6227
100 0.5415 0.4986 0.5321
300 0.5634 0.4779 0.4955
scikit-learn GradientBoostingRegressor, same settings: 0.4955
absolute loss, lr=0.1, 300 rounds: test RMSE 0.5224, test mean absolute error 0.3447 (squared loss: 0.3371)
With \(\nu=1\), test error bottoms out near 30 trees and then gets worse; with \(\nu=0.3\) it is still falling at 300; with \(\nu=0.1\) it is slower still but would keep improving. Our twenty lines reproduce scikit-learn's implementation exactly (0.4955). The absolute-loss version, fitting signs and taking leaf medians, is more robust to the capped house values but here does slightly worse even on mean absolute error: a loss that ignores large residuals also learns less from them.
In gradient boosting, the pseudo-residual for absolute loss \(|y-F|\) is , and for log loss with \(p=\sigma(F)\) it is .
Gradient boosting fits each tree to first derivatives and then fixes the leaf values with a separate line search. XGBoost (Chen and Guestrin, 2016) uses second derivatives as well, as Newton's method does (Lecture 2), and adds a penalty on the tree itself. This gives closed-form leaf values and a closed-form score for every candidate split.
At round \(t\) we add a tree \(f\) to the current predictions \(\hat y_i\). The tree is a set of leaves with values \(w_1,\dots,w_T\), and \(q(x)\) is the leaf that \(x\) falls in, so \(f(x)=w_{q(x)}\). The objective is the training loss plus a complexity penalty
$$\sum_i\ell\big(y_i,\hat y_i+f(x_i)\big)+\gamma T+\tfrac12\lambda\sum_{j=1}^Tw_j^2,$$a cost \(\gamma\) per leaf and a ridge penalty \(\lambda\) on the leaf values. Expand the loss to second order around \(\hat y_i\), with \(g_i=\partial\ell/\partial\hat y_i\) and \(h_i=\partial^2\ell/\partial\hat y_i^2\).
Let \(G_j=\sum_{i:q(x_i)=j}g_i\) and \(H_j=\sum_{i:q(x_i)=j}h_i\).
For a fixed tree structure, the second-order objective is minimised by the leaf values
$$w_j^*=-\frac{G_j}{H_j+\lambda},\qquad\text{giving the objective}\qquad-\frac12\sum_{j=1}^T\frac{G_j^2}{H_j+\lambda}+\gamma T.$$Splitting a leaf into left and right children therefore changes the objective by
$$\text{gain}=\frac12\Big[\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\Big]-\gamma,$$and the split is worth making only if the gain is positive.
To second order,
$$\ell(y_i,\hat y_i+f(x_i))\approx\ell(y_i,\hat y_i)+g_if(x_i)+\frac12h_if(x_i)^2.$$Dropping the constant and grouping the points by leaf (all points in leaf \(j\) get \(f=w_j\)), the objective is
$$\sum_{j=1}^T\Big[G_jw_j+\tfrac12(H_j+\lambda)w_j^2\Big]+\gamma T,$$a sum of independent one-variable quadratics. Each is minimised at
$$w_j=-G_j/(H_j+\lambda),$$with value
$$-\frac12G_j^2/(H_j+\lambda).$$The gain compares the objective with one leaf (\(G=G_L+G_R\), \(H=H_L+H_R\)) against two leaves, minus the extra leaf's cost \(\gamma\). \(\square\)
Several things are visible in these formulas. For squared loss, \(g_i=\hat y_i-y_i\) and \(h_i=1\), so \(w_j^*\) is the mean residual in the leaf, shrunk toward zero by \(\lambda\): ridge regression of Lecture 3, one leaf at a time. For log loss, \(g_i=p_i-y_i\) and \(h_i=p_i(1-p_i)\), so a leaf full of confident predictions (small \(h_i\)) gets a larger step, exactly as Newton's method takes larger steps where the curvature is small. And \(H_j\) acts as an effective sample size: XGBoost's min_child_weight is a lower bound on it. Let us check the formulas against XGBoost itself.
# XGBoost's split gain and leaf weights, by hand, for one depth-1 tree on the breast-cancer data import xgboost as xgb lam = 1.0 one = xgb.XGBClassifier(n_estimators=1, max_depth=1, learning_rate=1.0, reg_lambda=lam, gamma=0, min_child_weight=0, base_score=0.5, tree_method='exact').fit(Xb_tr, yb_tr) print(one.get_booster().get_dump(with_stats=True)[0]) p = np.full(len(yb_tr), 0.5) # starting prediction 0.5, i.e. score 0 g, h = p - yb_tr, p * (1 - p) # gradient and Hessian of the log loss in the score import re f, thr = re.search(r'\[f(\d+)<([-\d.e]+)\]', one.get_booster().get_dump()[0]).groups() # the split xgboost chose f, thr = int(f), np.float32(thr) left = Xb_tr[:, f].astype(np.float32) < thr # xgboost compares in single precision G, H_ = g.sum(), h.sum(); GL, HL, GR, HR = g[left].sum(), h[left].sum(), g[~left].sum(), h[~left].sum() print(f'G_L = {GL:.2f}, H_L = {HL:.2f}, G_R = {GR:.2f}, H_R = {HR:.2f}') print(f'leaf weights -G/(H+lambda): left {-GL / (HL + lam):.6f}, right {-GR / (HR + lam):.6f}') score = lambda G, H: G**2 / (H + lam) print(f'gain = G_L^2/(H_L+l) + G_R^2/(H_R+l) - G^2/(H+l) = {score(GL, HL) + score(GR, HR) - score(G, H_):.4f}') print('feature', bc.feature_names[f])
0:[f7<0.0489199981] yes=1,no=2,missing=1,gain=269.583771,cover=99.5 1:leaf=-1.76377952,cover=62.5 2:leaf=1.60526311,cover=37 G_L = 112.00, H_L = 62.50, G_R = -61.00, H_R = 37.00 leaf weights -G/(H+lambda): left -1.763780, right 1.605263 gain = G_L^2/(H_L+l) + G_R^2/(H_R+l) - G^2/(H+l) = 269.5838 feature mean concave points
Starting from \(p=0.5\), every \(h_i=0.25\) and every \(g_i=\pm0.5\). XGBoost splits on mean concave points at 0.0489, and our \(-G/(H+\lambda)\) reproduces its leaf values to all printed digits: \(-112/63.5=-1.7638\) on the benign side, \(61/38=1.6053\) on the malignant side. The "cover" it reports is \(H\). Its reported gain, 269.58, is our bracket without the factor \(\frac12\) and the \(\gamma\), a convention worth knowing when reading XGBoost's output.
A leaf has gradient sum \(G=-4\) and Hessian sum \(H=3\), with \(\lambda=1\). What value does XGBoost give the leaf?
The rest of XGBoost's design is engineering that made the method fast enough to dominate: approximate split finding on quantile sketches of each feature, so only a few hundred candidate thresholds are tried; sparsity-aware splits that learn a default direction for missing values; column subsampling borrowed from random forests; and cache-aware, parallel histogram construction. Two successors are worth knowing. LightGBM (Ke et al., 2017) bins features into histograms, grows trees leaf-wise (always splitting the leaf with the largest gain, rather than level by level), and samples data by gradient size. CatBoost (Prokhorenkova et al., 2018) targets categorical features: it encodes a category by the average target of earlier rows only, in a random order, and boosts with the same "ordered" trick, which prevents the target leakage that naive target encoding causes.
Here is the whole progression on California housing.
from sklearn.model_selection import GridSearchCV from sklearn.tree import DecisionTreeRegressor from sklearn.ensemble import GradientBoostingRegressor import xgboost as xgb, lightgbm as lgb rmse = lambda p: np.sqrt(np.mean((p - yte) ** 2)) rows = [] t0 = time.time(); beta = np.linalg.lstsq(np.column_stack([np.ones(len(Xtr)), Xtr]), ytr, rcond=None)[0] rows.append(('linear regression (Lecture 3)', rmse(np.column_stack([np.ones(len(Xte)), Xte]) @ beta), time.time() - t0)) t0 = time.time(); cvt = GridSearchCV(DecisionTreeRegressor(random_state=0), {'min_samples_leaf': [1, 5, 10, 20, 50, 100]}, cv=5).fit(Xtr, ytr) rows.append((f'one tree (min leaf {cvt.best_params_["min_samples_leaf"]} by CV, {cvt.best_estimator_.get_n_leaves()} leaves)', rmse(cvt.predict(Xte)), time.time() - t0)) t0 = time.time(); rf = RandomForestRegressor(500, max_features=0.33, oob_score=True, n_jobs=2, random_state=0).fit(Xtr, ytr) rows.append(('random forest, 500 trees', rmse(rf.predict(Xte)), time.time() - t0)) t0 = time.time(); gb = GradientBoostingRegressor(n_estimators=500, max_depth=4, learning_rate=0.1, subsample=0.8, random_state=0).fit(Xtr, ytr) rows.append(('gradient boosting (scikit-learn), 500 trees', rmse(gb.predict(Xte)), time.time() - t0)) Xfit, Xval, yfit, yval = train_test_split(Xtr, ytr, test_size=0.15, random_state=1) # validation set for early stopping t0 = time.time() xg = xgb.XGBRegressor(n_estimators=5000, learning_rate=0.03, max_depth=6, subsample=0.8, colsample_bytree=0.8, reg_lambda=1.0, early_stopping_rounds=100, random_state=0).fit(Xfit, yfit, eval_set=[(Xval, yval)], verbose=False) rows.append((f'XGBoost, early stopping at {xg.best_iteration + 1} trees', rmse(xg.predict(Xte)), time.time() - t0)) t0 = time.time() lg = lgb.LGBMRegressor(n_estimators=5000, learning_rate=0.03, num_leaves=63, subsample=0.8, subsample_freq=1, colsample_bytree=0.8, random_state=0, verbose=-1).fit( Xfit, yfit, eval_set=[(Xval, yval)], callbacks=[lgb.early_stopping(100, verbose=False)]) rows.append((f'LightGBM, early stopping at {lg.best_iteration_} trees', rmse(lg.predict(Xte)), time.time() - t0)) print('model test RMSE ($100k) fit time (s)') for name, r, t in rows: print(f'{name:50s} {r:17.4f} {t:12.1f}') print(f'random forest out-of-bag RMSE: {np.sqrt(np.mean((rf.oob_prediction_ - ytr) ** 2)):.4f}')
model test RMSE ($100k) fit time (s) linear regression (Lecture 3) 0.7263 0.0 one tree (min leaf 20 by CV, 634 leaves) 0.6014 2.6 random forest, 500 trees 0.4912 9.2 gradient boosting (scikit-learn), 500 trees 0.4697 18.0 XGBoost, early stopping at 2639 trees 0.4410 4.5 LightGBM, early stopping at 1244 trees 0.4406 2.6 random forest out-of-bag RMSE: 0.4887
Each step helps. One well-pruned tree beats Lecture 3's linear regression (0.60 against 0.73, in $100,000s), mostly because it can carve the map into neighbourhoods by latitude and longitude. A random forest gets 0.49, and its out-of-bag estimate (0.489) predicted that without touching the test set. Boosting does better still, and XGBoost and LightGBM, with a small learning rate and early stopping on a validation set, reach 0.44, an error 39% smaller than the linear model's, in a few seconds.
Deep learning transformed images, sound and text, but on tabular data (rows of mixed numeric and categorical features, as in most of science, medicine and business) gradient-boosted trees remain hard to beat. Grinsztajn, Oyallon and Varoquaux (2022) compared them carefully with neural networks on 45 medium-sized datasets with equal tuning budgets, and found tree ensembles ahead on most. They traced the gap to three properties of tabular data:
The challenger is a different kind of model. TabPFN (Hollmann et al., 2023; 2025) is a transformer trained once, on millions of synthetic datasets drawn from a prior over causal models. Given a new dataset's training rows and a test row as a single input, it outputs a predictive distribution in one forward pass, with no gradient steps on the new data. It is learning to do Bayesian inference: the network approximates the posterior predictive distribution under its synthetic prior. On datasets of up to about 10,000 rows it matches or beats tuned boosted trees in seconds (Hollmann et al., 2025). Whether such "tabular foundation models" will displace trees on larger data is an open question.
We can test the claim on the housing data of Section 7, giving each method only a small random sample of the training districts and scoring all of them on the same 2,000 test districts.
# TabPFN against boosted trees on small samples of the housing data: one forward pass, no training on the new data from tabpfn import TabPFNRegressor W_PFN = 'data/tabpfn/tabpfn-v2-regressor.ckpt' # TabPFN v2 weights (Prior Labs), from the Hugging Face Hub print('training rows random forest XGBoost (early stopping) TabPFN (test RMSE in $100k on the same 2,000 test districts; mean of 3 samples)') test_idx = np.random.default_rng(0).choice(len(Xte), 2000, replace=False); Xs_te, ys_te = Xte.iloc[test_idx].to_numpy(), yte[test_idx] r2 = lambda p: np.sqrt(np.mean((p - ys_te) ** 2)); T_pfn = [] for n in [100, 500, 2000]: res = [] for seed in range(3): i = np.random.default_rng(seed).choice(len(Xtr), n, replace=False); Xn, yn = Xtr.iloc[i].to_numpy(), ytr[i] f_ = RandomForestRegressor(500, max_features=0.33, n_jobs=2, random_state=0).fit(Xn, yn) a_, b_, ya_, yb_ = train_test_split(Xn, yn, test_size=0.2, random_state=seed) g_ = xgb.XGBRegressor(n_estimators=3000, learning_rate=0.03, max_depth=4, subsample=0.8, early_stopping_rounds=100, random_state=0).fit(a_, ya_, eval_set=[(b_, yb_)], verbose=False) t0 = time.time(); p_ = TabPFNRegressor(device='cpu', random_state=0, model_path=W_PFN, ignore_pretraining_limits=True).fit(Xn, yn).predict(Xs_te); T_pfn.append(time.time() - t0) res.append((r2(f_.predict(Xs_te)), r2(g_.predict(Xs_te)), r2(p_))) m = np.mean(res, 0); print(f"{n:13,d} {m[0]:15.3f} {m[1]:26.3f} {m[2]:9.3f}") print(f"for reference, XGBoost on the full training set of {len(Xtr):,} districts (Section 7): {r2(xg.predict(Xs_te)):.3f}; " f"TabPFN took {np.mean(T_pfn):.0f} s per fit-and-predict on two CPU cores")
training rows random forest XGBoost (early stopping) TabPFN (test RMSE in $100k on the same 2,000 test districts; mean of 3 samples)
100 0.834 0.834 0.677
500 0.647 0.613 0.559
2,000 0.572 0.540 0.492
for reference, XGBoost on the full training set of 16,346 districts (Section 7): 0.434; TabPFN took 45 s per fit-and-predict on two CPU cores
TabPFN is the most accurate of the three at every sample size here: with 100 districts its error is 0.677 against 0.834 for the forest and 0.834 for XGBoost, and with 2,000 it is 0.492 against 0.572 and 0.540, without tuning and without a single gradient step on these data. XGBoost trained on the full training set of 16,346 districts (85% to fit, 15% for early stopping) still does better (0.434): TabPFN's advantage is for small tables, as its authors say. The price is computation at prediction time, 45 seconds per fit-and-predict on our two CPU cores, against a second or two at most for the trees (not timed here).
Gradient-boosted trees are the workhorse of tabular machine learning in industry: credit scoring, fraud detection, insurance pricing, demand forecasting and click prediction all run on XGBoost, LightGBM or CatBoost. Search engines rank results with LambdaMART, gradient-boosted trees trained on a pairwise ranking loss. Random forests remain standard in genomics and ecology, where species-distribution models predict where a species can live from climate layers. Regulated industries pair boosted models with SHAP explanations (Section 9) to meet requirements that individual decisions, such as a declined loan, be explainable. And one tree is still the method of choice when a human must apply the rule by hand: clinical decision rules and triage protocols are short decision trees.
A boosted model with hundreds of trees is accurate and unreadable. For one prediction (this applicant, this patient), how much did each feature push the prediction up or down? Lloyd Shapley answered the corresponding question in cooperative game theory in 1953: how to divide a coalition's payoff fairly among its players. Here the "players" are features and the "payoff" is the prediction.
Let \(N=\{1,\dots,p\}\) and \(v\) assign a value \(v(S)\) to every coalition \(S\subseteq N\). The Shapley value of player \(j\) is its marginal contribution averaged over all orders in which players could join:
$$\phi_j=\sum_{S\subseteq N\setminus\{j\}}\frac{|S|!\,(p-|S|-1)!}{p!}\Big[v(S\cup\{j\})-v(S)\Big].$$In SHAP (Lundberg and Lee, 2017), \(v(S)\) is the model's expected prediction when only the features in \(S\) are known:
$$v(S)=\mathbb E[f(X)\mid X_S=x_S],$$or the "interventional" version that averages \(f(x_S,X_{\bar S})\) over the data distribution of the other features.
The Shapley value is the only way to divide \(v(N)-v(\emptyset)\) among the players that satisfies:
(Shapley, 1953).
The Shapley formula satisfies all four (efficiency because, in each ordering, the marginal contributions telescope to \(v(N)-v(\emptyset)\)).
For uniqueness, every game is a linear combination of "unanimity games"
$$u_T(S)=\mathbb 1[T\subseteq S],$$one for each non-empty \(T\). In \(u_T\), players outside \(T\) are dummies (share 0) and players in \(T\) are symmetric, so efficiency forces each to get \(1/|T|\). Additivity (and the scaling it implies) then fixes the shares for every game. \(\square\)
Efficiency is what makes a SHAP explanation readable: the contributions add up exactly to the difference between this prediction and the average prediction. Computing the Shapley value naively needs all \(2^p\) coalitions, but for tree ensembles Lundberg et al. (2020) found an exact algorithm, TreeSHAP, polynomial in the number of trees, leaves and depth, by pushing all coalitions through each tree at once. XGBoost has it built in.
195,665 working adults in California from the US Census Bureau's 2018 American Community Survey, in the "ACSIncome" task of Folktables (Ding, Hardt, Miller and Schmidt, 2021): age, class of worker, educational attainment, marital status, occupation (about 500 codes), place of birth, relationship to the householder, usual hours worked per week, sex and race; the label is whether annual income exceeds $50,000 (41.1% do). Folktables keeps people over 16 who worked at least an hour a week and earned more than $100. It was built to replace the 1994 "Adult" extract, long the standard example for this task, which is small, old and tied to an income threshold in 1994 dollars; Lecture 13 audits this model. Split 70/30, stratified, seed 0; the code reads the California person file that folktables.ACSDataSource downloads.
import re from sklearn.metrics import roc_auc_score from sklearn.linear_model import LogisticRegression from folktables import ACSIncome # California's 2018 ACS person file, downloaded with folktables.ACSDataSource acs = pd.read_csv('data/acs/2018/1-Year/psam_p06.csv', usecols=ACSIncome.features + ['PINCP', 'PWGTP']) Xa, ya, _ = ACSIncome.df_to_pandas(acs) # people older than 16, working at least 1 hour a week, income over $100 ad = Xa.copy(); ad['y'] = ya.iloc[:, 0].astype(int).values names = {'AGEP': 'age', 'COW': 'class of worker', 'SCHL': 'education', 'MAR': 'marital status', 'OCCP': 'occupation', 'POBP': 'place of birth', 'RELP': 'relationship', 'WKHP': 'hours per week', 'SEX': 'sex', 'RAC1P': 'race'} dic = pd.read_csv('data/PUMS_Data_Dictionary_2018.csv', header=None, names=range(7), dtype=str) lab = {(r[1], int(r[4])): r[6] for r in dic[dic[0] == 'VAL'].itertuples(index=False) if r[1] in names and r[4].strip().isdigit()} cat = ['COW', 'MAR', 'OCCP', 'POBP', 'RELP', 'SEX', 'RAC1P'] # unordered codes; age, education level and hours stay numeric for c in cat: ad[c] = ad[c].astype(int).astype('category') use = list(names) print(f'{len(ad):,} working adults in California (ACS 2018), {ad.y.mean():.1%} earn over $50,000') Atr, Ate = train_test_split(ad, test_size=0.3, stratify=ad['y'], random_state=0) Afit, Aval = train_test_split(Atr, test_size=0.15, stratify=Atr['y'], random_state=1) xa = xgb.XGBClassifier(n_estimators=3000, learning_rate=0.05, max_depth=6, subsample=0.8, colsample_bytree=0.8, max_cat_to_onehot=1, enable_categorical=True, tree_method='hist', early_stopping_rounds=100, random_state=0 ).fit(Afit[use], Afit['y'], eval_set=[(Aval[use], Aval['y'])], verbose=False) pa = xa.predict_proba(Ate[use])[:, 1] print(f'XGBoost ({xa.best_iteration + 1} trees): test accuracy {np.mean((pa > 0.5) == Ate.y):.4f}, AUC {roc_auc_score(Ate.y, pa):.4f}') from sklearn.compose import make_column_transformer from sklearn.preprocessing import OneHotEncoder, StandardScaler from sklearn.pipeline import make_pipeline enc_a = make_column_transformer((OneHotEncoder(handle_unknown='ignore'), cat), (StandardScaler(), ['AGEP', 'SCHL', 'WKHP'])) lr_a = make_pipeline(enc_a, LogisticRegression(C=1.0, max_iter=5000)).fit(Atr[use], Atr.y) # sparse one-hot columns pl = lr_a.predict_proba(Ate[use])[:, 1]; ncol = len(enc_a.get_feature_names_out()) print(f'logistic regression (one-hot, {ncol} columns): test accuracy {np.mean((pl > 0.5) == Ate.y):.4f}, AUC {roc_auc_score(Ate.y, pl):.4f}') # TreeSHAP, built into XGBoost: one contribution per feature plus a base value, summing to the log-odds S = Ate.sample(10_000, random_state=0); dte = xgb.DMatrix(S[use], enable_categorical=True) phi = xa.get_booster().predict(dte, pred_contribs=True, iteration_range=(0, xa.best_iteration + 1)) margin = xa.get_booster().predict(dte, output_margin=True, iteration_range=(0, xa.best_iteration + 1)) print(f'max |sum of contributions - log-odds| = {np.abs(phi.sum(1) - margin).max():.2e}; base value {phi[0, -1]:.4f}') glob = pd.Series(np.abs(phi[:, :-1]).mean(0), index=[names[c] for c in use]).sort_values(ascending=False) print('mean |SHAP value| (log-odds), 10,000 test people:'); print(glob.round(4).to_string()) ps = xa.predict_proba(S[use])[:, 1]; i = int(np.argmin(np.abs(ps - 0.62))) # one person whose predicted probability is near 0.62 show = lambda c, v: re.sub(r'^[A-Z]{3}-', '', lab.get((c, int(v)), str(int(v))))[:44] if c in cat or c == 'SCHL' else str(int(v)) # 'EAT-Chefs' -> 'Chefs' print(f'\none person: predicted P(>$50K) = {ps[i]:.3f}') print(pd.DataFrame({'value': [show(c, S[c].iloc[i]) for c in use], 'SHAP': phi[i, :-1].round(3)}, index=[names[c] for c in use]) .sort_values('SHAP', key=abs, ascending=False).head(6).to_string())
195,665 working adults in California (ACS 2018), 41.1% earn over $50,000
XGBoost (182 trees): test accuracy 0.8270, AUC 0.9070
logistic regression (one-hot, 792 columns): test accuracy 0.8173, AUC 0.8947
max |sum of contributions - log-odds| = 3.81e-06; base value -0.3695
mean |SHAP value| (log-odds), 10,000 test people:
occupation 0.9260
hours per week 0.6155
age 0.5149
education 0.4995
relationship 0.3622
sex 0.1816
place of birth 0.1770
class of worker 0.0899
marital status 0.0699
race 0.0366
one person: predicted P(>$50K) = 0.620
value SHAP
hours per week 60 0.993
occupation Chefs And Head Cooks -0.982
age 61 0.386
relationship Reference person 0.314
education 1 or more years of college credit, no degree -0.278
sex Male 0.261
XGBoost gets 82.7% accuracy and AUC 0.907 with 182 trees, against 81.7% and 0.895 for logistic regression on 792 one-hot and standardised columns. The contributions add up to the model's log-odds to within \(10^{-5}\), as efficiency promises. Averaged over people, occupation matters most, then hours per week, age and education; sex comes sixth and race last. For the person shown, working 60 hours a week adds 1.0 to the log-odds and the occupation (chefs and head cooks) subtracts 1.0; being 61 adds 0.39.
Read these charts with three cautions. First, SHAP explains the model, not the world: the occupation subtracts 0.98 for the person above because few chefs and head cooks in the training data earned over $50,000, not because a change of job would raise this person's pay by a predictable amount. Second, with correlated features the attribution depends on the choice of \(v(S)\): conditional and interventional SHAP can differ substantially, and neither is "the" importance. Third, a small contribution for race or sex does not show a model is fair; those features' information can arrive through correlated ones (occupation, hours worked). Lecture 13 takes this up.
A model's average prediction (log−odds) is −0.37 and its prediction for one person is −1.53. What must that person's SHAP values sum to?
Bayesian additive regression trees (Chipman, George and McCulloch, 2010) write \(f\) as a sum of \(m\) small trees (typically 200), put a prior on each tree that strongly prefers shallow trees and small leaf values, and sample from the posterior by MCMC, updating one tree at a time against the residuals of the others ("Bayesian backfitting"). The result is a boosted-tree ensemble with posterior uncertainty for every prediction and little tuning. BART has become a standard tool for estimating treatment effects from observational data (Hill, 2011), and BART-based methods have done well in causal-inference competitions. TabPFN (Section 8) is the opposite trade: instead of sampling a posterior for each new dataset, it amortises Bayesian inference, paying once to train a network that maps datasets to posterior predictive distributions.
Lecture 3's and Lecture 4's causal estimates were averages: the average effect of a training programme. Often the question is who benefits. The conditional average treatment effect is
$$\tau(x)=\mathbb E\big[Y(1)-Y(0)\mid X=x\big],$$the average effect among units with features \(x\). Two families of tree methods estimate it. Meta-learners (Künzel et al., 2019) reuse any regression method: the T-learner fits one model to the treated and one to the controls and subtracts their predictions; the X-learner refines this by regressing imputed individual effects. Causal forests (Wager and Athey, 2018; Athey, Tibshirani and Wager, 2019) change the trees themselves. Each split is chosen to make the treatment effect differ between the two children, rather than the outcome; and each tree is honest: it uses one half of its subsample to choose the splits and the other half to estimate the effect in each leaf, so the same data never both find a pattern and confirm it.
Under unconfoundedness, overlap, Lipschitz continuity of the outcome functions and suitable conditions on the subsample size and leaf sizes, the honest causal forest estimate \(\hat\tau(x)\) satisfies
$$(\hat\tau(x)-\tau(x))/\sqrt{\operatorname{Var}\hat\tau(x)}\to\mathcal N(0,1),$$and the variance can be estimated consistently by the infinitesimal jackknife (Wager and Athey, 2018).
That gives confidence intervals for individual-level effects, which no off-the-shelf boosted model provides. Here are both approaches on a real randomised experiment.
The Criteo AI Lab's uplift benchmark (Diemert, Betlei, Renaudin and Amini, 2018; CC BY-NC-SA 4.0): 13,979,592 users in a randomised advertising test, of whom 85% were assigned to be shown the company's adverts and 15% held out. Each user has 12 anonymised features (dense, real-valued projections of the advertiser's data), and the outcomes are whether the user visited the advertiser's website and whether they bought. We use a random 10% of the users (1,398,727), with "visit" as the outcome, and split them in half to fit and evaluate.
from econml.grf import CausalForest # Criteo's uplift benchmark: 13.98 million users in a randomised advertising test; we keep a random 10% g10 = np.random.default_rng(0) cr = pd.concat([ch[g10.random(len(ch)) < 0.10] for ch in pd.read_csv('data/criteo-research-uplift-v2.1.csv.gz', chunksize=1_000_000)]) fcols = [f'f{k}' for k in range(12)]; Xh = cr[fcols].astype(np.float32) Y, T = cr['visit'].to_numpy(), cr['treatment'].to_numpy() Htr, Hte = train_test_split(np.arange(len(cr)), test_size=0.5, random_state=0) def diff(idx): a, b = Y[idx][T[idx] == 1], Y[idx][T[idx] == 0] return a.mean() - b.mean(), np.sqrt(a.var() / len(a) + b.var() / len(b)) ate, se = diff(np.arange(len(cr))) print(f'{len(cr):,} users ({T.mean():.0%} shown ads); visit rate {Y[T == 0].mean():.4f} without ads, {Y[T == 1].mean():.4f} with;' f' average effect {ate:.4f} ± {1.96 * se:.4f}') # T-learner: one boosted model per arm m1 = xgb.XGBClassifier(n_estimators=300, max_depth=6, learning_rate=0.1, tree_method='hist', random_state=0) m0 = xgb.XGBClassifier(n_estimators=300, max_depth=6, learning_rate=0.1, tree_method='hist', random_state=0) tr1, tr0 = Htr[T[Htr] == 1], Htr[T[Htr] == 0] m1.fit(Xh.iloc[tr1], Y[tr1]); m0.fit(Xh.iloc[tr0], Y[tr0]) cate_t = m1.predict_proba(Xh.iloc[Hte])[:, 1] - m0.predict_proba(Xh.iloc[Hte])[:, 1] # Honest causal forest (generalised random forest), on 200,000 of the training users to keep it fast sub_cf = np.random.default_rng(1).choice(Htr, 200_000, replace=False) cf = CausalForest(n_estimators=500, min_samples_leaf=200, honest=True, random_state=0, n_jobs=2) cf.fit(Xh.iloc[sub_cf].to_numpy(), T[sub_cf], Y[sub_cf]) cate_cf = cf.predict(Xh.iloc[Hte].to_numpy()).ravel() print(f'\n{len(Hte):,} held-out users grouped by predicted effect; observed effect = difference in visit rates') for name, c in [('T-learner (XGBoost)', cate_t), ('causal forest', cate_cf)]: q = pd.qcut(c, 5, labels=False, duplicates='drop') print(f'{name}:') for k in range(5): idx = Hte[q == k]; d, s = diff(idx) print(f' quintile {k + 1}: mean predicted {c[q == k].mean():.4f} observed {d:.4f} ± {1.96 * s:.4f}')
1,398,727 users (85% shown ads); visit rate 0.0378 without ads, 0.0488 with; average effect 0.0110 ± 0.0009 699,364 held-out users grouped by predicted effect; observed effect = difference in visit rates T-learner (XGBoost): quintile 1: mean predicted -0.0175 observed 0.0117 ± 0.0035 quintile 2: mean predicted 0.0000 observed 0.0001 ± 0.0005 quintile 3: mean predicted 0.0004 observed 0.0004 ± 0.0006 quintile 4: mean predicted 0.0023 observed 0.0026 ± 0.0013 quintile 5: mean predicted 0.0572 observed 0.0346 ± 0.0050 causal forest: quintile 1: mean predicted -0.0022 observed -0.0002 ± 0.0010 quintile 2: mean predicted 0.0004 observed 0.0001 ± 0.0006 quintile 3: mean predicted 0.0013 observed 0.0008 ± 0.0007 quintile 4: mean predicted 0.0044 observed 0.0039 ± 0.0016 quintile 5: mean predicted 0.0383 observed 0.0396 ± 0.0058
On average the adverts raise the visit rate from 3.78% to 4.88%, an effect of 1.1 percentage points (±0.1). Because assignment was random, we can check each model's claims on the held-out half: group users by their predicted effect and compare the visit rates of treated and control users within each group. Both methods find that the effect is concentrated: in the causal forest's top quintile the adverts add 4.0 points (±0.6), while in its bottom three quintiles the observed effect is within two tenths of a point of zero, so a fifth of the users account for most of the campaign's effect. The causal forest's predictions are well calibrated quintile by quintile (it predicts 3.8 points for its top group, where 4.0 are observed). The T-learner is not: it predicts 5.7 points for its top quintile, where 3.5 are observed, and its bottom quintile, predicted to be harmed by the adverts (−1.8 points), in fact responds by 1.2: subtracting two separately fitted models of a rare outcome produces extreme differences in both directions, a known weakness of the T-learner.
Why is it legitimate to check predicted treatment effects by comparing treated and control visit rates within quintiles of predicted effect?
Marketing calls this uplift modelling: send the offer to the customers it changes, not to those who would buy anyway or never will. The same tools serve personalised medicine (which patients benefit from a treatment with side effects?) and policy (which job-seekers gain from a training programme?). Two cautions apply everywhere. Heterogeneity estimates are noisy, so a targeting rule should be evaluated on held-out randomised data, as above, before it is deployed. And with observational data the trees only estimate causal effects under unconfoundedness (Lecture 4); causal forests make the estimation flexible, not the assumptions weaker.
In complexity theory, a decision tree computing a Boolean function \(f:\{0,1\}^n\to\{0,1\}\) queries one input bit per node; its depth is the number of queries. The deterministic query complexity \(D(f)\) is the smallest depth of a tree computing \(f\). A quantum algorithm can query bits in superposition, and its query complexity \(Q(f)\) can be much smaller: Grover search computes OR of \(n\) bits with \(Q=O(\sqrt n)\) queries, against \(D=n\). How much smaller can it be? For total functions (defined on every input), Beals et al. (2001) proved \(D(f)=O(Q(f)^6)\), and after Huang's 2019 proof of the sensitivity conjecture, Aaronson et al. (2021) improved this to \(D(f)=O(Q(f)^4)\), which is tight up to logarithmic factors (Ambainis et al., 2017). So for total Boolean functions quantum computers give at most a polynomial speed-up in queries; exponential speed-ups, as in Shor's algorithm, need problems with structure, where the input is promised to have a special form.
Next: Lecture 9 turns from trees to general graphs: similarity graphs built from data, the graph Laplacian, label propagation, and graph neural networks.
Parent: \(2\times0.8\times0.2=0.32\). Left (40 penguins): \(2\times0.95\times0.05=0.095\). Right (10): \(2\times0.2\times0.8=0.32\). Weighted: \((40\times0.095+10\times0.32)/50=0.14\). Decrease \(0.32-0.14=0.18\).
Misclassification: parent 20/100; children 0/50 and 20/50, weighted \(20/100\): no change. Gini: parent 0.32; children 0 and \(2\times0.6\times0.4=0.48\), weighted 0.24, a decrease of 0.08. The split isolates a pure group of A, which makes later splits of the impure child easier; a greedy search guided by misclassification rate would never take it.
Each of the \(n\) draws misses the point with probability \(1-1/n\), independently. \(\log(1-1/n)^n=n\log(1-1/n)\to-1\). For \(n=239\), \((238/239)^{239}\approx0.3671\).
The variance of the sum, \(B\sigma^2(1+(B-1)\rho)\), cannot be negative. With many predictors, the correlation can only be very slightly negative, so the floor \(\rho\sigma^2\) can barely go below zero: decorrelating to near zero is the most one can hope for.
Mistakes are multiplied by \(e^{\alpha_t}=\sqrt{(1-\varepsilon_t)/\varepsilon_t}\) and correct points by \(e^{-\alpha_t}=\sqrt{\varepsilon_t/(1-\varepsilon_t)}\). The new mistake weight is \(\varepsilon_t\sqrt{(1-\varepsilon_t)/\varepsilon_t}=\sqrt{\varepsilon_t(1-\varepsilon_t)}\), and the correct weight is the same, so after normalising each is \(\tfrac12\). The new weighting makes \(h_t\) useless, so the next learner must capture something else.
Using \(\sigma'=\sigma(1-\sigma)\): \(\frac{\partial}{\partial F}\big[-y\log\sigma\big]=-y(1-\sigma)\) and \(\frac{\partial}{\partial F}\big[-(1-y)\log(1-\sigma)\big]=(1-y)\sigma\). Adding gives \(\sigma-y\), and differentiating again gives \(\sigma(1-\sigma)\). These are XGBoost's \(g_i\) and \(h_i\) for classification.
\(\tfrac12\big[36/5+4/3-16/7\big]-1=\tfrac12(7.2+1.3333-2.2857)-1=3.1238-1=2.1238>0\): yes. The leaf values would be \(6/5=1.2\) and \(-2/3\).
For \(x_1+2x_2\): \(v(\emptyset)=0\), \(v(\{1\})=1\), \(v(\{2\})=2\), \(v(N)=3\); \(\phi_1=\tfrac12[(1-0)+(3-2)]=1\), \(\phi_2=2\). For an additive model the Shapley values are the terms. For \(x_1x_2\): \(v(\{1\})=v(\{2\})=0\), \(v(N)=1\), so \(\phi_1=\phi_2=\tfrac12\): an interaction is split equally between the features involved.
A stump depends on one feature, so a sum of stumps is a sum of one-feature functions; group the stumps by feature. A depth-\(d\) tree's leaf is reached by at most \(d\) tests, so each leaf's indicator depends on at most \(d\) features, and the tree is a sum of such indicators. Friedman recommends trees with 4 to 8 leaves in practice, allowing moderate interactions.
Randomisation makes \(T\) independent of \((Y(0),Y(1),X)\), and membership in \(G\) is a function of \(X\) (and of independent data), so \(T\) is independent of \((Y(0),Y(1))\) given \(X\in G\). Then \(\mathbb E[Y\mid T=1,X\in G]=\mathbb E[Y(1)\mid X\in G]\) and similarly for control; conditionally on the group sizes, the sample means are unbiased for these.
Each project uses this lecture's methods and public data, and has a clear result.
Data. Penguins: A. M. Horst, A. P. Hill, K. B. Gorman, palmerpenguins (2020), CC0. California housing: R. K. Pace, R. Barry, "Sparse spatial autoregressions", Statistics & Probability Letters 33(3), 291–297 (1997), in the copy from A. Géron, Hands-On Machine Learning (github.com/ageron/handson-ml2). Breast cancer: Street, Wolberg and Mangasarian (1993), UCI, via scikit-learn. Crash-helmet data: Silverman (1985), MASS::mcycle. American Community Survey 2018, 1-year person file for California: US Census Bureau (public domain), downloaded with Folktables: F. Ding, M. Hardt, J. Miller, L. Schmidt, "Retiring Adult: new datasets for fair machine learning", NeurIPS 34 (2021); category labels from the Census Bureau's 2018 PUMS data dictionary. Criteo uplift v2.1: E. Diemert, A. Betlei, C. Renaudin, M.-R. Amini, "A large scale benchmark for uplift modeling", AdKDD (2018), CC BY-NC-SA 4.0, copy criteo/criteo-uplift on the Hugging Face Hub. TabPFN v2 regressor weights: Prior Labs (Prior Labs License 1.1), Prior-Labs/TabPFN-v2-reg on the Hugging Face Hub.
every number in the text and widgets is computed in verify_L08.py; code-box outputs are pasted from actual runs