11.2 Learning Decision Trees

Introduction

Learning a decision tree involves constructing a tree structure that partitions the feature space to minimize prediction error. The learning algorithm must decide which features to split on, where to split, and when to stop growing the tree. This process is fundamental to understanding how decision trees can model complex decision boundaries.

1. The Recursive Partitioning Algorithm

Decision tree learning follows a greedy, top-down recursive partitioning approach. Starting from the root, we select the best split at each node and recursively apply the same process to child nodes.

Algorithm Outline

    function BuildTree(data, features):
        if stopping_criterion(data):
            return LeafNode(predict(data))
        
        best_feature, best_threshold = find_best_split(data, features)
        left_data, right_data = split_data(data, best_feature, best_threshold)
        
        left_subtree = BuildTree(left_data, features)
        right_subtree = BuildTree(right_data, features)
        
        return InternalNode(best_feature, best_threshold, left_subtree, right_subtree)
    

2. Splitting Criteria

The quality of a split is measured by how well it separates the data into homogeneous groups. Different criteria quantify this homogeneity differently.

2.1 Classification: Impurity Measures

For classification, we measure the impurity of a node. A pure node contains samples from only one class.

Gini Impurity

The Gini impurity measures the probability of incorrectly classifying a randomly chosen element:

$$Gini(t) = 1 - \sum_{i=1}^{C} p_i^2$$

where $p_i$ is the proportion of class $i$ samples at node $t$, and $C$ is the number of classes.

Properties: Gini ranges from 0 (pure) to $1 - \frac{1}{C}$ (maximum impurity). For binary classification, maximum impurity is 0.5.

Entropy (Information Gain)

Entropy measures the amount of information (or uncertainty) in the node:

$$H(t) = -\sum_{i=1}^{C} p_i \log_2(p_i)$$

Information gain from a split is:

$$IG(t, s) = H(t) - \sum_{child \in \{left, right\}} \frac{N_{child}}{N_t} H(child)$$

where $N_t$ is the number of samples at node $t$, and $N_{child}$ is the number in each child node.

Classification Error

The misclassification error is simply:

$$E(t) = 1 - \max_i p_i$$

This is less sensitive to changes in node probabilities and is rarely used for growing trees, but can be useful for pruning.

2.2 Regression: Variance Reduction

For regression trees, we use the variance (or mean squared error) as the splitting criterion:

$$Var(t) = \frac{1}{N_t} \sum_{i \in t} (y_i - \bar{y}_t)^2$$

where $\bar{y}_t$ is the mean of target values at node $t$.

The variance reduction from a split is:

$$\Delta Var(t, s) = Var(t) - \sum_{child \in \{left, right\}} \frac{N_{child}}{N_t} Var(child)$$

3. Finding the Best Split

For each feature, we evaluate all possible split points and choose the one that maximizes the impurity decrease (or variance reduction).

Continuous Features

For a continuous feature $x_j$, we consider splits of the form $x_j \leq \theta$. The algorithm evaluates thresholds between consecutive unique values in the sorted feature values.

Efficient computation: Sort the data by feature $x_j$, then scan through the sorted order, updating sufficient statistics incrementally. This reduces complexity from $O(N^2)$ to $O(N \log N)$ per feature.

Categorical Features

For a categorical feature with values $\{v_1, v_2, \ldots, v_K\}$, we consider splits that partition the categories into two groups.

For binary classification, there's an optimal ordering of categories by their class proportions. For multi-class or regression, the problem is more complex ($2^{K-1} - 1$ possible splits).

4. Stopping Criteria

We stop growing the tree when one of the following conditions is met:

• Pure node: All samples belong to the same class (classification) or have the same target value (regression)
• Minimum samples: Number of samples at the node falls below a threshold (e.g., min_samples_split = 2)
• Maximum depth: The tree reaches a predefined maximum depth
• No improvement: No split improves the impurity beyond a threshold
• Minimum samples per leaf: A split would create a leaf with fewer than min_samples_leaf samples

5. Pruning

Growing a tree until stopping criteria are met often results in overfitting. Pruning reduces tree complexity by removing subtrees that provide little predictive power.

5.1 Pre-pruning (Early Stopping)

Stop growing the tree early based on criteria like:

• Maximum depth reached
• Minimum samples per node
• Minimum impurity decrease threshold

Limitation: May stop too early, missing opportunities for good splits further down the tree.

5.2 Post-pruning (Cost Complexity Pruning)

Grow a full tree, then prune it back. The cost complexity measure is:

$$R_\alpha(T) = R(T) + \alpha |T|$$

where:

• $R(T)$ is the total impurity (or error) of tree $T$
• $|T|$ is the number of leaf nodes
• $\alpha \geq 0$ is the complexity parameter (larger $\alpha$ means more pruning)

Minimal Cost-Complexity Pruning Algorithm

For each value of $\alpha$, there exists a smallest tree $T(\alpha)$ that minimizes $R_\alpha(T)$. The algorithm:

1. Grow the full tree $T_0$
2. For each internal node $t$, compute: $$\alpha_{eff}(t) = \frac{R(t) - R(T_t)}{|T_t| - 1}$$ where $T_t$ is the subtree rooted at $t$
3. Find the node with smallest $\alpha_{eff}$ and prune it
4. Repeat until only the root remains
5. Use cross-validation to select the best $\alpha$

6. Handling Missing Values

Decision trees can handle missing values in several ways:

Surrogate Splits

Find alternative features that give similar splits. When the primary feature is missing, use the best surrogate split.

Separate Category

Treat missing values as a separate category when evaluating splits.

Imputation

Fill in missing values before building the tree (e.g., with median for continuous features, mode for categorical features).

7. Feature Importance

The importance of feature $j$ is computed by summing the impurity decrease from all splits on that feature:

$$Importance(x_j) = \sum_{t: split\ on\ x_j} \frac{N_t}{N} \Delta I(t, s_t)$$

where $N$ is the total number of samples, $N_t$ is the number at node $t$, and $\Delta I(t, s_t)$ is the impurity decrease from split $s_t$.

8. Multivariate Splits

Standard decision trees use axis-parallel splits ($x_j \leq \theta$). Multivariate trees allow oblique splits:

$$w_1 x_1 + w_2 x_2 + \cdots + w_d x_d \leq \theta$$

This allows more compact trees but increases computational cost and reduces interpretability.

9. Advantages of the Learning Algorithm

• Efficient: $O(N d \log N)$ time complexity for $N$ samples and $d$ features
• Handles mixed data: Naturally handles both continuous and categorical features
• Non-parametric: Makes no assumptions about data distribution
• Feature selection: Automatically performs feature selection
• Interpretable: The resulting model is easy to understand and visualize

10. Connection to LLMs

Decision tree learning principles appear in modern LLM architectures:

• Hierarchical decisions: Attention mechanisms make sequential decisions similar to tree paths
• Information gain: Token selection in generation maximizes information about the next token
• Pruning strategies: Model compression techniques like pruning remove less important parameters
• Ensemble methods: Mixture of experts models combine multiple specialized sub-models (like random forests)
• Gradient-based splitting: Gradient boosting principles inform how transformers are trained layer by layer

11. Computational Considerations

Time Complexity

For each node, finding the best split requires:

• Sorting each feature: $O(N \log N)$
• Evaluating $d$ features: $O(d \cdot N \log N)$ per node
• Tree depth is typically $O(\log N)$, so total: $O(d \cdot N \log^2 N)$

Space Complexity

Storage requirements are $O(N_{leaves} + N_{internal})$ for the tree structure, plus $O(N)$ for the training data during construction.

Key Takeaways

• Decision tree learning uses recursive partitioning with greedy split selection
• Gini impurity and entropy are common splitting criteria for classification
• Variance reduction is used for regression trees
• Pruning is essential to prevent overfitting and improve generalization
• Cost-complexity pruning provides a principled way to select tree size
• Feature importance emerges naturally from the splitting process
• The algorithm efficiently handles large datasets and mixed feature types
• Decision tree principles underlie many modern ML techniques including gradient boosting and neural network design

12. Tree Depth vs. Performance

Deeper trees can overfit training data: training error often decreases monotonically with depth, while validation error typically follows a U-shape (initially decreasing, then increasing as the model memorizes noise). Explore this effect interactively below.