Entropy and information gain: Visual walkthrough

Step 1 — A bag of marbles: what does "messy" even mean?

WHAT. Picture a cloth bag. Inside are marbles of two colours: some plum (call them "Yes") and some teal (call them "No"). You reach in blind and pull one out. How surprised are you by the colour you get?

WHY. Before we can measure "mess" with a formula, we need to agree on what mess feels like. A decision tree wants tidy bags — bags where you can guess the colour before you even look. The opposite (a bag where you can never guess) is "maximum mess." Everything else is derived from this one feeling.

PICTURE. Three bags, left to right: all-plum (never surprised), lopsided (rarely surprised), half-and-half (a coin flip every time).

Step 2 — Turning "surprise" into a number

WHAT. We invent a function $I (p)$ = the surprise of pulling an outcome that had probability $p$ . We do NOT guess its formula. Instead we write down two things surprise must obey, and let those choose the formula for us.

WHY. This is the honest way to build a formula: state what you want, then discover what satisfies it — rather than pulling $- lo g$ out of a hat.

$a sure thing shocks nobody I (1) = 0 independent surprises pile up I (p \cdot q) = I (p) + I (q)$

$I (1) = 0$ : if an event was certain ( $p = 1$ ), seeing it happen tells you nothing new.
$I (pq) = I (p) + I (q)$ : if two unrelated things happen — a plum marble AND a coin landing heads — their joint probability is the product $pq$ , but your total surprise should be the two surprises added. Surprise stacks; probability multiplies.

PICTURE. Two dials feeding a totaliser: probabilities enter through a "×" gate, surprises leave through a "+" gate. The device that converts one to the other is the mystery box we solve next.

Step 3 — Only the logarithm turns × into +

WHAT. We look for the one continuous function that turns multiplication of inputs into addition of outputs. That function is the logarithm.

WHY this tool and not another? We need $f (pq) = f (p) + f (q)$ . Ask: which everyday function has that magic property? Not squaring ( $(pq)^{2} = p^{2} q^{2}$ , that multiplies). Not $sin$ . The logarithm is defined by exactly this identity: $lo g (pq) = lo g p + lo g q$ . It is the unique continuous answer, so surprise must be built from a log.

PICTURE. The curve $- lo g_{2} p$ : it explodes toward $+ \infty$ as $p \to 0$ (a near-impossible event is enormously surprising) and touches $0$ at $p = 1$ .

Step 4 — From one outcome's surprise to the whole bag's entropy

WHAT. $I (p)$ is the surprise of one particular outcome. Entropy is the surprise you expect on average across every possible outcome, weighted by how often each occurs.

WHY average? A single pull could be a plum or a teal. To rate the bag (not one pull) we ask "how surprised will I be, typically?" — that is the expected value of surprise. You weight each outcome's surprise by its own probability $p_{i}$ , because likely outcomes happen more often and should count more.

$H (S) = over all colours i i \sum how often colour i appears p_{i} \cdot surprise of that colour (- lo g_{2} p_{i}) = - \sum_{i} p_{i} lo g_{2} p_{i}$

$p_{i}$ appears twice: once as the weight (how often), once inside the log (how surprising).
The sum runs over every class in the bag ( $c$ classes total).

PICTURE. A bar chart: each colour's bar height is its surprise $- lo g_{2} p_{i}$ , its width is its probability $p_{i}$ ; entropy is the total shaded area (probability-weighted average height).

Step 5 — The two-colour case: the famous entropy hump

WHAT. With only two colours, $p_{plum} = p$ and $p_{teal} = 1 - p$ . Plug into the average:

$H (p) = - p lo g_{2} p - (1 - p) lo g_{2} (1 - p)$

WHY draw the whole curve? Because a tree split slides $p$ around, and we want to see which bags are messy. Sweeping $p$ from $0$ to $1$ traces one smooth hump.

PICTURE. The full $H (p)$ curve on warm paper: it rises from $(0, 0)$ , peaks at $(0.5, 1)$ , and falls back to $(1, 0)$ . The three marble bags from Step 1 are marked on it.

Reading the curve at a glance:

Left foot $p = 0$ : all teal, no surprise, $H = 0$ .
Peak $p = 0.5$ : perfect coin flip, maximum surprise, $H = 1$ bit.
Right foot $p = 1$ : all plum, no surprise, $H = 0$ .

Step 6 — The edge case: what is $0 lo g_{2} 0$ ?

WHAT. At $p = 0$ the formula has a term $0 \cdot lo g_{2} 0$ . But $lo g_{2} 0 = - \infty$ , and " $0 \times \infty$ " looks undefined. We must decide what it means here.

WHY it matters. A pure node (all one colour) has some class with $p = 0$ . If this term blew up, entropy of a pure node would be undefined — nonsense, since a pure bag is the least messy thing possible. We need the limit, not the naive plug-in.

The resolution. As $p \to 0^{+}$ , the weight $p$ shrinks to zero faster than $- lo g_{2} p$ grows. Their product is squeezed to $0$ : $lim_{p \to 0^{+}} p lo g_{2} p = 0 ⟹ convention: 0 lo g_{2} 0 := 0$

PICTURE. Zoom near $p = 0$ : the tiny sliver of area (width $p$ , height $- lo g_{2} p$ ) collapses to nothing as $p \to 0$ — the curve lands smoothly on the axis, no spike.

So a pure node genuinely has $H = 0$ . Both feet of the hump are honest zeros.

Step 7 — The other edge: more colours push the ceiling up

WHAT. With two colours, the most mess is $1$ bit. What if the bag has $c$ equally likely colours? Set every $p_{i} = 1/ c$ :

$H_{m a x} = - \sum_{i = 1}^{c} \frac{1}{c} lo g_{2} \frac{1}{c} = - c \cdot \frac{1}{c} lo g_{2} \frac{1}{c} = lo g_{2} c$

$c = 2 \Rightarrow lo g_{2} 2 = 1$ bit (matches the hump's peak).
$c = 4 \Rightarrow lo g_{2} 4 = 2$ bits.
$c = 8 \Rightarrow 3$ bits.

WHY care? Entropy of $1$ bit is the max only for two classes. Comparing entropies across problems with different numbers of classes needs this ceiling. And uniform ( $p_{i} = 1/ c$ ) is always the messiest arrangement — no colour to bet on.

PICTURE. Bars for $c = 2, 4, 8$ each at uniform mix, with the maximum entropy $lo g_{2} c$ rising in staircase steps.

Step 8 — Why information gain can never be negative (the concavity picture)

WHAT. Splitting bag $S$ on a question produces child bags $S_{v}$ . Information gain is $I G = H (S) - \sum_{v} \frac{∣ S _{v} ∣}{∣ S ∣} H (S_{v}) .$ We claim the subtracted term (the weighted child mess) never exceeds the parent mess $H (S)$ , so $I G \geq 0$ .

WHY it's true — geometrically. The entropy curve is concave (it bulges upward like a dome). For any dome-shaped curve, the height above a mixture point is at least the weighted average of the heights above the parts — this is Jensen's inequality. The parent $p$ is the weighted average of the children's $p_{v}$ ; the parent sits on the curve above the straight line joining the children.

$point on the dome H (S) \geq weighted avg = point on the chord below v \sum \frac{∣ S _{v} ∣}{∣ S ∣} H (S_{v})$

PICTURE. Two children marked on the entropy hump, the straight chord joining them, and the parent point sitting on the curve above the chord. The vertical gap is the information gain.

Worst case: children have the same $p$ as the parent (the chord touches the curve) → gap $= 0$ → useless split, $I G = 0$ . A split can never raise uncertainty.

The one-picture summary

Everything above, compressed: surprise curve → averaged into the entropy hump → a split's gain is the concavity gap.

Recall Feynman retelling — say it back in plain words

We started with a bag of coloured marbles and asked "how surprised am I by a pull?" We demanded two obvious rules — certainty is boring ( $I (1) = 0$ ), and unrelated surprises add while their chances multiply. The only function that turns multiply into add is the logarithm, so surprise had to be $- lo g_{2} p$ ; the minus makes it positive, base 2 gives bits. Entropy is just the average surprise over the whole bag: $- \sum p_{i} lo g_{2} p_{i}$ . For two colours it's a smooth hump — zero at the pure ends, a full bit at the 50/50 peak. At the pure end the scary-looking $0 lo g 0$ is really $0$ (the weight shrinks faster than the log grows), so pure bags are honestly zero mess. With $c$ colours the ceiling climbs to $lo g_{2} c$ . Finally, because the hump bulges upward (concave), a parent always sits above the line joining its children — that vertical gap is the information gain, which is why gain can never be negative and why the tree greedily grabs the biggest gap.

Connections

Parent topic — Entropy & Information Gain
Decision Trees — the hump-gap is computed at every candidate split.
Gini Impurity — same concave-dome argument, no logarithm.
ID3 and C4.5 Algorithms — turn these gaps into a tree.
Cross-Entropy Loss — the same $- \sum p lo g q$ surprise-average in neural nets.
KL Divergence — measures the extra surprise from using the wrong distribution.
Overfitting and Pruning — chasing $I G$ to pure leaves can memorise noise.