Introduction to Decision Trees
Learning Objectives
After reading this page, you should be able to:
- Classify a test point using a decision tree.
- Draw the decision boundaries of a decision tree.
- Explain why training error is a poor criterion for choosing a split.
1 Introduction
Decision trees are simple, interpretable, and powerful algorithms. They are akin to a sequence of layered if-else statements that you might write in many programming languages. However, instead of programming if-else statements by hand, we will use our example data set (a training set) to determine the exact logic to use.
This chapter consists of three sections. The first section describes inference using decision trees: that is, how to apply decision trees to make a prediction on a new data point. This section also briefly considers how decision trees are built and discusses challenges in comparing the quality of a split. The second section presents ideas from information theory, in particular the definition of a measure called information gain to help compare between different splits. The final section describes the learning of a decision tree, using the ideas and methods from the previous sections.
In this chapter, we will revisit a core ML idea: turning learning into optimization. We reframe the problem of choosing each split as an optimization problem. By using a greedy approach to choose the “best” local split at each step, we can select one tree from many candidates to fit the training set.
Although decision trees sound simple, they are remarkably versatile, and are still one of the best performing models in ML competitions. Many extensions can be made: e.g., gradient boosted decision trees and random forest. Some of these ideas will be discussed later on. In short, when approaching a machine learning problem, it pays to resist the temptation to jump straight into complex models because of their hype. Often, simpler models like decision trees can capture the underlying patterns just as effectively, are easier to train and interpret, and are more likely to generalize well to unseen data.
2 Inference Using Decision Trees: Making Predictions
As usual, we will start discussing decision trees by first learning how to perform inference, that is, how to generate a prediction for a test point given a decision tree.
Recall the leaf prediction example, where we predict whether a leaf is Oak or Maple based on the width and height measurements of the leaf. Here is an example of a decision tree that could be used to make these predictions.
Decision tree with 3 internal nodes and 4 leaf nodes
A decision tree is drawn upside down: the root is at the top, and the leaves are at the bottom. Each non-leaf node tests a condition on one feature, for example, “Is \(\text{width} \le 10.5\)?”, and routes the input down one of the two branches based on the answer. Each leaf node specifies a prediction, such as Oak or Maple.
To classify a new input, start at the root node, and answer the question at each non-leaf node, follow the corresponding branch until you reach a leaf. The leaf’s label is the prediction.
The following diagram visualizes the inference process for the test point \(\textbf{x}=\begin{bmatrix}7 & 6 \end{bmatrix}^\top\). Use the slider to see predictions for other inputs.
Decision tree showing the inference path
2.1 Decision Boundaries
Recall that a decision boundary partitions the data space into regions, where each region corresponds to a predicted class. Decision boundaries apply to any classifier, regardless of model family.
Decision tree boundaries are always axis-aligned, because each split tests a threshold on a single feature at a time. In two dimensions, this means every boundary is a horizontal or vertical line segment; in higher dimensions, each boundary is a hyperplane perpendicular to one of the feature axes. This contrasts with classifiers like k-nearest neighbors, whose boundaries can be oriented in any direction.
To find the boundaries of a decision tree, trace the splits from the root to the leaves and retain only those boundaries that separate regions of different predicted classes.
The figure below shows the boundaries of the decision tree above, which was trained on the leaf dataset introduced in the supervised learning section. The training points are included for reference.
3 Building a Decision Tree: Choosing a Split
Now that we know how to perform inference using a decision tree, how do we build a tree given a training set? A decision tree is constructed through a recursive splitting procedure. We start with all training points at the root. At each step, we choose a feature and a threshold, then split the current points into two subsets based on whether they satisfy the condition. This is useful for classification because conditioning on an observed feature value can reduce our uncertainty about the class label: after a good split, each subset is more class-pure than the original. We then repeat the same procedure on each subset until a stopping criterion is reached. At that point, each subset becomes a leaf node, which is assigned a class label.
The key question is which feature and threshold we should split on at each step. Different split orders can produce very different trees, because an early split changes the subset of data seen by every later split. The figure below shows two different decision trees built using the same Maple/Oak data set.
Two decision trees trained on the same Maple/Oak leaf dataset, but with different split orders
In principle, we could treat this as a global optimization problem. The hypothesis space is the set of all trees we can build from the training data, and the loss function is training error. Our goal is to find a tree that minimizes that loss. Unfortunately, this approach has two significant drawbacks. First, minimizing training error can lead to poor generalization. Decision trees are highly expressive. They are, in fact, universal function approximators. Thus, for a data set, a sufficiently large tree can often classify every training example correctly. Such a tree simply memorizes the training set and generalizes poorly to unseen data. Second, searching over all possible trees is computationally intractable. It has been shown that finding the smallest tree that perfectly classifies a training set is NP-complete.
Instead, we decompose the problem of learning a full tree into a sequence of smaller sub-problems. Each sub-problem is a local optimization problem: at the current node, choose the best split for the data that reached it.
This strategy is a greedy approach: at each node, we choose the locally optimal split without considering how it may affect future splits. Because each decision is myopic, a sequence of locally optimal splits need not produce a globally optimal tree.
To formalize this problem, we need two ingredients: a hypothesis space and a loss function. The hypothesis space contains all possible splits to consider at each node. The loss function measures the quality of each split so we can compare them and pick the best one.
Figure 5 below shows all possible splits on each feature. For convenience, we chose each split to be the midpoint value between two consecutive values of the feature. Theoretically, we could have chosen a split that is outside of the range of values for a feature, e.g., choosing to split on \(\text{width} = 4.0\,\text{cm}\). However, such a split is not useful since it does not split the data into two subsets with at least one data point in each subset. Therefore, we only consider splits that are within the range of values for the feature.
All possible splits on each feature
3.1 Training Error as the Loss Function
With the hypothesis space defined, it remains to define a loss function. We begin with a familiar concept: training error, the fraction of training examples that are misclassified.
A split divides the training data into two regions, and each region needs a prediction before we can compute the training error. We use the majority vote rule: each region predicts the most common class among its training points. If two classes are tied, we use a tie-breaking rule: the region predicts the most common class in the full training set, which is Oak for our leaf data. We also use these two rules to assign a prediction to each leaf node of a decision tree. Figure 6 shows three splits, each drawn as a tree with a single split.
Three columns (Tree A–C)
Let’s compare the first two splits using training error as the loss function. Tree A misclassifies 1 of the 7 training points (the Maple leaf that falls to the left of the split), giving a training error of \(1/7\). Tree B misclassifies 2 of the 7 training points, giving a training error of \(2/7\). Since Tree A achieves a lower training error (\(1/7 < 2/7\)), the training error loss function identifies Tree A’s split as the better choice.
3.2 Limitations of Training Error as the Loss Function
However, using training error as the loss function has significant limitations. Consider a scenario where we have two potential splits that result in the same training error. For example, Figure 7 shows two possible width-based splits on the same Maple/Oak leaf data set. Both splits produce a training error of \(2 / 7\). Does that mean that the two splits are equally good?
Comparison of two potential splits on the same Maple/Oak leaf dataset
Machine learning practitioners tend to prefer split #1 over split #2 for two reasons. First, the left side of split #1 is class-pure: all the training data points to the left of the split belong to class Oak. Thus, if our test data point has a low \(\text{width}\) measurement, we can confidently predict Oak. In this sense, split #1 is better at reducing our uncertainty about the class labels.
Second, although we are only considering a single split, we will eventually want to make additional splits further down the tree. A split that doesn’t immediately decrease error might still be valuable if it reduces uncertainty in a way that will help future splits.
These reasons suggest that we need a more nuanced measure that captures how well a split reduces uncertainty about the target variable. In the next section, we will explore information theory, which provides principled tools (entropy and information gain) for measuring uncertainty and evaluating splits. These concepts will allow us to build decision trees that are both accurate and interpretable.