Decision Trees

Table of Contents

1. Learning Objectives
2. Notation
3. Core Intuition
4. Recursive Partitioning Framework
5. Impurity Measures
6. Information Gain and Split Criteria
7. The Greedy Induction Algorithm
8. Regression Trees
9. Pruning and Complexity Control
10. Theoretical Properties
11. Common Pitfalls
12. Summary
13. Exercises

Learning Objectives

1. Formalize a decision tree as a recursive partition of input space.
2. Derive Gini impurity and entropy as measures of node heterogeneity.
3. Derive the information gain criterion for optimal split selection.
4. Analyze the greedy algorithm's computational complexity.
5. Explain cost-complexity pruning and its connection to regularized risk.
6. Understand why trees are high-variance, low-bias estimators.

Notation

• $\mathcal{R}_m$ — region corresponding to leaf node $m$
• $N_m$ — number of training samples in region $m$
• $\hat{p}_{mk}$ — proportion of class $k$ in node $m$
• $H(m)$ — impurity of node $m$
• $G$ — information gain from a split
• $|\mathcal{T}|$ — number of leaf nodes (tree complexity)

Core Intuition

A decision tree partitions the input space $\mathcal{X} \subseteq \mathbb{R}^d$ into axis-aligned rectangular regions, each assigned a constant prediction. The partition is built top-down: at each step, we find the split (feature $j$, threshold $t$) that most reduces prediction error. The resulting model is interpretable, non-parametric, and handles mixed feature types naturally.

Recursive Partitioning Framework

A tree $T$ defines a partition $\{\mathcal{R}_1, \ldots, \mathcal{R}_M\}$ of $\mathcal{X}$ with predictions:

For classification: $c_m = \arg\max_k \hat{p}_{mk}$ (majority vote). For regression: $c_m = \frac{1}{N_m}\sum_{x_i \in \mathcal{R}_m} y_i$ (mean).

Each internal node implements a split $x_j \leq t$, creating two child nodes.

Impurity Measures

Definition (Gini Impurity). For a node $m$ with $K$ classes:

Gini impurity equals the probability that a randomly chosen sample would be misclassified if labeled according to the distribution in the node.

Definition (Entropy).

Both are maximized when classes are uniformly distributed and minimized (zero) when the node is pure (single class).

Definition (MSE for regression).

Information Gain and Split Criteria

A split $s$ of node $m$ into children $m_L$ and $m_R$ produces information gain:

The optimal split maximizes $G$:

For each feature $j$ with $V$ distinct values, there are at most $V - 1$ candidate thresholds. Total candidates per node: $\sum_j (V_j - 1) \leq nd$ in the worst case.

The Greedy Induction Algorithm

CART Algorithm (Breiman et al., 1984):

1. Start with root containing all $n$ samples.
2. For current node $m$:
   • If stopping criterion met (pure node, max depth, min samples): make leaf.
   • Otherwise: find best split $s^* = (j^*, t^*)$ maximizing gain.
   • Partition data: $m_L = \{i : x_{ij^*} \leq t^*\}$, $m_R = \{i : x_{ij^*} > t^*\}$.
3. Recurse on $m_L$ and $m_R$.

Complexity. At each node with $N_m$ samples: testing all splits costs $O(d \cdot N_m\log N_m)$ (sort each feature). Over all nodes at a given depth: $O(dn\log n)$. For depth $D$: total $O(Ddn\log n)$.

Regression Trees

For squared-error loss, the optimal constant prediction in region $\mathcal{R}_m$ is the sample mean $\bar{y}_m$. The best split minimizes:

This is equivalent to maximizing the reduction in total variance — the regression analog of information gain.

Pruning and Complexity Control

An unpruned tree typically overfits ($\hat{R}_n = 0$ if grown to full depth). Cost-complexity pruning regularizes:

where $|\mathcal{T}|$ is the number of leaves and $\alpha \geq 0$ is a complexity parameter.

Theorem (Breiman). For any $\alpha$, there exists a unique smallest subtree $T_\alpha \subseteq T_{\max}$ that minimizes $R_\alpha$. The sequence of optimal subtrees is nested: $T_{\alpha_1} \supseteq T_{\alpha_2}$ for $\alpha_1 < \alpha_2$.

The optimal $\alpha$ is selected via cross-validation.

Theoretical Properties

Consistency. Under mild conditions, decision trees are universally consistent: as $n \to \infty$ with appropriate depth growth ($D \to \infty$, $D/n \to 0$), the risk converges to the Bayes risk.

Bias-Variance. Deep trees have low bias (can approximate any function on the training set) but high variance (small data perturbations change the tree structure drastically). This motivates ensemble methods (bagging, boosting) that reduce variance.

Approximation. A tree with $M$ leaves is a piecewise-constant function. Approximating a Lipschitz function to accuracy $\epsilon$ in $d$ dimensions requires $M = O(\epsilon^{-d})$ leaves — the curse of dimensionality.

Common Pitfalls

Pitfall 1. Splits are axis-aligned. If the true boundary is diagonal (e.g., $x_1 + x_2 = 0$), trees need many splits to approximate it (staircase pattern).

Pitfall 2. Greedy splitting is not globally optimal. The best split at the root may not lead to the best overall tree. Finding the optimal tree is NP-complete.

Pitfall 3. Information gain is biased toward features with many distinct values. Gain ratio (Quinlan, C4.5) corrects this by normalizing by split entropy.

Summary

• Decision trees recursively partition space via axis-aligned splits.
• Gini impurity and entropy measure node heterogeneity; splits maximize information gain.
• Trees are greedy, non-parametric, and interpretable.
• Unpruned trees overfit; cost-complexity pruning balances fit vs. complexity.
• High variance makes trees ideal base learners for ensembles.

Exercises

Exercise 1. Show that Gini impurity is a second-order Taylor approximation of entropy around uniform $\hat{p}_{mk} = 1/K$.

Exercise 2. For binary classification, show that both Gini and entropy are concave functions of $p$ and derive their maxima.

Exercise 3. Prove that the optimal constant prediction minimizing MSE within a region is the sample mean.

Exercise 4. Construct a 2D example where the optimal tree of depth 2 is not obtained by the greedy algorithm.

Exercise 5. Derive the number of possible binary trees with $M$ leaves and relate it to the Catalan numbers.