Entropy and information gain: Foundations — AI-ML deep dive

This page assumes you have seen nothing. Before you can read a single formula on the parent note, you need a small toolbox: fractions-as-probabilities, what a logarithm is, why base 2, the summation symbol, and averages. We build each one from a picture, in the exact order they stack.

1. A "set" $S$ and its labels

Picture a bag of marbles. Some are blue (label "Yes"), some are orange (label "No"). The bag is $S$ . We are not doing any maths yet — we are just naming the pile of things we will measure.

Why the topic needs it: entropy is a property of a bag. When the tree splits, it makes smaller bags $S_{v}$ (bag for value $v$ ). Every formula is "measure this bag, then measure the smaller bags".

2. Probability $p_{i}$ — a fraction that names "how much of the bag"

If the bag has 9 blue and 5 orange out of 14 total: $p_{blue} = \frac{9}{14} \approx 0.64, p_{orange} = \frac{5}{14} \approx 0.36.$

The little $i$ is just an index — a name-tag that walks through the classes one at a time: $i = 1$ is blue, $i = 2$ is orange. The letter $c$ means how many classes there are (here $c = 2$ ).

Why the topic needs it: entropy is built entirely out of these $p_{i}$ . No probabilities, no entropy.

3. The summation symbol $\sum$ — "add up over all the classes"

It is shorthand. Instead of writing $(stuff for blue) + (stuff for orange)$ we write $\sum_{i = 1}^{2} (stuff for i)$ . With 5 classes it saves a lot of ink.

Why the topic needs it: entropy $H (S) = - \sum_{i} p_{i} lo g_{2} p_{i}$ is a sum over classes. Information gain $\sum_{v} \frac{∣ S _{v} ∣}{∣ S ∣} H (S_{v})$ is a sum over the child bags. If $\sum$ is a blur, every formula is a blur.

4. The logarithm — the "how many doublings?" question

This is the tool the parent uses without ever slowing down. We slow down.

Doubling: $1 \to 2 \to 4 \to 8 \to 16$ . So:

$lo g_{2} 1 = 0$ (start at 1, no doublings needed),
$lo g_{2} 2 = 1$ (one doubling),
$lo g_{2} 8 = 3$ (three doublings, since $2 \times 2 \times 2 = 8$ ).

Why base 2 and not base 10 or $e$ ? Because we want to count in yes/no questions. Each yes/no question can split possibilities in half — one bit of information. "How many halvings?" is exactly $lo g_{2}$ . That is why the units are called bits.

This is the single reason the entropy formula has a minus sign out front: probabilities are $\leq 1$ , so their logs are $\leq 0$ , so $- lo g$ makes them back into friendly positive numbers.

5. Surprise $I (p)$ — turning "rare" into a number

Check the picture: at $p = 1$ the curve sits on the floor (no surprise — you knew it was coming). As $p$ shrinks toward $0$ the curve rockets up (a one-in-a-million event stuns you). This is the shape the log gives us for free.

Why the topic needs it: entropy is nothing more than the average of this surprise over the bag. Understand $I (p)$ and entropy is just "average $I$ ".

6. Weighted average $E [\cdot]$ — the average that respects size

Plain average of surprises would treat a rare class and a common class equally. That's wrong: a class that fills most of the bag should count more. So we weight each surprise $I (p_{i})$ by its own probability $p_{i}$ : $H (S) = E [I] = \sum_{i} p_{i} \cdot surprise of class i (- lo g_{2} p_{i}) .$

That is the entropy formula — assembled entirely from the pieces above: probabilities (§2), a sum (§3), a log (§4), and surprise (§5), averaged (§6).

The same weighting logic returns in information gain. There, the "quantity" is each child bag's entropy $H (S_{v})$ , and the weight is $\frac{∣ S _{v} ∣}{∣ S ∣}$ — the fraction of examples that land in that child.

7. Pure vs. maximally mixed — the two anchor pictures

Everything in between lives on the arch you see in the figure: entropy climbs from $0$ (pure), peaks at the balanced middle, and falls back to $0$ (pure the other way).

How these foundations feed the topic

Read top to bottom: a labelled bag gives probabilities; probabilities plus base-2 logs give surprise; averaging surprise gives entropy; comparing parent entropy to weighted child entropy gives information gain, which is what Decision Trees use to pick a question.

Where this leads next

Decision Trees — the machine that repeatedly maximises information gain.
Gini Impurity — the same "messiness" idea without any logarithm.
ID3 and C4.5 Algorithms — algorithms built directly on gain and gain ratio.
Cross-Entropy Loss — the same $- \sum p lo g q$ shape reused in neural nets.
KL Divergence — surprise generalised to compare two distributions.
Overfitting and Pruning — what happens when we chase pure leaves too hard.

Equipment checklist

Recall I can state what

$S$ and a label are. $S$ is a bag of examples; each carries a label (the class we predict). ::: A bag of examples, each tagged with its class.

Recall I can turn counts into

$p_{i}$ . $p_{i} = \frac{count of class i}{total}$ , always in $[0, 1]$ , and $\sum_{i} p_{i} = 1$ . ::: Divide each class count by the total; fractions sum to 1.

Recall I can read

$\sum_{i = 1}^{c}$ aloud. Plug in $i = 1, 2, \dots, c$ and add all the results. ::: Loop the index over all classes and add.

Recall I know what

$lo g_{2} x$ asks and why base 2. "How many doublings from 1 to $x$ ?" Base 2 because each yes/no question halves possibilities → units are bits. ::: Number of doublings; base 2 gives bits.

Recall I know why the entropy formula has a minus sign.

Probabilities $\leq 1$ have negative logs; the minus flips them positive. ::: Logs of fractions are negative, so $- lo g$ makes surprise positive.

Recall I can define surprise

$I (p)$ and its two anchor values. $I (p) = - lo g_{2} p$ ; $I (1) = 0$ (certain, no surprise), $I (\frac{1}{2}) = 1$ bit. ::: $- lo g_{2} p$ ; zero at $p = 1$ , one bit at $p = \frac{1}{2}$ .

Recall I know why we take a weighted average, not a plain one.

Common classes should count more; weight each surprise by its probability $p_{i}$ (and each child entropy by $\frac{∣ S _{v} ∣}{∣ S ∣}$ ). ::: Bigger/likelier pieces should dominate the average.

Recall I know the two entropy extremes.

Pure bag → $0$ ; balanced two-class bag → $1$ bit (max is $lo g_{2} c$ in general). ::: 0 when pure, max when evenly mixed.