Entropy, conditional entropy & mutual information
After this page you can compute entropy, conditional entropy and information gain by hand, prove why gain is never negative, and run BestAttribute on a table of data without a calculator.
This chapter gives the splitting criterion decision trees actually use: measure the uncertainty in a node's labels, and pick the attribute that removes the most of it.
- Surprisal — an outcome of probability $p$ costs $\log_2\frac1p$ bits to name.
- Entropy — $H(Y) = \sum_y P(y)\log\frac{1}{P(y)} = -\sum_y P(y)\log P(y)$, the average surprisal. Probabilities are empirical frequencies inside the node.
- Bounds — $0 \le H \le \log_2 k$; $H = 0$ iff the node is pure, $H = \log_2 k$ iff uniform.
- Binary entropy — $H(p) = -p\log_2 p - (1-p)\log_2(1-p)$; $H(0)=H(1)=0$, $H(\tfrac12)=1$ bit, $H(p)=H(1-p)$, and $H''(p) = -\frac{1}{p(1-p)} < 0$ so it is strictly concave.
- Specific conditional entropy — $H(Y\mid W{=}\omega)$: entropy of one child, computed from that child's rows alone.
- Conditional entropy — $H(Y\mid W) = \sum_\omega P(W{=}\omega)H(Y\mid W{=}\omega)$: the size-weighted average over children.
- Mutual information = information gain — $I(Y;W) = H(Y) - H(Y\mid W) \ge 0$, with equality iff $Y \perp W$. Symmetric: $I(Y;W) = H(Y)+H(W)-H(Y,W)$.
- The trap — $H(Y\mid W) \le H(Y)$ always; $H(Y\mid W{=}\omega) \le H(Y)$ is false. A single branch may be more uncertain than the parent.
- BestAttribute — $\argmax_b I(Y;x_b) = \argmin_b H(Y\mid x_b)$, because $H(Y)$ is the same constant for every candidate at a node.
- Hand values — $\log_2 3 = 1.585$, $\log_2 5 = 2.322$, $\log_2 7 = 2.807$; $H(0.5)=1$, $H(0.375)=0.954$, $H(0.25)=0.811$, $H(0.2)=0.722$, $H(0.1)=0.469$.
Everything below is the explanation and the practice. If you are short on time, read this box, then go to the problems.
Where we left off: a criterion that cannot see progress
Chapter 6 ended with a dataset on which splitting on $a$, splitting on $b$, and not splitting at all all produced a training error of exactly $2/8$ — even though split $b$ purified half the dataset and split $a$ accomplished nothing. The diagnosis: training error only asks which label wins the vote in each child, never by how much. A child that goes from a 50/50 coin flip to a 75/25 near-certainty has made enormous progress, but the majority did not flip, so the error count did not move.
We need to measure uncertainty on a continuous scale, so that a split making the labels more predictable gets credit even when no prediction changes yet.
The whole chapter is one sentence: uncertainty about a random variable = the average number of yes/no questions you need to pin it down. Everything else — entropy, conditional entropy, mutual information, information gain — is bookkeeping around that one sentence.
The 20-questions game
There are $128$ students. I choose one uniformly at random — probability $1/128$ each. You may ask any yes/no questions (not only "Is it Alice?" but "Is the surname in the first half of the roster?"), then name the student. How many questions do you need?
The answer is $\mathbf{7}$, and
$$7 \;=\; \log_2 128 \;=\; \log_2 \frac{1}{1/128} \;=\; \log_2 \frac{1}{P(\text{any particular student})}.$$That needs proving in two directions: $7$ questions suffice, and $6$ do not.
Keep a set $C$ of still-possible candidates, initially $|C| = 128$. At each step split $C$ into two halves of equal size and ask "is the chosen student in the first half?" Whichever the answer, you discard exactly half:
$$128 \to 64 \to 32 \to 16 \to 8 \to 4 \to 2 \to 1.$$Seven arrows, because $128 = 2^7$. The strategy never needs more than $7$ and never fewer, so the average is exactly $7$. $\blacksquare$
Fix any strategy that asks at most $k$ yes/no questions. The only information that ever reaches you is the sequence of answers, a string of $k$ bits, and there are at most $2^k$ such strings. Your final guess is a function of that string alone, so the strategy can output at most $2^k$ distinct guesses across all plays.
With $k = 6$: at most $2^6 = 64$ distinct guesses, but $128$ students each with probability $1/128$. At least $128 - 64 = 64$ students are never guessed, so
$$P(\text{you are correct}) \;\le\; \frac{64}{128} \;=\; \frac{1}{2}.$$You fail at least half the time, so $6$ is not enough and $7$ is optimal. $\blacksquare$
The same counting works for any $k$: $k$ yes/no answers distinguish at most $2^k$ outcomes, so distinguishing $n$ equally likely outcomes requires $k \ge \log_2 n$. A yes/no answer is worth one bit, and one bit is exactly the power to halve a set of possibilities — the logarithm is counting halvings.
Why $\log \frac{1}{p}$, and why the logarithm specifically
The chosen student had probability $1/128$ and the answer was $\log_2\frac{1}{1/128}$. So the fundamental quantity is
$$\boxed{\;\text{surprise}(\text{outcome with probability } p) \;=\; \log \frac{1}{p} \;=\; -\log p.\;}$$This is the information content or surprisal: how many bits it takes to name the outcome, equivalently how startled you should be to see it. Two reasons the logarithm — and nothing else — belongs here.
Reason 1: a 1-in-$2^k$ event literally costs $k$ bits. If $p = 2^{-k}$ out of a uniform pool there are $2^k$ equally likely outcomes, and the counting argument says you need exactly $k$ questions. And indeed $\log_2\frac{1}{p} = \log_2 2^k = k$. On powers of two, $\log_2(1/p)$ is not an analogy for "number of questions" — it is the number of questions.
Reason 2: additivity over independent events. Suppose I also flip a fair coin independently; naming the pair should cost $7 + 1 = 8$. Probabilities multiply for independent events, and the logarithm turns multiplication into addition:
$$\log \frac{1}{p \cdot q} \;=\; \log \frac{1}{p} + \log \frac{1}{q}, \qquad \log_2 \frac{1}{\tfrac{1}{128}\cdot\tfrac12} \;=\; \log_2 256 \;=\; 8 \;=\; 7 + 1. \quad\checkmark$$Averaging: the expected number of questions
Drop the uniformity. With $k$ outcomes of probabilities $p_1,\dots,p_k$, outcome $i$ costs $\log\frac1{p_i}$ questions and occurs a $p_i$ fraction of the time, so the expected number of questions is the probability-weighted average of the surprisals:
$$\text{Answer} \;=\; \sum_{i=1}^{k} p_i \log \frac{1}{p_i}.$$Sanity check in the uniform case, $p_i = 1/128$:
$$\sum_{i=1}^{128} \frac{1}{128}\log_2 128 \;=\; \log_2 128 \cdot \underbrace{\sum_{i=1}^{128}\frac{1}{128}}_{=\,1} \;=\; 7. \quad\checkmark$$The notes' non-uniform example, computed in full
The notes change the distribution to
$$p_1 = \tfrac14, \qquad p_2 = p_3 = \cdots = p_7 = \tfrac18, \qquad p_8 = \cdots = p_{128} = 0,$$with the convention $0 \cdot \log\frac10 := 0$, and assert the answer is $11/4$.
It is a distribution: $\tfrac14 + 6 \cdot \tfrac18 = \tfrac28 + \tfrac68 = 1$ ✓ (students $2$ through $7$ is six students, not seven). Surprisals: $\log_2\frac{1}{1/4} = \log_2 4 = 2$ bits for student 1, $\log_2\frac{1}{1/8} = \log_2 8 = 3$ bits each for students 2–7, and $0$ for students 8–128 by the convention. So
$$\sum_i p_i \log_2\frac{1}{p_i} \;=\; \underbrace{\tfrac14 \cdot \log_2 4}_{\text{student 1}} \;+\; \underbrace{6 \cdot \tfrac18 \cdot \log_2 8}_{\text{students 2–7}} \;+\; \underbrace{121 \cdot 0}_{\text{students 8–128}}$$ $$= \tfrac14 \cdot 2 \;+\; 6 \cdot \tfrac38 \;=\; \tfrac12 \;+\; \tfrac{18}{8} \;=\; \tfrac24 + \tfrac94 \;=\; \tfrac{11}{4} \;=\; 2.75 \text{ questions on average.} \quad\checkmark$$The $0\log\frac10 := 0$ convention. An outcome that never happens should contribute nothing to the average. This is not a fudge but a limit, so the definition keeps $H$ continuous — the surprisal $\log\frac10$ is infinite, but it is multiplied by a probability heading to zero faster, and zero wins:
$$\lim_{p\to 0^+} p \log_2 \frac{1}{p} \;=\; \lim_{p\to 0^+} \frac{-\log_2 p}{1/p} \;\overset{\text{L'Hôpital}}{=}\; \lim_{p\to 0^+} \frac{-1/(p\ln 2)}{-1/p^2} \;=\; \lim_{p\to 0^+} \frac{p}{\ln 2} \;=\; 0.$$"So entropy is the number of questions." Only when every $p_i$ is a power of two — as here, where asking "is it in $\{1,2,3\}$?" (mass $\tfrac14+\tfrac18+\tfrac18 = \tfrac12$, an exact half) and then halving the surviving mass costs student 1 two questions and students 2–7 three, for $\tfrac14(2) + 6\cdot\tfrac18(3) = \tfrac{11}{4}$ exactly. In general $\log_2(1/p_i)$ is not an integer, and you cannot ask $1.58$ questions.
What is true in general: entropy is a lower bound, reachable to within one question by rounding each ideal length up to $\lceil\log_2(1/p_i)\rceil$:
$$H \;\le\; L^\star \;\lt\; H + 1.$$Three equally likely outcomes have $H = \log_2 3 \approx 1.585$ bits, but any real strategy costs $\tfrac13(1) + \tfrac13(2) + \tfrac13(2) = \tfrac53 \approx 1.667$ questions; the gap is the rounding. For decision trees none of this matters — we only ever compare entropies, never cash them in for questions.
I pick one of four objects with probabilities $p_1 = \tfrac12$, $p_2 = \tfrac14$, $p_3 = \tfrac18$, $p_4 = \tfrac18$.
(a) Compute the entropy. (b) Design a yes/no question strategy and verify its expected cost equals the entropy. (c) Compare against the "just ask is it object 1? is it object 2? in order" strategy.
Step 1 — Write down the surprisal of each outcome
$\log_2\frac{1}{1/2} = \log_2 2 = 1$; $\log_2\frac{1}{1/4} = \log_2 4 = 2$; $\log_2\frac{1}{1/8} = \log_2 8 = 3$ (twice).
All powers of two, so we should expect a strategy to match the bound exactly.
Step 2 — Take the weighted average
Check it is a distribution first: $\tfrac12+\tfrac14+\tfrac18+\tfrac18 = \tfrac48+\tfrac28+\tfrac18+\tfrac18 = 1$ ✓.
Step 3 — Build the strategy by splitting the mass in half each time
Q1: "Is it object 1?" Mass on each side: $\tfrac12$ vs $\tfrac12$ — a perfect half. Yes → done in $1$.
Q2 (given no): "Is it object 2?" Remaining mass is $\tfrac14+\tfrac18+\tfrac18 = \tfrac12$, and object 2 holds $\tfrac14$ of it — half again ✓. Yes → done in $2$.
Q3 (given no again): "Is it object 3?" Two outcomes of mass $\tfrac18$ each — half ✓. Either way, done in $3$.
Cost: $\tfrac12(1)+\tfrac14(2)+\tfrac18(3)+\tfrac18(3) = 1.75$. Identical to $H$. ✓
The rule that made it work: every question split the remaining probability mass exactly in half, so every answer carried a full bit of information. That is the general recipe.
Answer & the takeaway
(a) $H = 7/4 = 1.75$ bits. (b) The strategy above costs exactly $1.75$. (c) Here the naive "is it object 1? is it object 2? …" strategy is the optimal one, because the probabilities were arranged to halve at each step. Change the distribution to uniform ($\tfrac14$ each) and the naive strategy costs $\tfrac14(1)+\tfrac14(2)+\tfrac14(3)+\tfrac14(3) = 2.25$, while balanced binary search costs $2 = \log_2 4 = H$.
Takeaway: low entropy = one outcome hogs the mass = you can find it fast. High entropy = the mass is spread out = every question buys you less. That is exactly the property we want from a splitting criterion.
Entropy: the definition and its properties
For a discrete distribution $p = (p_1, \dots, p_k)$ over $k$ outcomes, the entropy is
$$H(p) \;=\; \sum_{i=1}^{k} p_i \log \frac{1}{p_i} \;=\; -\sum_{i=1}^{k} p_i \log p_i,$$with the convention $0\log\frac10 := 0$. Every symbol:
- $k$ — the number of possible outcomes (for us: the number of class labels).
- $p_i$ — the probability of outcome $i$; in a decision-tree node, the fraction of examples in that node carrying label $i$.
- $\log\frac{1}{p_i}$ — the surprisal of outcome $i$: how many bits to name it.
- The sum is an expectation, $H(p) = \mathbb{E}_{i \sim p}\!\left[\log \frac{1}{p_i}\right]$ — the average surprisal. The two forms agree because $\log\frac1p = -\log p$; the $-\sum p\log p$ form is the one you will see on exams.
Units. With $\log_2$, bits; with $\ln$, nats ($1$ nat $\approx 1.4427$ bits); with $\log_{10}$, bans. The base only rescales by a constant, so it never changes which attribute wins a split. Use $\log_2$ in this course.
Property 1: $H(p) \ge 0$
Take any term $p_i \log\frac{1}{p_i}$. Since $p_i \in [0,1]$ we have $\frac{1}{p_i} \ge 1$, hence $\log\frac{1}{p_i} \ge \log 1 = 0$. The term is a product of two non-negative numbers, so it is $\ge 0$, and a sum of non-negative terms is non-negative. $\blacksquare$
You can never need a negative number of questions. Entropy has no upper limit in general (many outcomes ⟹ large $H$), but it has a hard floor at zero.
Property 2: $H(p) = 0$ if and only if the distribution is deterministic
($\Leftarrow$) If some $p_j = 1$ and all others are $0$: the $j$ term is $1 \cdot \log\frac11 = 0$, and every other term is $0\log\frac10 = 0$ by convention. So $H = 0$.
($\Rightarrow$) Suppose $H = 0$. By Property 1 every term is $\ge 0$, and a sum of non-negative numbers is zero only if every term is zero. So $p_i \log\frac{1}{p_i} = 0$ for each $i$, forcing $p_i = 0$ or $\log\frac1{p_i}=0 \Rightarrow p_i = 1$. Every $p_i \in \{0,1\}$, and since they sum to $1$, exactly one is $1$. $\blacksquare$
Decision-tree meaning: $H = 0$ ⟺ the node is pure. Zero uncertainty, and the recursion stops.
Property 3: $H(p) \le \log k$, with equality exactly for the uniform distribution
$\log$ is concave (second derivative $-1/(x^2\ln 2) < 0$ on $x>0$), and Jensen for concave $f$ says $\mathbb{E}[f(Z)] \le f(\mathbb{E}[Z])$. Apply it with $Z = 1/p_i$, $i \sim p$, summing only over the $m \le k$ indices with $p_i > 0$:
$$H(p) = \mathbb{E}\!\left[\log \frac{1}{p_i}\right] \;\le\; \log\left(\mathbb{E}\!\left[\frac{1}{p_i}\right]\right) = \log\left(\sum_{i : p_i > 0} p_i \cdot \frac{1}{p_i}\right) = \log\left(\sum_{i: p_i>0} 1\right) = \log m \;\le\; \log k.$$Step by step: definition of $H$ as an expectation; Jensen, legal because $\log$ is concave; expand the expectation as a sum, the $p_i$ cancels; count the surviving terms.
Equality. $\log$ is strictly concave, so Jensen is tight only when $1/p_i$ is constant over the support — a uniform distribution — and the last inequality is tight only when $m = k$. So $H = \log k$ exactly when $p$ is uniform over all $k$ outcomes. $\blacksquare$
Meaning: maximum uncertainty is "all outcomes equally likely", costing $\log_2 k$ questions — the 20-questions answer, now as a theorem. For $k=2$ the cap is $1$ bit.
Property 4: entropy measures uncertainty
More uncertainty $\iff$ more questions needed $\iff$ higher entropy. The scale runs from $0$ (a pure node) to $\log_2 k$ (a perfectly balanced node), graded continuously — precisely what training error refused to do.
The binary entropy function
Almost every hand computation in this course has two labels, so learn one function cold. Write $p$ for the probability of label "1"; label "0" then has probability $1-p$ and
$$H(p) \;=\; -p\log_2 p - (1-p)\log_2(1-p).$$Notation warning: $H(p)$ here takes a single number $p \in [0,1]$ and means the entropy of $(p, 1-p)$. Elsewhere $H(\cdot)$ takes a random variable. Both are standard; context disambiguates.
The three facts to memorise, with their one-line reasons
| Fact | Why |
|---|---|
| $H(0) = H(1) = 0$ | Deterministic node (Property 2). Both terms vanish under the $0\log\frac10=0$ convention. |
| $H(1/2) = 1$ bit | $-\tfrac12\log_2\tfrac12 - \tfrac12\log_2\tfrac12 = \tfrac12(1)+\tfrac12(1) = 1$. The maximum, by Property 3 with $k=2$. |
| $H(p) = H(1-p)$ | Swapping $p \leftrightarrow 1-p$ swaps the two terms of the sum; addition is commutative. |
Work in nats ($\ln$) for cleaner derivatives; the base only multiplies by a positive constant, which cannot change concavity. With $H(p) = -p\ln p - (1-p)\ln(1-p)$:
$$H'(p) = -\ln p - 1 + \ln(1-p) + 1 = \ln\frac{1-p}{p},$$ $$H''(p) = \frac{d}{dp}\Big[\ln(1-p) - \ln p\Big] = \frac{-1}{1-p} - \frac{1}{p} = -\frac{1}{p(1-p)} \;\lt\; 0 \quad\text{for } p \in (0,1).$$Strictly negative second derivative ⟹ strictly concave. Also $H'(1/2) = \ln 1 = 0$, confirming the maximum sits at $p = 1/2$. $\blacksquare$
The notes' example: $P(Y{=}1) = 0.4$, $P(Y{=}0) = 0.6$.
$$H(Y) = 0.4\log_2\frac{1}{0.4} + 0.6\log_2\frac{1}{0.6} = 0.4\log_2 2.5 + 0.6\log_2 1.\overline{6}.$$With $\log_2 2.5 = \log_2 5 - 1 = 1.321928$ and $\log_2 \tfrac53 = 2.321928 - 1.584963 = 0.736966$:
$$H(Y) = 0.4(1.321928) + 0.6(0.736966) = 0.528771 + 0.442179 = \mathbf{0.970951} \text{ bits}.$$Round to $0.971$ and memorise it — a 40/60 split is the most common number on 07-280 problem sets, and it is only $0.029$ bits below the maximum.
Entropy of the labels inside a node
The translation into decision-tree language. Let $S$ be the examples at a node and $\mathcal{Y}$ the possible labels. Define the label distribution empirically — by counting:
$$P(Y = y) \;=\; \frac{\#\{\text{examples in } S \text{ with label } y\}}{|S|}.$$The entropy of the labels at a node $S$ is
$$H(Y) \;=\; \sum_{y \in \mathcal{Y}} P(Y=y)\,\log\frac{1}{P(Y=y)},$$where $Y$ is the label of an example drawn uniformly at random from $S$, $y$ ranges over the possible labels ($\{0,1\}$ for us), and $P(Y=y)$ is the fraction of $S$ carrying label $y$. For the $40\%$/$60\%$ node above, $H(Y) = 0.971$ bits.
$H(Y)$ does not depend on $|S|$: $4$ ones and $6$ zeros has the same entropy as $400$ and $600$. Size enters later, through the weights in conditional entropy.
These probabilities are empirical frequencies computed from the node's own examples, not a prior belief and not the frequencies in the full dataset. When you recurse into a child, recompute from scratch using only the examples that reached it. Forgetting to recompute is the single most common arithmetic error on this material.
Specific conditional entropy and conditional entropy
To score a split we need to know how uncertain the labels are after it. Let $W$ be the attribute we split on (so $W = x_b$), with $\omega$ ranging over its values ($0$ and $1$ for binary attributes).
Specific conditional entropy — the entropy of one child
Two annotations from the notes, and both are the whole point:
- "The conditioning $\mid W = \omega$ defines left or right child node." Fixing $\omega$ is literally walking down one branch: $H(Y \mid x_b = 1)$ is the left child's entropy, $H(Y \mid x_b = 0)$ the right child's.
- $P(Y{=}y \mid W{=}\omega) = \dfrac{\#\{\text{examples with } W=\omega \text{ and label } y\}}{\#\{\text{examples with } W=\omega\}}$ — count within the child, divide by the child's size.
It is called specific because it is pinned to one value $\omega$: a single number per child, not an average. Computationally it is nothing new — throw away every example whose attribute isn't $\omega$, recount, apply $H$.
Conditional entropy — the weighted average over children
where $P(W=\omega)$ is the fraction of $S$ landing in child $\omega$ — for a binary attribute $\frac{|S_\omega|}{|S|}$, so
$$H(Y \mid W) = \frac{|S_1|}{|S|}H(Y \mid W{=}1) + \frac{|S_0|}{|S|}H(Y \mid W{=}0).$$In the notes' words: "the average entropy across the child nodes (after the current node is split)."
Take a node of $100$ examples, $50$ of each label ($H(Y) = 1$ bit), and an attribute that isolates a single example into the left child and dumps the other $99$ right. The left child is pure, $H(Y\mid W{=}1) = 0$. Averaged naively you would get $\tfrac12(0) + \tfrac12(0.99993) = 0.49996$ bits and conclude this useless split halved your uncertainty.
With the correct weights: $\tfrac{1}{100}(0) + \tfrac{99}{100}(0.99993) = 0.98993$ bits, a gain of $0.01007$ bits — the truth, since it resolved one example out of a hundred. The weight $P(W=\omega)$ is what stops a split that isolates a single point from looking good.
Mutual information = information gain
The mutual information between the label $Y$ and the attribute $W$ is
$$I(Y; W) \;=\; H(Y) - H(Y \mid W).$$In the notes' words: "amount of reduction in entropy (before vs. after splitting)." The decision-tree literature calls the same quantity the information gain. Units: bits. Reading: "splitting on $W$ saves you $I(Y;W)$ yes/no questions, on average, when you later have to guess the label."
Theorem: $I(Y;W) \ge 0$, i.e. $H(Y \mid W) \le H(Y)$
Step 1 — the parent's distribution is a mixture of the children's. By the law of total probability, for every label $y$,
$$P(Y = y) \;=\; \sum_{\omega} P(W=\omega)\, P(Y = y \mid W = \omega).$$As vectors over $y$: the parent distribution $P(Y)$ is the convex combination of the child distributions $P(Y \mid W=\omega)$ with weights $P(W=\omega)$. Pooling the children back together is the parent.
Step 2 — $H$ is concave as a function of the distribution. $H(p) = \sum_i p_i\log\frac1{p_i}$ is a sum of terms $-p_i\log p_i$, each concave in $p_i$ (second derivative $-1/(p_i\ln 2) < 0$), and a sum of concave functions is concave.
Step 3 — Jensen for a concave $f$: $f(\sum_j \lambda_j z_j) \ge \sum_j \lambda_j f(z_j)$. With $f = H$, $\lambda_\omega = P(W=\omega)$, $z_\omega = P(Y \mid W=\omega)$:
$$H(Y) = H\!\left(\sum_\omega P(W{=}\omega)\,P(Y\mid W{=}\omega)\right) \;\ge\; \sum_\omega P(W{=}\omega)\, H\big(P(Y \mid W{=}\omega)\big) \;=\; H(Y \mid W).$$The left side is $H(Y)$ by Step 1, the right side is the definition of conditional entropy. Therefore $I(Y;W) \ge 0$. $\blacksquare$
Equality condition. $H$ is strictly concave, so Jensen is tight only when all $z_\omega$ with positive weight are identical: $P(Y \mid W = \omega) = P(Y)$ for every $\omega$, i.e. $Y$ and $W$ are independent. So
$$H(Y \mid W) = H(Y) \iff I(Y;W) = 0 \iff Y \perp W.$$Why can't information hurt on average? Because you are free to ignore it: any strategy that doesn't look at $W$ is still available after you learn $W$. In tree terms, "predict the parent's majority in both children" is one of the options available after splitting, so splitting and predicting each child's majority is at least as accurate.
The exam trap: a specific conditional entropy CAN exceed $H(Y)$
The theorem says $H(Y \mid W) \le H(Y)$ — the weighted average over children never exceeds the parent. It does not say $H(Y \mid W = \omega) \le H(Y)$ for each individual $\omega$. That statement is false, and it is examined constantly.
A particular branch can leave you more confused than you started. Learning "the patient's test came back inconclusive" genuinely increases your uncertainty about the diagnosis; learning "the test was positive" decreases it a lot. On average you win, but not in every branch.
A node with $|S| = 10$: $9$ labelled "0" and $1$ labelled "1", split by $W$ as follows.
| Node | $n$ | zeros | ones | $P(Y{=}1)$ | entropy | weight |
|---|---|---|---|---|---|---|
| parent $S$ | 10 | 9 | 1 | 0.1 | $H(Y) = 0.469$ | — |
| child $W{=}1$ | 2 | 1 | 1 | 0.5 | $H(Y\mid W{=}1) = 1.000$ | $2/10 = 0.2$ |
| child $W{=}0$ | 8 | 8 | 0 | 0.0 | $H(Y\mid W{=}0) = 0.000$ | $8/10 = 0.8$ |
Parent. $H(Y) = -0.9\log_2 0.9 - 0.1\log_2 0.1 = 0.9(0.152003) + 0.1(3.321928) = 0.136803 + 0.332193 = \mathbf{0.468996}$. The child $W{=}1$ has one of each label, so $H(Y\mid W{=}1) = \mathbf{1.000}$ bit; the child $W{=}0$ is pure, so $\mathbf{0.000}$.
$1.000 \;>\; 0.469$ — the specific conditional entropy strictly exceeds the parent's entropy.
The average, however, obeys the theorem:
$$H(Y \mid W) = 0.2(1.000) + 0.8(0.000) = \mathbf{0.200} \;\le\; 0.469 = H(Y),$$ $$I(Y;W) = 0.468996 - 0.200000 = \mathbf{0.268996} \;>\; 0. \quad\checkmark$$The branch $W{=}1$ made things worse ($0.469 \to 1.000$), but only $20\%$ of the examples go there while $80\%$ go to a branch that became perfectly certain.
Symmetry: $I(Y;W) = I(W;Y)$
Chain rule for entropy: $H(Y, W) = H(W) + H(Y \mid W)$. Derivation, using $P(y,w) = P(w)P(y\mid w)$:
$$H(Y,W) = -\sum_{y,w} P(y,w)\log P(y,w) = -\sum_{y,w} P(w)P(y\mid w)\big[\log P(w) + \log P(y\mid w)\big]$$ $$= -\sum_{w} P(w)\log P(w)\underbrace{\sum_y P(y\mid w)}_{=1} \;-\; \sum_w P(w)\underbrace{\Big[\sum_y P(y\mid w)\log P(y \mid w)\Big]}_{=\,-H(Y\mid W=w)} \;=\; H(W) + H(Y\mid W).$$Now substitute into the definition of mutual information:
$$I(Y;W) = H(Y) - H(Y\mid W) = H(Y) - \big[H(Y,W) - H(W)\big] = H(Y) + H(W) - H(Y,W).$$That expression is visibly symmetric in $Y$ and $W$ — swapping the two names leaves it unchanged. Hence $I(Y;W) = I(W;Y)$. $\blacksquare$
Symmetry is genuinely surprising: "how much does knowing the attribute tell me about the label" equals "how much does knowing the label tell me about the attribute". Information is a shared quantity, not a directional flow — hence mutual information.
beyond syllabus Equivalently $I(Y;W) = \sum_{y,w} P(y,w)\log\frac{P(y,w)}{P(y)P(w)}$, the KL divergence between the joint and the product of the marginals.
BestAttribute, version 2: maximise mutual information
We can now fill in the missing subroutine from Chapter 6's DT algorithm:
function BestAttribute(S, A):
H_Y <- entropy of the labels in S # one number, fixed
best <- none; bestI <- -infinity
for each attribute b in A:
S1 <- {(x,y) in S : x_b = 1}
S0 <- {(x,y) in S : x_b = 0}
H_cond <- (|S1|/|S|) * entropy(labels of S1)
+ (|S0|/|S|) * entropy(labels of S0)
I <- H_Y - H_cond # information gain
if I > bestI: bestI <- I; best <- b
return bestThe notes state the rule as: "BestAttribute chooses the attribute that maximizes mutual information (equivalently, minimizes conditional entropy)." Both forms:
$$b^\star \;=\; \argmax_{b \in A} \; I(Y; x_b) \;=\; \argmax_{b \in A} \big[H(Y) - H(Y \mid x_b)\big] \;=\; \argmin_{b \in A} \; H(Y \mid x_b).$$$H(Y)$ is computed from the labels in $S$ alone. It does not mention $b$ at all — it is the same constant for every candidate attribute at this node. Subtracting a constant from a collection of numbers reverses nothing and shifts everything equally, so
$$\argmax_b \big[\underbrace{H(Y)}_{\text{const}} - H(Y\mid x_b)\big] = \argmax_b \big[-H(Y\mid x_b)\big] = \argmin_b H(Y\mid x_b). \quad\blacksquare$$Practical consequence: at a given node you may skip computing $H(Y)$ entirely and just rank the conditional entropies, smallest wins. Compute $H(Y)$ only when you want to report the gain (or when comparing across nodes, where $H(Y)$ does change).
$H(Y)$ is constant within one node, not across the tree. Each recursive call recomputes it from that node's examples. Gains at different nodes are not directly comparable — a gain of $0.3$ bits in a node holding $4$ examples is worth far less than $0.3$ bits in a node holding $400$.
A fully worked split selection
The poll dataset from Chapter 6, solved there under training error and now solved properly.
| $i$ | $y$ | $x_1$ | $x_2$ | $x_3$ |
|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 0 |
| 2 | 0 | 1 | 0 | 1 |
| 3 | 0 | 1 | 0 | 0 |
| 4 | 1 | 0 | 0 | 1 |
| 5 | 1 | 1 | 1 | 0 |
| 6 | 1 | 1 | 1 | 1 |
| 7 | 1 | 1 | 1 | 0 |
| 8 | 1 | 1 | 1 | 1 |
Reading the table: $i$ indexes the training example, $y \in \{0,1\}$ is its label, and $x_1, x_2, x_3 \in \{0,1\}$ are its three binary attributes.
Step 0 — the root entropy $H(Y)$
Labels down the $y$ column: $0,0,0,1,1,1,1,1$. That is $3$ zeros and $5$ ones out of $8$:
$$P(Y{=}0) = \tfrac38 = 0.375, \qquad P(Y{=}1) = \tfrac58 = 0.625.$$ $$\log_2\tfrac38 = \log_2 3 - \log_2 8 = 1.584963 - 3 = -1.415037,$$ $$\log_2\tfrac58 = \log_2 5 - \log_2 8 = 2.321928 - 3 = -0.678072,$$ $$H(Y) = 0.375(1.415037) + 0.625(0.678072) = 0.530639 + 0.423795 = \mathbf{0.954434}\text{ bits}.$$Sanity: a $3$-to-$5$ node should be close to, but below, the maximum of $1$ bit. ✓ (It is the $3/8 : 5/8$ row of the lookup table below.)
Step 1 — attribute $x_1$
$x_1 = 1$ for rows $1,2,3,5,6,7,8$ and $x_1 = 0$ only for row $4$.
| branch | rows | labels | $n$ | 0s | 1s | weight |
|---|---|---|---|---|---|---|
| $x_1 = 1$ | 1,2,3,5,6,7,8 | $0,0,0,1,1,1,1$ | 7 | 3 | 4 | $7/8$ |
| $x_1 = 0$ | 4 | $1$ | 1 | 0 | 1 | $1/8$ |
Tiny gain. The split peeled off one example and left the other seven almost as confused as the parent — in fact $0.985 \gt 0.954$, another instance of a specific conditional entropy exceeding the parent's.
Step 2 — attribute $x_2$
$x_2 = 1$ for rows $5,6,7,8$; $x_2 = 0$ for rows $1,2,3,4$.
| branch | rows | labels | $n$ | 0s | 1s | weight |
|---|---|---|---|---|---|---|
| $x_2 = 1$ | 5,6,7,8 | $1,1,1,1$ | 4 | 0 | 4 | $4/8$ |
| $x_2 = 0$ | 1,2,3,4 | $0,0,0,1$ | 4 | 3 | 1 | $4/8$ |
($\log_2\tfrac43 = 2 - \log_2 3 = 2 - 1.584963 = 0.415037$.) This is the split drawn in Figure 2.
Step 3 — attribute $x_3$
$x_3 = 1$ for rows $2,4,6,8$; $x_3 = 0$ for rows $1,3,5,7$.
| branch | rows | labels | $n$ | 0s | 1s | weight |
|---|---|---|---|---|---|---|
| $x_3 = 1$ | 2,4,6,8 | $0,1,1,1$ | 4 | 1 | 3 | $4/8$ |
| $x_3 = 0$ | 1,3,5,7 | $0,0,1,1$ | 4 | 2 | 2 | $4/8$ |
Step 4 — the scoreboard and the winner
| attribute | $H(Y\mid \cdot{=}1)$ | $H(Y\mid \cdot{=}0)$ | weights | $H(Y\mid\cdot)$ | $I(Y;\cdot)$ | training error |
|---|---|---|---|---|---|---|
| — (no split) | $H(Y) = 0.954434$ | — | — | $3/8 = 0.375$ | ||
| $x_1$ | $0.985228$ | $0.000000$ | $\tfrac78,\ \tfrac18$ | $0.862075$ | $0.092359$ | $3/8 = 0.375$ |
| $\mathbf{x_2}$ | $0.000000$ | $0.811278$ | $\tfrac48,\ \tfrac48$ | $\mathbf{0.405639}$ | $\mathbf{0.548795}$ | $1/8 = 0.125$ |
| $x_3$ | $0.811278$ | $1.000000$ | $\tfrac48,\ \tfrac48$ | $0.905639$ | $0.048795$ | $3/8 = 0.375$ |
Equivalently $\argmin_b H(Y\mid x_b) = x_2$ with $0.405639$ — the same winner, as the equivalence theorem guarantees. Notice the two columns rank the attributes identically ($x_2 \succ x_1 \succ x_3$ both ways), because they differ only by the constant $0.954434$.
So the root of the tree asks "Is $x_2 = 1$?" — which is exactly the tree the notes draw ("Is $x_2 = 0$?", the same question with the branches swapped).
Step 5 — contrast with the training-error criterion
Under training error, each split scores mistakes made by majority vote in each child:
- $x_1$: the $x_1{=}1$ child is $3$ zeros, $4$ ones → vote $1$ → $3$ mistakes; the $x_1{=}0$ child is pure → $0$. Total $3/8$.
- $x_2$: $x_2{=}1$ is pure → $0$; $x_2{=}0$ is $3$ zeros, $1$ one → vote $0$ → $1$ mistake. Total $1/8$.
- $x_3$: $x_3{=}1$ is $1$ zero, $3$ ones → vote $1$ → $1$ mistake; $x_3{=}0$ is a $2$–$2$ tie → $2$ mistakes. Total $3/8$.
- No split at all: vote $1$ → $3$ mistakes. $3/8$.
Training error gets the winner right here ($x_2$, $1/8$), but $x_1$, $x_3$ and doing nothing all score $3/8$ — a three-way dead tie, including a tie with "don't split".
Mutual information separates them: $I(Y;x_1) = 0.0924$ versus $I(Y;x_3) = 0.0488$, and both are strictly better than not splitting. Error rate cannot express any of that, because the majority label did not flip. On a dataset where the best attribute is one of the tied ones, error rate picks arbitrarily and the greedy algorithm goes down the wrong path.
Interactive: the entropy calculator
Set the class counts in the two children; the parent is their union, so its counts follow automatically. Watch $I(Y;W)$ and try to make it negative. You cannot.
ID3, C4.5, and the bias toward many-valued attributes
beyond syllabus The algorithm above is ID3 (Quinlan, 1986); C4.5 adds real-valued thresholds, missing values, pruning, and a fix for one bug — information gain prefers attributes with many values, since an attribute as fine as a row number gives all-pure children and so the maximal gain $H(Y)$ while memorising the training set. The fix is the gain ratio, which charges the attribute for its own entropy:
$$\text{GainRatio}(Y;W) = \frac{I(Y;W)}{H(W)}, \qquad H(W) = \sum_\omega P(W{=}\omega)\log\frac{1}{P(W{=}\omega)}.$$On the 8-row dataset, a row-number attribute scores $0.954434/3 = 0.318$ against $x_2$'s $0.548795/1 = 0.549$, so $x_2$ wins again. CART instead uses Gini impurity $\sum_y p_y(1-p_y)$, which the notes mention and do not discuss; it behaves almost identically to entropy and needs no logarithm.
The hand-computation lookup table
Exams are computed by hand, and every entropy you will need on a small dataset is built from a handful of logarithms and two-class entropies. Learn these and you will never stall.
| $n$ | $\log_2 n$ |
|---|---|
| 2 | 1.000000 |
| 3 | 1.584963 |
| 4 | 2.000000 |
| 5 | 2.321928 |
| 6 | 2.584963 |
| 7 | 2.807355 |
| 8 | 3.000000 |
| 9 | 3.169925 |
| 10 | 3.321928 |
Everything else follows from $\log_2\frac{a}{b} = \log_2 a - \log_2 b$ and $\log_2(2n) = 1 + \log_2 n$. E.g. $\log_2 12 = \log_2 4 + \log_2 3 = 3.584963$.
| split | $p$ | $H$ (bits) |
|---|---|---|
| $1/2 : 1/2$ | 0.500 | 1.000 |
| $2/5 : 3/5$ | 0.400 | 0.971 |
| $3/8 : 5/8$ | 0.375 | 0.954 |
| $1/3 : 2/3$ | 0.333 | 0.918 |
| $1/4 : 3/4$ | 0.250 | 0.811 |
| $1/5 : 4/5$ | 0.200 | 0.722 |
| $1/8 : 7/8$ | 0.125 | 0.544 |
| $0 : 1$ | 0.000 | 0.000 |
Symmetry gives you the mirror rows for free: $H(0.6)=H(0.4)=0.971$, $H(0.625)=H(0.375)=0.954$, $H(0.75)=H(0.25)=0.811$, $H(0.875)=H(0.125)=0.544$.
Three more that come up often, derived from the table: $H(3/7) = 0.985$ (the $x_1$ branch above), $H(1/10) = 0.469$ (the counterexample above), $H(1/16) = 0.337$.
Entropy falls slowly at first: $50/50 \to 40/60$ buys $0.029$ bits, $40/60 \to 25/75$ buys $0.160$, $12.5/87.5 \to$ pure buys $0.544$. Entropy rewards finishing the job far more than starting it — exactly what you want from a criterion trying to build small trees.
Guided problems
BestAttribute from scratch on a new datasetShould you go for a run? $y = 1$ means "go". Three binary attributes: $x_1$ = it is raining, $x_2$ = it is cold, $x_3$ = you are busy.
| $i$ | $y$ | $x_1$ rain | $x_2$ cold | $x_3$ busy |
|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 0 |
| 2 | 1 | 0 | 0 | 1 |
| 3 | 0 | 1 | 0 | 0 |
| 4 | 0 | 1 | 1 | 1 |
| 5 | 1 | 0 | 1 | 0 |
| 6 | 0 | 1 | 0 | 1 |
| 7 | 1 | 0 | 1 | 1 |
| 8 | 0 | 0 | 1 | 1 |
Compute $H(Y)$, then for each attribute both specific conditional entropies, the conditional entropy, and the mutual information. Declare the winner. Then compute each attribute's training error and compare what the two criteria tell you. Work it out before opening the steps.
Step 1 — the root entropy $H(Y)$
Labels: $1,1,0,0,1,0,1,0$ — four ones and four zeros out of eight.
$$P(Y{=}1) = P(Y{=}0) = \tfrac12 \;\Longrightarrow\; H(Y) = \tfrac12\log_2 2 + \tfrac12 \log_2 2 = \mathbf{1.000000}\text{ bit}.$$A perfectly balanced root — maximum uncertainty for two classes (Property 3 with $k=2$). Convenient: every conditional entropy we compute is directly the gain subtracted from $1$.
Step 2 — attribute $x_1$ (raining)
$x_1{=}1$: rows $3, 4, 6$ → labels $0,0,0$. $n=3$, pure. $x_1{=}0$: rows $1,2,5,7,8$ → labels $1,1,1,1,0$. $n=5$, one zero and four ones.
$$H(Y\mid x_1{=}1) = \mathbf{0.000000}.$$ $$H(Y\mid x_1{=}0) = \tfrac15\log_2 5 + \tfrac45\log_2\tfrac54 = 0.2(2.321928) + 0.8(0.321928) = 0.464386 + 0.257542 = \mathbf{0.721928}.$$($\log_2\tfrac54 = 2.321928 - 2 = 0.321928$; and this is the $1/5 : 4/5$ row of the lookup table ✓.)
$$H(Y\mid x_1) = \tfrac38(0.000000) + \tfrac58(0.721928) = 0 + 0.451205 = \mathbf{0.451205}.$$ $$I(Y;x_1) = 1.000000 - 0.451205 = \mathbf{0.548795}\text{ bits}.$$Step 3 — attribute $x_2$ (cold)
$x_2{=}1$: rows $4,5,7,8$ → labels $0,1,1,0$. $n=4$, two of each. $x_2{=}0$: rows $1,2,3,6$ → labels $1,1,0,0$. $n=4$, two of each.
$$H(Y\mid x_2{=}1) = \mathbf{1.000000}, \qquad H(Y\mid x_2{=}0) = \mathbf{1.000000}.$$ $$H(Y\mid x_2) = \tfrac12(1) + \tfrac12(1) = \mathbf{1.000000}.$$ $$I(Y;x_2) = 1.000000 - 1.000000 = \mathbf{0.000000}\text{ bits}.$$Exactly zero — and by the equality condition of the theorem that means $Y$ and $x_2$ are statistically independent in this dataset. Check it directly: both children have label distribution $(\tfrac12,\tfrac12)$, identical to the parent's. Knowing whether it is cold tells you literally nothing about whether you go running.
Step 4 — attribute $x_3$ (busy)
$x_3{=}1$: rows $2,4,6,7,8$ → labels $1,0,0,1,0$. $n=5$, three zeros and two ones. $x_3{=}0$: rows $1,3,5$ → labels $1,0,1$. $n=3$, one zero and two ones.
$$H(Y\mid x_3{=}1) = \tfrac25\log_2\tfrac52 + \tfrac35\log_2\tfrac53 = 0.4(1.321928) + 0.6(0.736966) = 0.528771 + 0.442180 = \mathbf{0.970951}.$$ $$H(Y\mid x_3{=}0) = \tfrac13\log_2 3 + \tfrac23\log_2\tfrac32 = 0.333333(1.584963) + 0.666667(0.584963) = 0.528321 + 0.389975 = \mathbf{0.918296}.$$ $$H(Y\mid x_3) = \tfrac58(0.970951) + \tfrac38(0.918296) = 0.606844 + 0.344361 = \mathbf{0.951205}.$$ $$I(Y;x_3) = 1.000000 - 0.951205 = \mathbf{0.048795}\text{ bits}.$$(Both child entropies are lookup-table rows: $2/5:3/5 = 0.971$ and $1/3:2/3 = 0.918$ ✓.)
Step 5 — the scoreboard, and the training-error comparison
| attribute | $H(Y\mid\cdot)$ | $I(Y;\cdot)$ | training error |
|---|---|---|---|
| — (no split) | $1.000000$ | — | $4/8 = 0.500$ |
| $\mathbf{x_1}$ rain | $\mathbf{0.451205}$ | $\mathbf{0.548795}$ | $1/8 = 0.125$ |
| $x_2$ cold | $1.000000$ | $0.000000$ | $4/8 = 0.500$ |
| $x_3$ busy | $0.951205$ | $0.048795$ | $3/8 = 0.375$ |
Training errors, for the record: $x_1$ — pure child $0$ mistakes, the other child votes $1$ and misses row 8 → $1/8$. $x_2$ — both children are $2$–$2$ ties → $2+2 = 4/8$, no better than not splitting. $x_3$ — the $x_3{=}1$ child votes $0$ and misses rows 2 and 7 ($2$), the $x_3{=}0$ child votes $1$ and misses row 3 ($1$) → $3/8$.
Answer & the takeaway
$b^\star = x_1$ (raining), with $I(Y;x_1) = 0.548795$ bits, $H(Y\mid x_1) = 0.451205$ bits. Both criteria agree on the winner here.
But look at $x_2$: mutual information reports exactly $0.000000$ — a precise, unambiguous statement that this attribute carries no information about the label whatsoever. Training error reports $4/8$ for $x_2$, which is the same score it gives no split at all: the right verdict, but arrived at by coincidence, since a $2$–$2$ tie in each child produces four mistakes for reasons that have nothing to do with independence. And when comparing $x_3$ ($3/8$) with $x_2$ ($4/8$), error rate tells you $x_3$ is better but gives you no sense of by how much; mutual information says $0.048795$ versus $0.000000$ — better, but barely worth having.
The real payoff: after splitting on $x_1$, the $x_1{=}1$ child is pure and becomes a leaf immediately. The recursion continues only on the five examples with $x_1 = 0$, where $H = 0.721928$ and only $x_2, x_3$ remain. That is Chapter 6's algorithm with the fixed criterion, running correctly.
A node holds $12$ examples: $10$ labelled "0" and $2$ labelled "1". Attribute $W$ splits it into
- $W{=}1$: $4$ examples — $2$ zeros and $2$ ones;
- $W{=}0$: $8$ examples — $8$ zeros and $0$ ones.
Your lab partner says: "Throw this split away. The left child has entropy $1.0$, which is higher than the parent's. The split increased uncertainty, and we proved that's impossible, so I must have made an arithmetic error." Is your partner right? Compute everything.
Step 1 — the parent's entropy
$P(Y{=}0) = 10/12 = 0.833333$, $P(Y{=}1) = 2/12 = 0.166667$.
$$\log_2\tfrac{12}{10} = \log_2 12 - \log_2 10 = 3.584963 - 3.321928 = 0.263034,$$ $$\log_2 6 = 2.584963,$$ $$H(Y) = 0.833333(0.263034) + 0.166667(2.584963) = 0.219195 + 0.430827 = \mathbf{0.650022}\text{ bits}.$$Step 2 — the two specific conditional entropies
$W{=}1$: two of each label, so $P(Y{=}1\mid W{=}1) = 1/2$ and
$$H(Y \mid W{=}1) = \mathbf{1.000000}\text{ bit}.$$$W{=}0$: all eight are zeros, so the node is pure and
$$H(Y \mid W{=}0) = \mathbf{0.000000}.$$Your partner's observation is factually correct: $1.000000 \gt 0.650022$. The left child really is more uncertain than the parent.
Step 3 — the theorem says nothing about individual children
The theorem is $H(Y\mid W) \le H(Y)$, where $H(Y\mid W)$ is the weighted average $\sum_\omega P(W{=}\omega)H(Y\mid W{=}\omega)$. It is not a claim about each $H(Y\mid W{=}\omega)$ separately, and indeed that claim is false — this problem is the counterexample.
Why it can happen: Jensen's inequality concerns the value of a concave function at a mixture of points versus the mixture of the values. Nothing stops one of the individual points from sitting higher than the mixture point; what's guaranteed is that the average of the values sits below.
Weights: $P(W{=}1) = 4/12 = 1/3$ and $P(W{=}0) = 8/12 = 2/3$.
Answer & the takeaway
Your partner is wrong, and there is no arithmetic error. The split is a good one: it cut uncertainty roughly in half. Two thirds of the data landed in a perfectly pure child that never needs another question; the remaining third became a coin flip, but it is only a third.
Takeaway — memorise the two statements separately:
- $H(Y\mid W) \le H(Y)$ — always true (the weighted average).
- $H(Y\mid W{=}\omega) \le H(Y)$ — often false (a single branch).
Confusing the two is the most reliably examined error on this material. Set the calculator above to left $= (2, 2)$ and right $= (8, 0)$ and watch it happen.
A dataset of $N = 100$ patients, label $y = $ "has the condition", with $50$ yes and $50$ no. Two candidate attributes:
- $W_A$ = "blood test positive", binary. Splits $50/50$; the positive child is $45$ yes and $5$ no, the negative child is $5$ yes and $45$ no.
- $W_B$ = "patient ID", taking $100$ distinct values, one per patient.
Compute $I(Y;W_A)$ and $I(Y;W_B)$. Which does information gain pick? Which should you pick, and what fixes the criterion?
Step 1 — the parent, and $W_A$
$H(Y) = H(1/2) = \mathbf{1.000000}$ bit (balanced).
Each $W_A$ child is $45$–$5$, i.e. $p = 0.1$:
$$H(Y\mid W_A{=}\text{pos}) = H(Y\mid W_A{=}\text{neg}) = 0.9\log_2\tfrac{10}{9} + 0.1\log_2 10 = 0.9(0.152003)+0.1(3.321928)$$ $$= 0.136803 + 0.332193 = \mathbf{0.468996}.$$ $$H(Y\mid W_A) = \tfrac12(0.468996) + \tfrac12(0.468996) = \mathbf{0.468996}, \qquad I(Y;W_A) = 1 - 0.468996 = \mathbf{0.531004}.$$Step 2 — $W_B$, the ID attribute
Each of the $100$ values selects exactly one patient. A one-example node is pure, so every specific conditional entropy is $0$:
$$H(Y\mid W_B) = \sum_{\omega=1}^{100}\tfrac{1}{100}\cdot 0 = \mathbf{0.000000}, \qquad I(Y;W_B) = 1 - 0 = \mathbf{1.000000}\text{ bit}.$$The absolute maximum — you cannot gain more than $H(Y)$, and $W_B$ takes all of it. Information gain picks $W_B$.
Step 3 — why that is catastrophic
The resulting tree has $100$ leaves, one per training patient. Training error: $0$. Test error: for a new patient with an unseen ID, the tree has no branch at all — and if you force one, the prediction is a coin flip. It has memorised, not learned.
The mechanism of the failure: gain measures reduction in entropy on the training set, and any attribute fine enough to separate every example drives that to zero regardless of whether the attribute means anything. This is overfitting showing up inside the splitting criterion itself.
Answer & the takeaway
$I(Y;W_A) = 0.531004$, $I(Y;W_B) = 1.000000$. Raw information gain picks $W_B$. Gain ratio repairs it:
$$H(W_A) = H(1/2) = 1 \Rightarrow \text{GainRatio}(W_A) = \frac{0.531004}{1} = \mathbf{0.531004},$$ $$H(W_B) = \log_2 100 = 6.643856 \Rightarrow \text{GainRatio}(W_B) = \frac{1.000000}{6.643856} = \mathbf{0.150515}.$$$W_A$ now wins by more than a factor of three. beyond syllabus
Takeaway: information gain is the right local criterion but it has no notion of generalisation. In this course we split on binary attributes, where every attribute has $H(W) \le 1$ and the bias is invisible. The moment you allow many-valued or real-valued attributes, you need gain ratio (C4.5), a depth limit, or pruning.
Recap
The quantities, in tree language: surprisal $\log_2\frac1p$ is the bits to name one outcome; entropy is the impurity of a node's labels; specific conditional entropy is the impurity of one child; conditional entropy is the size-weighted average impurity after the split; mutual information is the split's information gain; and BestAttribute picks which question to ask at this node. The formulas are in the Essentials box at the top.
- $0 \le H \le \log_2 k$, with $0$ iff deterministic (pure node) and $\log_2 k$ iff uniform (worst node).
- $I(Y;W)\ge 0$ always, by concavity of $H$ plus Jensen; equality iff $Y \perp W$. But a single $H(Y\mid W{=}\omega)$ can exceed $H(Y)$.
- The weights are not decoration. They are what stops a pure-but-empty child from winning.
- On the poll dataset the answer is $x_2$: $I = 0.548795$ bits versus $0.092359$ for $x_1$ and $0.048795$ for $x_3$ — a ranking training error could not produce.
Next up: linear regression, where the labels become real numbers, the "impurity" becomes squared error, and we finally get a model we can differentiate.