Information Theory for Decision Trees
Learning Objectives
After reading this page, you should be able to:
- Compute the entropy of a discrete distribution over class labels.
- Calculate the expected information gain of splitting on a feature given a data set.
1 Introduction
When building decision trees, we face a fundamental question at each node: which feature should we use to split the data, and what threshold should we apply? In the previous discussions of decision trees, we considered using misclassification rates to guide our splitting decisions, and found this metric to be problematic.
Information theory provides a more principled approach through the concept of entropy and information gain. Information theory, developed by Claude Shannon in the 1940s, provides a rigorous mathematical framework for quantifying uncertainty and information. The core concepts from information theory, particularly entropy and information gain, turn out to be ideally suited for decision tree construction. This chapter introduces these fundamental concepts and demonstrates how they apply to the problem of learning decision trees.
The key insight is that a good split should reduce our uncertainty about the class labels. Information theory gives us precise tools to measure this uncertainty and to quantify how much a particular split reduces it. By the end of this chapter, we will see that information gain provides a systematic way to compare different possible splits.
2 Entropy: Quantifying Uncertainty
Before we can evaluate how good a decision tree split is, we need a way to measure uncertainty. Consider the two loaded coins: coin 1 produces heads with probability \(p=\frac{1}{9}\) and coin 2 produces heads with probability \(p=\frac{5}{9}\). Here is a sequence of outcomes from flipping these two coins.
Sequence of 30 flips of Coin 1 and Coin 2
Question: Which coin would you say has a larger uncertainty? Why?
Answer:
Coin 2 is more uncertain. Coin 1 strongly favors tails, so each flip is more predictable.
The term “entropy” originates from thermodynamics, where it measures the state of disorder in a physical system. In the context of machine learning and information theory, entropy measures the uncertainty inherent in a probability distribution over possible outcomes. In other words, entropy measures how unpredictable the outcome of a random draw from a probability distribution is.
Definition: The entropy of a discrete random variable \(X\) with probability mass function \(p(x)\) is defined as: \[\begin{align*} H(X) = -\mathbb{E}_{X\sim p}[\log_2 p(X)]=-\sum_{x \in X} p(x) \log_2 p(x) \end{align*}\] where the logarithm is taken in base 2, and by convention \(0 \log_2 0 = 0\). The summation \(x \in X\) sums over the set of possible outcomes, and \(p(x)\) is the probability of outcome \(x\).
Entropy is measured in bits.
Intuitively, entropy measures how much “surprise” or “information” we expect from a single observation. It represents how much information, on average, we gain by observing a random draw from the distribution. If the outcome is completely predictable (one outcome has probability 1), we gain no information by observing it, so the entropy is zero. If the outcome is completely unpredictable (uniform distribution), we gain a larger amount of information by observing it, so the entropy is larger.
But why is entropy measured in bits? Why is base-2 logarithm used? This choice is linked to coding theory and another interpretation of entropy: entropy is a lower bound on the number of bits needed to encode and store a sequence of outcomes of a random variable. If the outcome of a random variable is predictable, then we can find compression schemes to encode and store a sequence of outcomes with a small number of bits. For example, if a coin has only \(p=\frac{1}{1000}\) chance of coming up heads, then we can store a sequence of outcomes by storing just the indices of coin flips that came up heads, which requires much less storage than storing all outcomes explicitly. However, this compression scheme would not work well if a coin is balanced. Thus, the entropy of a random variable that is “more predictable” is lower than if the random variable is “less predictable”.
3 The Entropy of a Bernoulli Random Variable
To help develop intuition, let’s compute the entropy of Bernoulli Random Variables. Consider the two coins from earlier: coin 1 with probability \(p = \frac{1}{9}\) of producing heads, and coin 2 with probability \(p = \frac{5}{9}\). Intuitively, coin 2 has a larger uncertainty than coin 1. We can verify this by computing the entropy for these two coins.
Let \(X_1\) and \(X_2\) be random variables that represent the outcomes of coin 1 and coin 2. Then, we have that the entropy of the two variables are:
\[\begin{align*} H(X_1) &= -\frac{1}{9}\log_2\left(\frac{1}{9}\right) - \frac{8}{9}\log_2\left(\frac{8}{9}\right) \approx 0.503 \text{ bits} \\[2pt] H(X_2) &= -\frac{5}{9}\log_2\left(\frac{5}{9}\right) - \frac{4}{9}\log_2\left(\frac{4}{9}\right) \approx 0.991 \text{ bits} \end{align*}\]
The second coin has nearly double the entropy of the first, reflecting the fact that its outcome is much more uncertain. More generally, when a probability distribution is concentrated on a small number of outcomes, the entropy is low. When the distribution is spread more evenly across many outcomes, the entropy is high.
Question: What is the entropy of a fair coin where the probability of heads is exactly \(\frac{1}{2}\)? What is the entropy when the probability is exactly 0 or 1?
Answer:
For a fair coin, there is probability \(p=\frac{1}{2}\) of heads, so \(H = -\frac{1}{2}\log_2 \frac{1}{2} - \frac{1}{2}\log_2 \frac{1}{2} = 2\cdot \bigl(\frac{1}{2}\cdot(-1)\bigr) = 1 \text{ bit}\).
For \(p=0\), we have \(H = 0 \log_2 0 = 0\) by convention. Likewise, for \(p=1\), we have \(H = 1 \log_2 1 = 0\). In both cases, the entropy is 0 since the outcome is deterministic.The figure below shows that in extreme cases, when \(p=0\) or \(p=1\), the outcome is completely certain before we even observe it. We gain no new information by observing the coin flip, so the entropy is exactly 0 bits (recall that this is the amount of storage needed). At the other extreme, when \(p=\frac{1}{2}\), the coin is fair and the entropy reaches its maximum value of 1 bit for a binary random variable.
Entropy of a coin flip as a function of the probability of heads
These properties align with our intuitive understanding of uncertainty. When we are completely certain about an outcome, we learn nothing from observing it (entropy is zero). When all outcomes are equally likely, we are maximally uncertain and learn the most from each observation.
4 Joint and Conditional Entropy
In decision tree learning, we are interested in how knowledge of one random variable affects our uncertainty about another. For instance, we might want to know how observing whether it is raining (\(X\)) affects our uncertainty about whether it is cloudy (\(Y\)). Thus, we need to extend the concept of entropy to multiple random variables. This subsection will begin by introducing several definitions and concepts, before connecting these concepts back to comparing decision tree splits.
Let us consider the weather example as a running example to ground our definitions: we would like to predict whether it is cloudy outside (with \(Y=1\) representing that it is cloudy, and \(Y=0\) representing that it is not), but we are sitting in a classroom and can only observe whether it is raining (with \(X=1\) meaning it is raining, \(X=0\) meaning it is not). Given the local climate, the joint distribution of the system might look like this:
\[\begin{array}{c|cc} & Y=1\ (\text{Cloudy}) & Y=0\ (\text{Not Cloudy}) \\ \hline X=1\ (\text{Raining}) & \frac{24}{100} & \frac{1}{100} \\ X=0\ (\text{Not Raining}) & \frac{25}{100} & \frac{50}{100} \end{array}\]Question: Given this table, what is \(P(X=0, Y=1)\)? What about \(P(X=0)\)? What about \(P(Y=1|X=0)\)?
Answer:
\(P(X=0,Y=1)=\frac{25}{100}\).
\(P(X=0)= P(X=0,Y=0) + P(X=0,Y=1) = \frac{50}{100}+\frac{25}{100}=\frac{75}{100}\).
\(P(Y=1\mid X=0)=\dfrac{P(X=0,Y=1)}{P(X=0)}=\frac{25/100}{75/100}=\frac{1}{3}\).
In our first definition, we will consider the entropy of the entire system. The joint entropy \(H(X,Y)\) measures the total uncertainty in both variables considered together: i.e., if we consider \((X,Y)\) as a single random variable with 4 possible outcomes.
Definition: The joint entropy of two discrete random variables \(X\) and \(Y\) with joint probability mass function \(p(x,y)\) is: \[\begin{align*} H(X,Y) = -\mathbb{E}_{X, Y\sim p(x,y)}[\log_2 p(X, Y)] = -\sum_{x\in X}\sum_{y\in Y} p(x,y) \log_2 p(x,y) \end{align*}\]
The joint entropy represents the total uncertainty when both variables are unknown. It is the amount of information we would gain, on average, by observing both \(X\) and \(Y\). In our example, the entropy of this joint system can be calculated as follows:
\[\begin{align*} H(X,Y) &= -\frac{24}{100} \log_2\frac{24}{100} -\frac{1}{100} \log_2\frac{1}{100} -\frac{25}{100} \log_2\frac{25}{100} -\frac{50}{100} \log_2\frac{50}{100} \\[2pt] &\approx 1.561 \text{ bits} \end{align*}\]
More interesting is the concept of conditional entropy: if we observe one variable, how much uncertainty remains about the other? To understand conditional entropy, we first need to distinguish between two related concepts: the conditional entropy for a specific value \(H(Y|X=x)\), and the expected conditional entropy \(H(Y|X)\).
When we condition on a specific value \(X=x\), we obtain a conditional distribution \(p(y|X=x)\) for \(Y\). The conditional entropy \(H(Y|X=x)\) is simply the entropy of this conditional distribution:
\[\begin{align*} H(Y|X=x) = -\sum_{y\in Y} p(y|x) \log_2 p(y|x) \end{align*}\]
This quantity tells us how uncertain we are about \(Y\) when we know that \(X\) has taken on the specific value \(x\). For example, suppose that it is not raining \(X=0\). Then the conditional entropy \(H(Y|X=0)\) is
\[\begin{align*} H(Y|X=0) &= -p(Y=1|X=0)\log_2(p(Y=1|X=0)) \\[2pt] &\quad\quad - p(Y=0|X=0)\log_2(p(Y=0|X=0)) \\[2pt] &= -\frac{25}{75}\log_2\left(\frac{25}{75}\right) - \frac{50}{75}\log_2\left(\frac{50}{75}\right) \\[2pt] &\approx 0.918 \text{ bits} \end{align*}\]
Compare this with the case \(X=1\) (it is raining):
\[\begin{align*} H(Y|X=1) &= -p(Y=1|X=1)\log_2(p(Y=1|X=1)) \\[2pt] &\quad\quad- p(Y=0|X=1)\log_2(p(Y=0|X=1)) \\[2pt] &= -\frac{24}{25}\log_2\left(\frac{24}{25}\right) - \frac{1}{25}\log_2\left(\frac{1}{25}\right) \\[2pt] &\approx 0.242 \text{ bits} \end{align*}\]
In this case, the uncertainty about cloudiness is smaller when we observe rain, compared to when we observe no rain.
However, these quantities don’t answer the original question “how much does observing whether it is raining (\(X\)) affect our uncertainty about whether it is cloudy (\(Y\))” In this case, we do not know which specific conditional entropy we will encounter: \(X=0\) or \(X=1\). The expected conditional entropy averages over all possible values of \(X\), weighted by their probabilities.
Definition: The expected conditional entropy of \(Y\) given \(X\) is: \[\begin{align*} H(Y|X) &= \mathbb{E}_{x \sim p(x)}[H(Y|X=x)] \\[2pt] &= \sum_{x\in X} p(x)H(Y|X=x) \\[2pt] &= -\sum_{x\in X} \sum_{y\in Y} p(x,y) \log_2 p(y|x) \end{align*}\]
In our example, the expected conditional entropy of \(Y\) given \(X\) is
\[\begin{align*} H(Y | X) &= p(X=1) \cdot H(Y|X=1) + p(X=0) \cdot H(Y|X=0) \\[2pt] &= \frac{1}{4} \cdot 0.242 + \frac{3}{4} \cdot 0.918 \\[2pt] &\approx 0.749 \text{ bits} \end{align*}\]
This result tells us that after observing whether it is raining, we expect to have about 0.749 bits of uncertainty remaining about cloudiness. Before observing anything, the entropy of cloudiness alone (which we can compute from the marginal distribution) would be higher. Observing whether it is raining has reduced our uncertainty.
5 Properties of Entropy
Entropy, conditional entropy, and joint entropy satisfy important mathematical properties. Understanding these properties helps build intuition for how these quantities behave and provides tools for working with them algebraically. We will enumerate some important properties here.
Entropy is always nonnegative: That is, \(H(X) \geq 0\) for any random variable \(X\). This follows directly from the definition, since probabilities are between 0 and 1, so \(-\log_2 p(x) \geq 0\). The entropy is exactly zero if and only if the distribution is deterministic, meaning one outcome has probability 1.
The Chain Rule: This rule states that the joint entropy can be decomposed as the entropy of one variable plus the conditional entropy of the other given the first: \[\begin{align*} H(X,Y) = H(X|Y) + H(Y) = H(Y|X) + H(X) \end{align*}\] The symmetry of this equation reflects the fact that we can consider either variable first.
Independence: If random variables \(X\) and \(Y\) are independent, then \(X\) provides no information about \(Y\), so \(H(Y|X) = H(Y)\). The chain rule then implies \(H(X,Y) = H(X) + H(Y)\), meaning the joint entropy is the sum of the marginal entropies.
Information never increases uncertainty: Conditional entropy is always less than or equal to the unconditional entropy: \(H(Y|X) \leq H(Y)\). This makes intuitive sense: observing \(X\) can only reduce (or leave unchanged) our uncertainty about \(Y\), never increase it. Information never hurts.
Perfect Information: If \(X\) completely determines \(Y\) (i.e., if \(Y\) is a function of \(X\)), then \(H(Y|X) = 0\). Knowing \(X\) makes \(Y\) certain. If this wording is confusing, consider the case that \(X=Y\), i.e. observing \(X\) is the same as observing \(Y\) itself. But once we know \(Y\), there is no uncertainty left about \(Y\): \(H(Y|Y)=0\). This is consistent with our intuition that perfect information eliminates uncertainty.
6 Information Gain
We now arrive at the key concept that connects information theory to decision tree learning: information gain. Information gain quantifies how much observing one random variable (e.g., \(X\)) reduces our uncertainty about another (e.g., \(Y\)).
Definition: The information gain (also called mutual information) of \(Y\) with respect to \(X\) is defined as: \[\begin{align*} IG(Y|X) = H(Y) - H(Y|X) \end{align*}\] Information gain measures how many bits of information about \(Y\) we gain, on average, by observing \(X\). It can also be interpreted as the reduction in uncertainty about \(Y\) achieved by knowing \(X\).
Information gain has several properties, deriving from the properties of entropy given above.
Information gain is always non-negative. Since \(H(Y|X) \leq H(Y)\), we have \(IG(Y|X) \geq 0\).
When \(X\) and \(Y\) are independent, observing \(X\) provides no information about \(Y\). Thus, if \(X\) and \(Y\) are independent, then \(IG(Y|X)=0\).
If \(X\) completely determines \(Y\), meaning we can perfectly predict \(Y\) from \(X\), then \(H(Y|X)=0\) and \(IG(Y|X)=H(Y)\). In this case, observing \(X\) removes all uncertainty about \(Y\).
Information gain is symmetric: \(IG(Y;X) = IG(X;Y)\). This can also be written as \(IG(Y;X) = H(X) - H(X|Y) = H(X) + H(Y) - H(X,Y)\).
Let us return to our weather example and compute the information gain \(IG(Y|X)\). We had previously computed \(H(Y|X) \approx 0.749\) bits. To find the information gain, we need the marginal entropy \(H(Y)\).
\[\begin{align*} H(Y) &= -p(Y=1)\log_2(p(Y=1)) - p(Y=0)\log_2(p(Y=0)) \\[2pt] &= -0.49 \log_2(0.49) - 0.51 \log_2(0.51) \\[2pt] &\approx 1.000 \text{ bits} \end{align*}\]
The information gain is: \[\begin{align*} IG(Y|X) = H(Y) - H(Y|X) \approx 1.000 - 0.749 = 0.251 \text{ bits} \end{align*}\]
This computation tells us that observing whether it is raining reduces our uncertainty about cloudiness by approximately 0.251 bits, on average. This is a modest but meaningful reduction in uncertainty.
7 Information Gain in Decision Trees
But what does this have to do with decision tree training?
Suppose that we are learning a decision tree to predict whether it is cloudy \(Y\), and we have several candidate features that we can use to make a split. One of the candidate features \(X\) might be a binary feature measuring whether it is raining. The quantity \(IG(Y|X)\) thus measures how “good” this split is. Of course, we will need to compare this split with other candidate features in our data set: for example, if we also have features representing the current temperature, the current air pressure, etc.
In other words, when learning a decision tree, we must choose which feature to split on at each node. Information gain provides a principled criterion for this choice: we should select the split that maximizes information gain with respect to the class label.
In order to evaluate a split, we will define some notation. Consistent with earlier, we use the random variable \(Y\), which represents the class label that we wish to predict. We use the (binary) random variable \(X\), which represents which side of a potential split a data point falls on. For a binary split, \(X\) might take values “left” (\(X=0\)) and “right” (\(X=1\)). To obtain estimates of the probabilities required in the information gain computation (such as \(p(Y=y)\), \(p(X=x)\), and \(p(Y=y|X=x)\)), we will use the training data: i.e., we count the observed frequencies of each outcome in the training data.
Let us make this concrete with an example using the leaf dataset. We consider potential splits on the “width” feature, using \(Y=0\) to represent Oak and \(Y=1\) to represent Maple. The dataset contains 4 Oak leaves (\(Y=0\)) and 3 Maple leaves (\(Y=1\)), so the entropy at the root is:
\[\begin{align*} H(Y) &= -p(Y=0)\log_2(p(Y=0)) - p(Y=1)\log_2(p(Y=1)) \\[2pt] &= -\frac{4}{7}\log_2\left(\frac{4}{7}\right) - \frac{3}{7}\log_2\left(\frac{3}{7}\right) \approx 0.985 \text{ bits} \end{align*}\]
Now, let’s consider two candidate splits: Split 1, which divides the data at width = 8.0, and Split 2, which divides the data at width = 9.5. Which split is better?
Comparison of two potential splits on the leaf dataset
Here, it is helpful to introduce two variables. Let \(X_1 = \{ 0, 1\}\) represent whether a data point lies on the left side (\(X_1=0\)) or the right side (\(X_1=1\)) of Split 1. Likewise, we define \(X_2\) similarly, for Split 2. In order to compare the two splits, we will need to compute \(IG(Y|X_1)\) and \(IG(Y|X_2)\).
To compute \(IG(Y|X_1)\) for Split 1, note that the left child (\(X_1=0\)) contains 2 Oak leaves and 0 Maple leaves (a pure node!), while the right child (\(X_1=1\)) contains 2 Oak and 3 Maple leaves:
\[\begin{align*} H(Y|X_1=0) &= -p(Y=1|X_1=0)\log_2(p(Y=1|X_1=0)) \\[2pt] &\quad\quad - p(Y=0|X_1=0)\log_2(p(Y=0|X_1=0)) \\[2pt] &= -\frac{0}{2}\log_2\left(\frac{0}{2}\right) - \frac{2}{2}\log_2\left(\frac{2}{2}\right)\\[2pt] &= 0 \\[2pt] H(Y|X_1=1) &= -p(Y=1|X_1=1)\log_2(p(Y=1|X_1=1)) \\[2pt] &\quad\quad- p(Y=0|X_1=1)\log_2(p(Y=0|X_1=1)) \\[2pt] &= -\frac{3}{5}\log_2\left(\frac{3}{5}\right) - \frac{2}{5}\log_2\left(\frac{2}{5}\right) \\[2pt] &\approx 0.971 \text{ bits} \\[2pt] H(Y|X_1) &= p(X_1=0) \cdot H(Y|X_1=0) + p(X_1=1) \cdot H(Y|X_1=1) \\[2pt] &= \frac{2}{7} \cdot 0 + \frac{5}{7} \cdot 0.971 \\[2pt] &\approx 0.694 \text{ bits} \\[2pt] IG(Y|X_1) &= H(Y) - H(Y|X_1) = 0.985 - 0.694 \\[2pt] &\approx 0.292 \text{ bits} \end{align*}\]
Now consider Split 2, which divides the data at width = 9.5. The left child (\(X_2=0\)) contains 3 Oak leaves (\(Y=0\)) and 1 Maple leaf (\(Y=1\)), while the right child (\(X_2=1\)) contains 1 Oak leaf (\(Y=0\)) and 2 Maple leaves (\(Y=1\)). To compute \(IG(Y|X_2)\):
\[\begin{align*} H(Y|X_2=0) &= -p(Y=1|X_2=0)\log_2(p(Y=1|X_2=0)) \\[2pt] &\quad\quad - p(Y=0|X_2=0)\log_2(p(Y=0|X_2=0)) \\[2pt] &= -\frac{1}{4}\log_2\left(\frac{1}{4}\right) - \frac{3}{4}\log_2\left(\frac{3}{4}\right) \\[2pt] &\approx 0.811 \text{ bits} \\[2pt] H(Y|X_2=1) &= -p(Y=1|X_2=1)\log_2(p(Y=1|X_2=1)) \\[2pt] &\quad\quad - p(Y=0|X_2=1)\log_2(p(Y=0|X_2=1)) \\[2pt] &= -\frac{2}{3}\log_2\left(\frac{2}{3}\right) - \frac{1}{3}\log_2\left(\frac{1}{3}\right) \\[2pt] &\approx 0.918 \text{ bits} \\[2pt] H(Y|X_2) &= p(X_2=0) \cdot H(Y|X_2=0) + p(X_2=1) \cdot H(Y|X_2=1) \\[2pt] &= \frac{4}{7} \cdot 0.811 + \frac{3}{7} \cdot 0.918 \\[2pt] &\approx 0.857 \text{ bits} \\[2pt] IG(Y|X_2) &= H(Y) - H(Y|X_2) = 0.985 - 0.857 \\[2pt] &\approx 0.128 \text{ bits} \end{align*}\]
As you can see, Split 1 has higher information gain than Split 2. This is despite the fact that both splits have the same misclassification rate of \(2/7\)! Thus, information gain provides a more nuanced criterion for evaluating splits than misclassification rate alone, as it can distinguish between splits that create different levels of uncertainty reduction even when they have the same error rate.
When building a decision tree, at each node, we aim to evaluate many possible splits: e.g., across different features and different possible thresholds for each feature. We aim to choose the one with the highest information gain. Thus, it is worth asking: are there other splits that are even better than the two we considered? We will need to consider splitting along both the “height” and “width” dimensions.
Considering the “width” dimension only, can you find a better split than the two above, using the figure below?
Interactive exploration of information gain
One subtle but important observation is that, even though “width” is a continuous variable in principle, the number of meaningful splits we need to consider is actually finite for a given dataset. We saw this in this figure. As a result, even with continuous features, finding the optimal split is computationally feasible, since only a finite set of candidate splits need to be evaluated.
8 Limitations and Considerations
The approach of choosing a split that maximizes information gain is a greedy strategy. Greedy approaches like this do not guarantee finding the optimal tree overall. It may be possible that choosing a “less good” split near the root can result in an overall more optimal tree. However, finding the globally optimal decision tree is computationally intractable for realistic problem sizes, so greedy algorithms remain a practical choice.
The computational considerations for decision trees are also very different from those of the k-nearest neighbours algorithm. With k-NN, training requires simply storing the training data. However, making predictions requires computing distances to all training examples, which can be slow for large datasets. In contrast, decision trees require significant computation during training to evaluate all possible splits, but once the tree is built, making predictions is extremely fast. At inference time, we simply follow a path from root to leaf, requiring only a few comparisons regardless of the training set size. This trade-off reflects a fundamental distinction in machine learning: training-time complexity versus prediction-time complexity. Decision trees invest computation upfront during training to create a model that enables fast predictions, while k-NN defers computation to prediction time. The choice between these approaches depends on the application: if we need to make many predictions quickly (e.g., in real-time systems), decision trees are preferable. If we have limited training data and can afford slower predictions, k-NN may be more suitable.
While information gain is a theoretically well-founded criterion, other splitting criteria exist that provide similar results in practice. Gini impurity is computationally simpler (requiring no logarithms) and often produces trees very similar to those built with information gain. It is the default choice in decision tree algorithms implemented in software packages like sklearn. The fact that different criteria tend to yield similar results reflects a recurring theme in ML: the “best” criterion is often context-dependent, and practitioners compare alternatives on held-out data rather than relying on theory alone.
Information gain treats all misclassifications equally. In some applications, different types of errors may have different costs. For instance, in medical diagnosis, failing to detect a serious disease (a false negative) may be much worse than falsely suspecting disease when none is present (a false positive). Cost-sensitive learning extensions to decision trees can incorporate such asymmetric costs into the splitting criterion, allowing the algorithm to prioritize reducing more costly types of errors.
For regression tasks, where the target variable is continuous rather than discrete, information gain is not suitable. However, other measures can be used. We will see, in the linear regression unit, that mean squared error is a commonly used metric in evaluating regression models. Mean squared error or variance reduction is the standard criterion for regression trees, measuring how much a split reduces the variance of the target variable in the child nodes. This is analogous to how information gain measures reduction in entropy for classification tasks: a good split should create child nodes where the target values are more homogeneous (lower variance) than in the parent node.
These limitations and considerations tie back to themes from the introduction, primarily Fundamental Idea #3: Model Evaluation is Empirical. Context matters in the decision to choose model families and evaluation metrics.
9 Summary
Information theory provides powerful tools for decision tree learning. Entropy quantifies uncertainty in class distributions, conditional entropy measures uncertainty after a split, and information gain evaluates how effectively a split reduces uncertainty. These concepts form the foundation for principled decision tree construction algorithms.
Although modern decision tree learning algorithms generally do not use Information Gain directly, measures like Gini impurity also use similar ideas. While information gain has limitations and alternatives like Gini impurity are also effective, understanding the information-theoretic foundations deepens our understanding of how and why decision trees work.
One other takeaway from this chapter is Fundamental Idea #1: Learning is Optimization—the practice of turning learning problems into optimization problems. In considering how to choose a split (a learning problem), we have defined a measure for how good a split is, and chose a split that maximized that measure (i.e., optimization). The solution to this optimization problem is rather naive: we try a bunch of splits and choose the one that optimizes the cost. However, in practice the strategy ends up being quite effective in this particular case. We shall see repeatedly that turning learning problems into optimization problems is a common technique used across machine learning.
Fundamental Idea #5: ML Demands a Probabilistic Lens, is perhaps most directly illustrated in this chapter. The entire information-theoretic framework is built on probability distributions. Rather than asking “does this split correctly classify the training points?” we ask “does this split reduce our uncertainty about the class label?” This shift from deterministic reasoning (misclassification rate) to probabilistic reasoning (entropy reduction) is precisely why information gain is a more principled criterion: it treats the class label as a random variable and directly measures how much observing a feature reduces uncertainty about it. As we will see in later chapters, this probabilistic lens is essential for understanding and designing ML algorithms more generally.