Decision trees and ensemble methods

Tree models partition the input space into axis-aligned regions and fit a constant per region, giving interpretable but high-variance predictors. Ensemble methods combine many trees: bagging and random forests average independently grown trees to cut variance, while boosting grows trees sequentially to cut bias.

Objectives

• Express a tree as a piecewise-constant function and choose splits with an impurity criterion.
• Control overfitting with cost-complexity pruning.
• Reduce variance by bagging and decorrelate trees with feature subsampling.
• Estimate generalization error for free with out-of-bag samples.
• Build a strong predictor as an additive sum of weak learners (AdaBoost, gradient boosting).

CART decision trees

Tree as a partition

A CART tree partitions the input space into \(M\) disjoint regions \(R_1,\dots,R_M\) (the leaves) and predicts a constant \(c_m\) on each. The prediction is defined as

Each internal node tests one feature against a threshold, \(x_j\le s\), sending an example left or right. A path from the root to a leaf is a conjunction of such tests.

Remark: the regions are axis-aligned boxes, so the decision boundary is a staircase. A single tree has low bias but high variance.

Impurity and split selection

For a region with class proportions \(\hat p_k\), impurity measures how mixed the labels are. The Gini index is defined as

and the entropy as

A candidate split sends \(N_-\) examples to child \(R_-\) and \(N_+\) to child \(R_+\) out of \(N\). Its information gain is defined as

where \(I\) is the chosen impurity. CART greedily picks the feature and threshold that maximize \(IG\) at each node.

Remark: the two criteria almost always pick the same split. Gini is the default in most implementations because it avoids the logarithm.

Regression trees

For regression the leaf value is the mean of the targets in the region, defined as

and splits minimize the within-region squared error instead of a classification impurity.

Pruning

An unpruned tree fits the training set exactly and overfits. Cost-complexity pruning trades fit against tree size \(|T|\) (the number of leaves) through a penalty \(\alpha\ge0\):

\[\boxed{ C_\alpha(T)=\sum_{m} N_m\,I(R_m)+\alpha\,|T| }\]

Increasing \(\alpha\) collapses the weakest splits, yielding a nested sequence of subtrees. The best \(\alpha\) is chosen by cross-validation.

graph TD
  A["x_j <= s ?"] -->|"yes"| B["x_k <= t ?"]
  A -->|"no"| C["leaf R3"]
  B -->|"yes"| D["leaf R1"]
  B -->|"no"| E["leaf R2"]

A tree carves the input space into axis-aligned regions, each with a constant prediction.

Random forests

Bagging

Bagging (bootstrap aggregating) trains \(B\) trees on \(B\) bootstrap resamples of the data and averages them. The bagged predictor is defined as

For classification the average is replaced by a majority vote. Averaging leaves bias unchanged while shrinking variance.

A bootstrap sample draws \(N\) examples with replacement from \(N\) examples. The probability that a given example is never drawn is \((1-\tfrac1N)^N\to e^{-1}\approx0.37\), so about 37% of the data is left out of each tree. These are its out-of-bag (OOB) examples.

Variance of an average

If the \(B\) trees each have variance \(\sigma^2\) and pairwise correlation \(\rho\), the variance of their average is

The second term vanishes as \(B\) grows, but the first, \(\rho\sigma^2\), does not. Reducing the correlation \(\rho\) between trees is therefore the key lever, and that is what random forests target.

Random forests

A random forest is bagging plus feature subsampling: at each split only a random subset of \(m_{\text{try}}\) features is considered as split candidates. The usual choices are

Restricting the candidate features stops every tree from splitting on the same dominant feature, which decorrelates the trees and lowers \(\rho\).

Remark: OOB error averages each tree's error over only the examples that tree never saw, giving a cross-validation-like estimate at no extra cost.

graph TD
  A["training set"] --> B1["bootstrap sample 1"]
  A --> B2["bootstrap sample 2"]
  A --> B3["bootstrap sample B"]
  B1 --> T1["tree 1"]
  B2 --> T2["tree 2"]
  B3 --> T3["tree B"]
  T1 --> AGG["aggregate: average or vote"]
  T2 --> AGG
  T3 --> AGG

(a) A single deep tree overfits with a jagged boundary. (b) A random forest averages many trees for a smoother boundary.

Boosting

Additive model

Boosting builds a predictor as a weighted sum of \(T\) weak learners \(h_t\) (typically shallow trees), fitted one at a time. The additive model is defined as

Each stage corrects the errors of the running sum, so the ensemble is built sequentially and reduces bias rather than variance.

AdaBoost

With labels \(y\in\{-1,+1\}\), AdaBoost keeps example weights \(w^{(i)}\) that concentrate on the currently misclassified points. At round \(t\) the weak learner has weighted error \(\varepsilon_t\), and its coefficient is defined as

so a more accurate learner (\(\varepsilon_t\) small) gets a larger vote. The weights are then updated as

and renormalized. Misclassified examples (\(y^{(i)}h_t(x^{(i)})<0\)) gain weight, so the next learner focuses on them.

Gradient boosting

Gradient boosting generalizes the idea to any differentiable loss \(L\). At stage \(t\) it fits the next learner to the negative gradient of the loss evaluated at the current model, the pseudo-residual defined as

The model is then updated with a learning rate (shrinkage) \(\nu\in(0,1]\):

Remark: with squared-error loss the pseudo-residual is just the ordinary residual \(y^{(i)}-H_{t-1}(x^{(i)})\), so each tree fits what the current model still gets wrong.

graph LR
  A["weak learner 1"] --> B["weak learner 2"]
  B --> C["weak learner 3"]
  C --> D["weak learner T"]
  D --> E["weighted sum H_T"]

This completes the supervised-learning core of the course. To take these models from a notebook to a running service, continue with the MLOps course.

Next: Course overview