Trees, Bagging and Boosting

Impurity and greedy splitting, the exact variance algebra behind bagging, and boosting derived as functional gradient descent.

Classical MLAdvanced⏱ 3 hours14 min readdecision treeentropyginibaggingrandom forest

5 problems →

AssumesLinear, Ridge and Lasso Regression · Gradient Descent and Its Convergence Rates

Trees and impurity

A decision tree partitions $\Xcal$ by recursive axis-aligned splits and predicts a constant in each leaf. Growing it optimally is NP-hard, so the standard algorithm is greedy: at each node choose the split maximising the decrease in an impurity measure.

DefinitionImpurity measures

For a node with class distribution $p = (p_1,\dots,p_C)$ :

\text{entropy } H(p) = -\sum_c p_c\log p_c, \qquad \text{Gini } G(p) = 1-\sum_cp_c^2 = \sum_c p_c(1-p_c), \qquad \text{misclassification } M(p) = 1-\max_cp_c .

PropositionConcave impurity gives non-negative information gain

Let $\Phi$ be concave on the probability simplex. A split of a node into children with weights $w_L+w_R=1$ and distributions $p_L,p_R$ satisfying $w_Lp_L + w_Rp_R = p$ has

\text{gain} = \Phi(p) - \big(w_L\Phi(p_L) + w_R\Phi(p_R)\big) \ge 0 ,

with equality iff $\Phi$ is affine along the segment $[p_L,p_R]$ . Entropy and Gini are strictly concave; misclassification error is concave but piecewise affine.

Key idea

This is why entropy and Gini are used and misclassification error is not, despite being the quantity we actually care about: because $M$ is piecewise affine, many splits have exactly zero gain under it, and the greedy algorithm has no signal to follow. A strictly concave surrogate always prefers a split that makes the children purer, even when it does not change the majority class in either. The choice of surrogate is driven by the optimisation, not by the statistics — the same pattern as the hinge and logistic losses standing in for the zero-one loss.

Bagging and random forests

PropositionBagging variance algebra

Let $\hat f_1,\dots,\hat f_B$ be predictors each with variance $\sigma^2$ and pairwise correlation $\rho$ at a fixed input. The average $\bar f = \frac1B\sum_b\hat f_b$ has

\Var(\bar f) = \rho\sigma^2 + \frac{1-\rho}{B}\sigma^2 \xrightarrow[B\to\infty]{} \rho\sigma^2 .

Key idea

The limit is $\rho\sigma^2$ , not $0$ . Averaging removes only the independent part of the variance; the correlated part survives no matter how many trees you grow. So after a few hundred trees, further averaging is wasted, and the only way to improve is to reduce $\rho$ .

That single observation is the entire design of random forests: in addition to bootstrap resampling (which decorrelates through the data), split on a random subset of $m \ll p$ features at each node (which decorrelates through the algorithm). The cost is an increase in $\sigma^2$ — each tree is worse — and the trade is favourable because the $\rho$ term dominates for large $B$ . Breiman's $m$ of $\sqrt p$ for classification is a tuning of exactly this trade.

AdaBoost

Algorithm — AdaBoost

Initialise weights $w_i^{(1)} = 1/n$ .
For $t = 1,\dots,T$ :
fit a weak classifier $h_t\in\{\pm1\}^\Xcal$ minimising the weighted error $\eps_t = \sum_i w_i^{(t)}\one\{h_t(x_i)\ne y_i\}$ ;
set $\beta_t = \tfrac12\log\dfrac{1-\eps_t}{\eps_t}$ ;
reweight $w_i^{(t+1)} \propto w_i^{(t)}\exp\big(-\beta_ty_ih_t(x_i)\big)$ and renormalise.
Output $F_T(x) = \sum_{t\le T}\beta_th_t(x)$ , classified by $\sign F_T$ .

TheoremAdaBoost is coordinate descent on the exponential loss

Consider minimising

\mathcal{E}(F) = \frac1n\sum_{i=1}^n\exp\big(-y_iF(x_i)\big)

over additive models $F = \sum_t\beta_th_t$ . Then at each round, the $h$ minimising $\mathcal{E}(F_{t-1}+\beta h)$ to first order in $\beta$ is the minimiser of the weighted error with weights $w_i^{(t)}\propto e^{-y_iF_{t-1}(x_i)}$ , and the exact minimising step size is $\beta_t = \tfrac12\log\frac{1-\eps_t}{\eps_t}$ .

Key idea

AdaBoost was invented from a learning-theoretic question ("can weak learners be combined into a strong one?") and only later recognised as coordinate descent on the exponential loss. The recognition is what generalised it: once you know the algorithm is minimising a loss by greedy stagewise fitting, you can swap the loss, and gradient boosting is what you get.

TheoremAdaBoost drives training error to zero exponentially

If each weak learner satisfies $\eps_t \le \tfrac12-\gamma$ for some $\gamma>0$ , then the training error of $F_T$ satisfies

\frac1n\sum_i\one\{\sign F_T(x_i)\ne y_i\} \le \exp\big(-2\gamma^2T\big) .

Gradient boosting

PropositionGradient boosting is gradient descent in function space

Let $L(y,F)$ be differentiable in $F$ and consider minimising $\frac1n\sum_iL(y_i,F(x_i))$ over $F$ in the span of a base class $\mathcal{B}$ . Regard the objective as a function of the vector $\big(F(x_1),\dots,F(x_n)\big)\in\R^n$ ; its negative gradient has components

r_i = -\frac{\partial L(y_i,F(x_i))}{\partial F(x_i)} .

Fitting $h_t\in\mathcal{B}$ by least squares to $(x_i,r_i)$ and taking $F_t = F_{t-1}+\nu\beta_th_t$ is a projected gradient step in this $n$ -dimensional space, with $\nu$ the learning rate.

Reading the residuals for common losses:

Loss $L(y,F)$	Negative gradient $r_i$
$\tfrac12(y-F)^2$	$y_i - F_i$ — the ordinary residual
$\log(1+e^{-yF})$	$y_i\,\sigma(-y_iF_i)$ — residual weighted by uncertainty
$e^{-yF}$	$y_ie^{-y_iF_i}$ — recovers AdaBoost
$\abs{y-F}$	$\sign(y_i-F_i)$ — robust, ignores outlier magnitude

XGBoost in one line of mathematics

XGBoost replaces the first-order step with a second-order one: expand $L(y_i, F_i + h(x_i))$ to second order in $h$ ,

\sum_i\left[g_ih(x_i) + \tfrac12 h_ih(x_i)^2\right] + \Omega(h), \qquad g_i = \partial_F L,\ h_i = \partial^2_F L ,

and minimise this weighted quadratic plus a tree-complexity penalty $\Omega$ exactly over tree structures. Because the objective is now a sum of per-leaf quadratics, the optimal leaf value has a closed form $-\sum_{i\in\text{leaf}}g_i / (\sum_{i\in\text{leaf}}h_i+\lambda)$ and the split gain does too — which is what makes the greedy search fast. The relationship to plain gradient boosting is exactly the relationship of Newton's method to gradient descent.

Empirical observationBoosting resists overfitting longer than expected

Empirical observation — a regularity seen in experiments. No theorem on this page establishes it in general.

Boosted ensembles often continue to improve on test data long after the training error has reached zero, and adding hundreds more rounds frequently does not hurt.

What this does not say

The training-error theorem above says nothing about test error, and a naive capacity argument would predict severe overfitting: $T$ rounds of trees is a large hypothesis class. The partial explanation is margin theory: Schapire and co-authors showed that boosting continues to increase the margin distribution $y_iF_T(x_i)/\sum_t\beta_t$ after the training error hits zero, and there are margin-based generalisation bounds analogous to the SVM margin bound that are independent of $T$ .

This is a genuine explanation but not a complete one: the margin bounds are numerically loose, there are constructed examples where a larger minimum margin gives worse generalisation, and boosting with a very flexible base learner and noisy labels does overfit. The practical rules — shrinkage $\nu\approx0.1$ , shallow trees, early stopping on a validation set — are empirical, and gradient boosting remains the strongest method on tabular data for reasons that are not fully characterised.

Problems

Concave impurity gives non-negative information gainProof · Intermediate · 30 min The bagging variance formulaProof · Intermediate · 30 min AdaBoost as exact line search on the exponential lossProof · Advanced · 30 min AdaBoost drives training error to zero exponentiallyProof · Advanced · 1 hour Gradient boosting fits the negative functional gradientProof · Intermediate · 30 min

References

PaperLeo Breiman (1996). Bagging Predictors
PaperLeo Breiman (2001). Random Forests
PaperYoav Freund and Robert E. Schapire (1997). A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting
PaperJerome H. Friedman (2001). Greedy Function Approximation: A Gradient Boosting Machine
PaperTianqi Chen and Carlos Guestrin (2016). XGBoost: A Scalable Tree Boosting System

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

PropositionAny concave impurity gives non-negative information gainproof includedA split can never increase a concave impurity measure in expectation, which is what makes greedy splitting well posed.
PropositionBagging variance algebraproof includedAveraging B correlated predictors leaves the correlated part of the variance untouched, which is exactly what feature subsampling attacks.
TheoremAdaBoost is coordinate descent on the exponential lossproof includedThe AdaBoost weights and coefficients are exactly the exact line search and greedy coordinate choice for the exponential loss.
TheoremAdaBoost drives training error to zero exponentiallyproof includedIf every weak learner beats chance by a fixed margin the training error decays geometrically in the number of rounds.
PropositionGradient boosting is gradient descent in function spaceproof includedEach round fits a base learner to the negative functional gradient of the loss at the current model.
Empirical observationBoosting resists overfitting longer than the training error suggestsTest error often keeps improving after training error reaches zero, which margin theory partially explains.

Problems (5)

All problems

Papers that use this mathematics

XGBoost: A Scalable Tree Boosting System
Tianqi Chen, Carlos Guestrin · 2016