Decision Tree Learning
Learning Objectives
After reading this page, you should be able to:
- Construct a decision tree by recursively selecting features that maximize information gain.
- Describe the advantages and limitations of decision trees.
- Explain how the hyperparameters of a decision tree affect the complexity of the tree.
1 Introduction
Thus far, we have seen how to make predictions with decision trees, and we have learned about how information gain \(IG(Y|X)\) can be used as a metric for measuring the “quality” of a potential decision tree split. We can now put everything together to understand how to build decision trees from data.
In this chapter, we will see how these concepts come together in a complete learning algorithm. We will also explore the practical aspects of building decision trees, including hyperparameters that control tree growth and strategies for handling real-world challenges like overfitting and missing data.
2 The Trade-Off Question and Why Not Build the “Optimal” Tree?
At first glance, building a decision tree might seem simple: you might expect we should just construct the “optimal” tree that perfectly classifies every training example. In fact, if our only goal were to achieve maximum accuracy on the training data, the process would be trivial: we could simply build a very large tree that has a separate leaf for every training sample. In this way, each path through the tree leads to an exact match for a single example, ensuring perfect training accuracy. Decision trees can, thus, represent any function (or data) arbitrarily well. They are what are called universal function approximators. This theoretical power means that, given enough depth, a decision tree can fit any training set perfectly.
Definition: A model class \(\mathcal{A}\) is a universal function approximator if, for any continuous target function \(f\) (i.e., any continuous ground-truth mapping from input \(x\) to output \(t\)) and for any desired level of approximation error \(\epsilon > 0\) (i.e., any degree of training accuracy), there exists some hypothesis \(h \in \mathcal{A}\) such that \(|h(x) - f(x)| < \epsilon\) for all \(x\) in the domain (or for all \(x\) in a relevant, sufficiently large subset of the domain).
However, an optimal tree will not be the most useful. We saw during the nearest neighbours unit that a model that attains perfect training accuracy can fail to generalize. A tree with many leaf nodes could achieve high training accuracy, but it would likely perform poorly on new data because it has memorized the training set rather than learning generalizable patterns.
We would typically like a smaller tree than the tree that maximizes training accuracy. Unfortunately, finding the smallest optimal tree is NP-complete. It is generally computationally infeasible to find such a tree.
Because of this, our goal shifts from finding the absolute optimal tree to learning a useful tree: one that strikes a balance between accuracy, generalization to new data, interpretability, and computational efficiency. To illustrate, consider the following two classification trees, both trained to predict the presence of heart disease. Which one do you think is more useful?
Two decision trees for heart disease prediction
Tree (A) is simple. It only splits on age. It is smaller, and thus requires less storage and provides faster inference time. Smaller trees are also more interpretable: its predictions are easier for a person to understand. However, smaller trees like this might underfit. It might not capture important patterns.
Tree (B) is more complex. It has more splits, and therefore more leaf nodes. It will more certainly produce a higher training accuracy (why?), but it will have additional storage, computation, and interpretability costs. It could also overfit.
The point is there’s a trade-off, and it’s hard to say which tree is definitively better without proper evaluation. This trade-off between model complexity and generalization is a central theme in machine learning that we’ll explore throughout this text.
3 Decision Tree Learning: The Greedy Strategy
Given that finding the optimal tree is computationally intractable, we need a practical approach. We use a greedy strategy: the key idea is to make the locally optimal “best” split at each node, even if this doesn’t lead to a globally optimal tree. Then, to construct a decision tree from data, we use a recursive algorithm. We treat each subtree as itself a decision tree, so we can recursively choose the locally optimal “best” split.
The algorithm can be summarized as follows:
Start with all training data at the root node
For each node:
- Check if we should stop splitting (see stopping criteria below)
- If stopping, create a leaf node with a prediction
- Otherwise, find the best feature and split point (maximize information gain)
- Split the data according to this feature and threshold
- Recursively apply the algorithm to each child node
Continue until all branches end in leaf nodes
This recursive structure makes sense because each subtree is itself a decision tree. The algorithm naturally handles the hierarchical structure of decision trees.
This greedy approach is computationally efficient and, in practice, produces trees that perform well. However, it does not guarantee finding the best possible tree: it only guarantees that each individual split is locally optimal.
At each node, you need to consider all possible splits. The number of candidate splits depends on the type of feature. For categorical features, consider all possible ways to partition the categories. For a binary feature, there’s only one way to split. For a feature with \(k\) categories, there are \(2^{k-1} - 1\) ways to partition them into two groups. For continuous features, consider split points between consecutive unique values. Since the training data is finite, there are only a finite number of thresholds to consider—specifically, the midpoints between consecutive unique values.
Consider the oak vs maple leaf dataset. How could this greedy process be used to learn the decision tree shown at the beginning of the decision tree unit?
Interactive decision tree builder
4 Decision Tree Stopping Criteria
The goal is to build a tree that is neither too small nor too large. This balance is crucial for good performance. Not too small: we need to handle important but possibly subtle distinctions in the data, capture relevant patterns that help with prediction, and avoid underfitting. Not too big: we want computational efficiency (avoid redundant, spurious attributes), avoid overfitting to the training examples, and maintain human interpretability—a tree that’s too large becomes hard to understand.
Occam’s Razor suggests finding the simplest hypothesis that fits the observations. This is a useful principle, but hard to formalize (how to define simplicity?). We desire small trees with informative nodes near the root. The simplest tree that explains the data well is often the best.
In practice, finding good stopping criteria is challenging and needs to be resolved empirically. One important consideration is that you have exponentially less data at lower levels of the tree. The root node uses all training data, but as you go deeper, each node uses a subset of the data from its parent. By the time you reach deep leaves, you may have very few examples, making those predictions less reliable. This is why we need hyperparameters to control when to stop splitting. There are some cases where it is obvious that we should stop splitting. If a node is pure, i.e., all training examples in that node have the same label, then there is no point to continued splitting.
More generally, there are hyperparameters that control when to stop splitting. Unlike model parameters (like the split thresholds), which are learned from data, hyperparameters are tuned empirically using the validation set. Key hyperparameters to consider include:
- Maximum depth limits how many levels the tree can have. Too deep may overfit; too shallow may underfit. Common values range from 3 to 20, depending on the dataset.
- Minimum samples per node requires that each node contains at least a certain number of training examples before it can be split. This prevents splitting on very small subsets of data, which are more likely to be noise.
- Minimum information gain requires that a split must provide at least a certain amount of information gain to be considered. Splits that don’t meet this threshold are rejected, preventing unnecessary tree growth.
- Minimum samples per leaf ensures that each leaf has enough examples to make a reliable prediction. Leaves with very few examples may have unreliable predictions, especially if those examples are noisy.
One other approach to build a “useful” tree is to begin with a large tree, but then post-prune the tree afterwards. Post-pruning works by growing the tree until it fits the training data (possibly overfitting), evaluating each subtree on validation data, removing branches that don’t improve validation performance, and keeping the simplest tree that performs well on validation data.
5 Summary
Building decision trees involves using a greedy algorithm that recursively splits the data, choosing the “best” split according to some criteria (e.g., information gain for classification), and stopping when hyperparameter limits are reached or no beneficial splits remain. Since finding the optimal tree is computationally intractable, this greedy approach provides a practical way to build trees.
The resulting trees are interpretable, fast at inference time, and effective for many tasks. However, decision trees make strong assumptions about the form of the decision boundary: trees create boundaries that are aligned with the feature axes, meaning they can only create rectangular regions in the feature space. This inductive bias, the assumption that the decision boundary can be well-approximated by axis-aligned splits, can be a strength or weakness: it improves interpretability, keeps models simple, but can limit the model’s expressiveness.
Of course, decision trees are universal approximators, so in theory a deeper tree can approximately emulate any decision boundary. However, there are tradeoffs to having deeper trees. This goes back to one of the themes that you will see throughout many ML models that we will encounter: many models will have hyperparameters that affect the capacity of the model. In this case, the stopping criteria (e.g., max depth, minimum samples to split) control the size of the tree. Post-pruning, or growing a tree fully then removing branches that don’t help, is another option to control the size of the tree. The choice of hyperparameters determines where we balance between underfitting (too simple, missing important patterns) and overfitting (too complex, capturing noise).