Entropy and Information Gain

Play 20 Questions well and you'll notice a pattern in the best players: their first question is never "is it a rock, specifically a piece of granite, from a quarry in Wales?" It's something broad like "is it alive?" Why? Because "is it alive?" roughly splits the world in half — whichever answer comes back, you've thrown away about half of all possible objects. "Is it a rock specifically?" almost certainly gets a "no" and barely narrows anything down at all.

A decision tree faces exactly the same problem at every single node: out of all the questions it could ask about the data, which one should it ask first? To answer that, it needs a way to measure two things — how "mixed up" a group of examples currently is (entropy), and how much a candidate question would clean that mixture up (information gain). The tree then simply asks whichever question gains the most.

This isn't just a cute analogy — it's the exact same arithmetic. A tree trying to predict whether a customer will buy a product doesn't know in advance whether "age over 30?" or "owns a pet?" is the smarter opening question. It has to try both, measure how much each one would clean up the mixed group of buyers and non-buyers, and pick the winner — precisely the way a sharp 20-Questions player picks "is it alive?" over "is it a rock, specifically granite?"

Entropy: a number for "how mixed up"

Imagine a bag of labelled examples — say, "will this customer buy the product? yes or no." If every example in the bag is "yes," there's no mystery left: reach in and you already know what you'll pull out. That group is perfectly pure, and we say its entropy is 0 — zero uncertainty. If the bag is a perfect fifty-fifty mix of "yes" and "no," you genuinely can't guess better than a coin flip. That's maximum entropy — maximum uncertainty.

For a group split into two classes with proportions p and 1-p, entropy (measured in bits) is:

H(p) = -p\log_2 p - (1-p)\log_2(1-p).

Check it matches the story at the extremes: at p=0 (all "no") and p=1 (all "yes"), H=0 — pure, no surprise. At p=0.5, H(0.5) = -0.5\log_2 0.5 - 0.5\log_2 0.5 = 1 — the peak. Every mix in between lands somewhere on the curve joining those points.

(This page sticks to two classes — "yes/no," "spam/not spam" — because that's what most splits boil down to. The same idea stretches to more classes by adding one -p_i\log_2 p_i term per class, but the two-class case already carries the whole lesson.)

The disorder curve

Slide the class mix below and watch the curve. Entropy climbs from 0 at the edges to a single peak of 1 bit right at p=0.5, then falls away symmetrically on the other side. Nothing about the curve prefers "yes" over "no" — it only cares how mixed the group is, not which label happens to be in the majority.

Information gain: how much a question helps

Entropy alone tells you how mixed up one group is. To pick a splitting question, a tree needs to know how much a candidate split would clean things up — that's information gain: the parent group's entropy, minus the average entropy of the children the split creates (each child's entropy weighted by how large it is):

\text{gain} = H(\text{parent}) - \sum_{\text{child}} \frac{|\text{child}|}{|\text{parent}|}\, H(\text{child}).

At every node, the tree tries every candidate question, computes the information gain each one would give, and greedily picks the largest one. Do that node after node, and a whole tree grows itself, one locally-best question at a time. (Some tree libraries use a near-identical measure called Gini impurity instead of entropy — the spirit, and the greedy "pick the biggest improvement" logic, is the same either way.)

Notice the word greedily. The tree never looks two questions ahead to check whether a slightly worse first question might set up a much better second one — it just takes whichever gain is biggest right now, at every node, forever. That's usually a very good strategy (and a fast one — checking every possible pair of questions in advance would be far too slow), but it's not guaranteed to build the absolute best possible tree. It's also exactly the habit that gets a tree into trouble, as the next card shows.

Worked example: entropy by hand

Suppose a node holds 8 customers: 6 who bought ("yes") and 2 who didn't ("no"). The proportion of the majority class is p = 6/8 = 0.75. Plug it straight into the formula:

H(0.75) = -0.75\log_2(0.75) - 0.25\log_2(0.25) \approx 0.311 + 0.5 = 0.811 \text{ bits}.

Compare that to the two extremes: a group that's all 8 "yes" would score H=0 (perfectly pure), while a 4-yes/4-no group would score the maximum, H=1. Our 6-yes/2-no group sits — sensibly — somewhere between "quite pure" and "totally mixed," closer to the pure end.

Worked example: which split wins?

Take that same 8-customer group (entropy 0.811) and try two candidate splitting questions.

Split A — "Age over 30?" makes two children of 4 each: the "over 30" child is 4 yes / 0 no (entropy 0, perfectly pure!); the "30 or under" child is 2 yes / 2 no (entropy 1). The weighted average is \tfrac{4}{8}(0) + \tfrac{4}{8}(1) = 0.5, so:

\text{gain}_A = 0.811 - 0.5 = 0.311 \text{ bits}.

Split B — "Owns a pet?" makes a child of 5 (3 yes / 2 no, entropy \approx 0.971) and a child of 3 (3 yes / 0 no, entropy 0). Weighted average: \tfrac{5}{8}(0.971) + \tfrac{3}{8}(0) \approx 0.607, so:

\text{gain}_B = 0.811 - 0.607 = 0.204 \text{ bits}.

\text{gain}_A (0.311) > \text{gain}_B (0.204), so the tree asks "Age over 30?" first — it does more to untangle the group, even though neither split is perfect on its own.

Checking the arithmetic in code

The two worked examples above are just a handful of multiplications and logarithms. Run the code below to check the numbers land exactly where the by-hand working said they would — and try changing the group sizes to see the gains shift.

Entropy 0 doesn't mean "bad" — it means no uncertainty is left. A perfectly pure group is exactly what splitting is trying to produce, not a mistake to avoid. Low entropy children are the goal.
Information gain has a blind spot. Splitting on a column that's different for almost every row — a customer ID number, say — creates one tiny, perfectly pure group per row, which looks like a spectacular information gain. But it's not a real pattern; it's just memorising which ID belongs to which answer, and it tells the tree nothing useful about a new customer it hasn't seen before. This exact trap is the seed of overfitting a tree.

Put a number on it: split our 8-customer group by ID number instead of age or pets, and you get 8 children of size 1 — each one either 100% "yes" or 100% "no," so every single child has entropy 0. The weighted average child entropy is therefore exactly 0 too, which makes the information gain the biggest one possible — the whole 0.811 bits of parent entropy, easily beating both "age over 30?" (0.311) and "owns a pet?" (0.204). A tree that blindly follows the highest gain would ask "what is this customer's ID number?" — a question that is completely useless for predicting anything about a customer it hasn't already met.

This formula isn't a machine-learning invention at all — it's borrowed wholesale from Claude Shannon's 1948 paper that founded information theory. Shannon was asking a totally different question: how many bits, on average, do you need to communicate a message down a noisy telephone line? His answer was exactly this H(p) formula — the entropy of a source measures how much genuine "surprise" it contains, and therefore how many bits it takes to describe. Decision trees repurpose that same idea seventy-odd years later to ask "which question is most informative?"

It also explains why a sharp 20-Questions player can nail an object out of over a million possibilities in just 20 yes/no questions. Each perfectly-chosen question should roughly halve the remaining possibilities, and 2^{20} = 1{,}048{,}576 — so 20 good halvings are, in principle, exactly enough to pin down one item out of over a million. Ask sloppy questions ("is it a rock specifically?") and you waste your halvings on a question that barely removes any possibilities; ask sharp ones ("is it alive?") and every single one earns its keep. A decision tree, at its heart, is trying to be a sharp 20-Questions player: at every node it hunts for the one candidate question that comes closest to that ideal 50/50 halving of the group it's holding.

Shannon himself worked at Bell Labs, and legend has it he liked to ride a unicycle down the corridors while juggling — a fitting image for someone who could make something as slippery as "information" as precise and countable as a length in metres or a mass in kilograms.

Next: a tree that greedily chases information gain, split after split, will happily fall straight into that ID-column trap and others like it — carving out ever-tinier, ever-purer groups that fit the training data perfectly but generalize terribly. That's exactly the story of overfitting a tree.