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

Recall One-line reminders of the tools you need

Entropy: $H (S) = - \sum_{i} p_{i} lo g_{2} p_{i}$ (units = bits, because $lo g_{2}$ ).
Binary entropy: $H (p) = - p lo g_{2} p - (1 - p) lo g_{2} (1 - p)$ .
Convention: $0 lo g_{2} 0 = 0$ .
Information gain: $I G (S, A) = H (S) - \sum_{v} \frac{∣ S _{v} ∣}{∣ S ∣} H (S_{v})$ .
Gini impurity: $G ini (S) = 1 - \sum_{i} p_{i}^{2}$ .
SplitInfo: $- \sum_{v} \frac{∣ S _{v} ∣}{∣ S ∣} lo g_{2} \frac{∣ S _{v} ∣}{∣ S ∣}$ ; Gain Ratio $= I G / SplitInfo$ . ⚠️ Edge case: Gain Ratio is undefined when $SplitInfo = 0$ — see below.

Handy log values you will reuse (all base 2): $lo g_{2} 3 \approx 1.585, lo g_{2} 5 \approx 2.322, lo g_{2} 7 \approx 2.807.$

Visual warm-up (read before the exercises)

The whole page rests on four pictures. Meet them once so every exercise below is "just reading a graph you already understand".

Intuition Why the entropy curve is a hump (and why

$0 lo g_{2} 0 = 0$ ) Look at Figure s01, the red binary-entropy curve $H (p)$ .

At the two ends ( $p = 0$ and $p = 1$ ) the node is pure — nothing to be uncertain about — so the curve touches zero.
In the middle ( $p = 0.5$ ) every draw is a coin flip — maximum mess — so the curve peaks at 1 bit.
The curve bulges upward (concave). That single shape fact is what guarantees information gain is never negative (proved visually in Exercise 4.3).

Why $0 lo g_{2} 0 = 0$ (the endpoint mystery): the term $- p lo g_{2} p$ looks like it should blow up at $p = 0$ because $lo g_{2} 0 = - \infty$ . But watch the red dot sliding toward $p = 0$ in the figure: the shrinking weight $p$ crushes the exploding $lo g$ faster than the log can grow. In the limit, $lim_{p \to 0^{+}} p lo g_{2} p = 0$ — the area of a razor-thin, infinitely-tall sliver goes to zero. So a class that never occurs adds no surprise, exactly as intuition demands. That is why the curve lands smoothly on $0$ at both ends instead of diving to $- \infty$ .

Level 1 — Recognition

Exercise 1.1

Which of these class counts gives entropy exactly $0$ bits? (a) 5 Yes, 5 No (b) 8 Yes, 0 No (c) 3 Yes, 1 No.

Recall Solution

Entropy is $0$ only when one class has probability 1 (perfectly pure) — the ends of the red curve in Figure s01.

(a) 50/50 → $H = 1$ bit, not 0.
(b) all Yes → $p = 1$ , $H = - 1 lo g_{2} 1 = 0$ . ✅
(c) mixed → $H > 0$ .

Answer: (b).

Exercise 1.2

A binary node is at its maximum entropy. What is $p$ (fraction of positives) and what is $H$ ?

Recall Solution

Binary entropy peaks at the top of the hump in Figure s01, where both classes are equally likely: $p = 0.5$ . $H (0.5) = - 0.5 lo g_{2} 0.5 - 0.5 lo g_{2} 0.5 = - 0.5 (- 1) - 0.5 (- 1) = 1 bit.$ Answer: $p = 0.5$ , $H = 1$ bit.

Level 2 — Application

Exercise 2.1

Compute $H$ for a node with 3 Yes, 1 No.

Recall Solution

$p_{Yes} = \frac{3}{4}, p_{No} = \frac{1}{4}$ . $H = - \frac{3}{4} lo g_{2} \frac{3}{4} - \frac{1}{4} lo g_{2} \frac{1}{4} .$ Now $lo g_{2} \frac{3}{4} = lo g_{2} 3 - 2 \approx 1.585 - 2 = - 0.415$ , and $lo g_{2} \frac{1}{4} = - 2$ . $H = - \frac{3}{4} (- 0.415) - \frac{1}{4} (- 2) = 0.311 + 0.5 = 0.811 bits.$ Answer: $\approx 0.811$ bits. (On Figure s01 this is the height of the red curve at $p = 0.75$ .)

Exercise 2.2

Compute $H$ for a 3-class node: 2 A, 2 B, 4 C (8 total).

Recall Solution

$p_{A} = \frac{1}{4}, p_{B} = \frac{1}{4}, p_{C} = \frac{1}{2}$ . $H = - \frac{1}{4} lo g_{2} \frac{1}{4} - \frac{1}{4} lo g_{2} \frac{1}{4} - \frac{1}{2} lo g_{2} \frac{1}{2} .$ $lo g_{2} \frac{1}{4} = - 2$ , $lo g_{2} \frac{1}{2} = - 1$ : $H = - \frac{1}{4} (- 2) - \frac{1}{4} (- 2) - \frac{1}{2} (- 1) = 0.5 + 0.5 + 0.5 = 1.5 bits.$ Answer: $1.5$ bits. (Note: >1 is fine — with 3+ classes entropy can exceed 1 bit.)

Exercise 2.3

Compute the Gini impurity for the same node (2 A, 2 B, 4 C).

Recall Solution

$G ini = 1 - (p_{A}^{2} + p_{B}^{2} + p_{C}^{2}) = 1 - (\frac{1}{16} + \frac{1}{16} + \frac{1}{4}) .$ $= 1 - (0.0625 + 0.0625 + 0.25) = 1 - 0.375 = 0.625.$ Answer: $0.625$ . (Log-free, hence cheaper than entropy — the black curve in Figure s03; see Gini Impurity.)

Level 3 — Analysis

Exercise 3.1

Parent node: 10 Yes, 10 No (20 examples). Split on attribute $A$ :

$A =$ Left (12): 9 Yes, 3 No
$A =$ Right (8): 1 Yes, 7 No

Compute the information gain $I G (S, A)$ .

Recall Solution

Step 1 — parent. 10/10 → $H (S) = 1$ bit.

Step 2 — children. Left: $p = \frac{9}{12} = \frac{3}{4}$ → this is the same distribution as Exercise 2.1: $H (Left) = 0.811 bits.$ Right: $p = \frac{1}{8}$ , $q = \frac{7}{8}$ . $lo g_{2} \frac{1}{8} = - 3$ , $lo g_{2} \frac{7}{8} = lo g_{2} 7 - 3 \approx 2.807 - 3 = - 0.193$ . $H (Right) = - \frac{1}{8} (- 3) - \frac{7}{8} (- 0.193) = 0.375 + 0.169 = 0.544 bits.$

Step 3 — weighted child entropy. The weights are the child widths from Figure s02: $\frac{12}{20} (0.811) + \frac{8}{20} (0.544) = 0.6 (0.811) + 0.4 (0.544) = 0.487 + 0.218 = 0.705.$

Step 4 — gain. $I G = 1 - 0.705 = 0.295 bits.$ Answer: $\approx 0.295$ bits — a genuinely useful split (both children lean strongly one way).

Exercise 3.2

Two candidate splits on the same parent ( $H (S) = 1$ bit, 20 examples):

Split P: two children each 50/50 (10 and 10).
Split Q: children {9 Yes, 3 No} (12) and {1 Yes, 7 No} (8) — the split from 3.1.

Without heavy computation, which has higher gain, and why?

Recall Solution

Split P: each child is 50/50 → $H = 1$ each → weighted after $= 1 \Rightarrow I G = 0$ . Split Q: weighted after $= 0.705 \Rightarrow I G = 0.295$ (from 3.1). $I G_{Q} = 0.295 > I G_{P} = 0.$ Split Q wins. Reasoning without arithmetic: Split P produces children just as messy as the parent — it separated nothing. Split Q pushed each child toward a majority class, removing uncertainty. Gain measures how much the mess dropped, not how the examples were counted.

Level 4 — Synthesis

Exercise 4.1

An ID column gives every one of 6 examples (3 Yes, 3 No) its own value, so 6 children of size

Compute (a) $I G$ , (b) SplitInfo, (c) Gain Ratio. Then explain why raw $I G$ is misleading here.

Recall Solution

(a) $I G$ . Parent 3/3 → $H (S) = 1$ . Each child has 1 example → pure → $H = 0$ . Weighted after $= 6 \times \frac{1}{6} (0) = 0$ . $I G = H (S) - 0 = 1 - 0 = 1 bit (looks perfect!).$

(b) SplitInfo. Six equal children, each $\frac{1}{6}$ : $SplitInfo = - \sum_{v = 1}^{6} \frac{1}{6} lo g_{2} \frac{1}{6} = - 6 \cdot \frac{1}{6} lo g_{2} \frac{1}{6} = - lo g_{2} \frac{1}{6} = lo g_{2} 6.$ $lo g_{2} 6 = 1 + lo g_{2} 3 \approx 1 + 1.585 = 2.585$ bits.

(c) Gain Ratio. $GainRatio = \frac{I G}{SplitInfo} = \frac{1}{2.585} \approx 0.387.$

Why raw $I G$ misleads: an ID splits data into pure singletons, so $I G$ hits its max of $1$ — but the tree learned nothing generalisable (a new example has a brand-new ID). Gain Ratio divides by SplitInfo, which is huge for many-valued splits, penalising the fake gain. This is why C4.5 uses Gain Ratio.

Exercise 4.2 (edge case)

When is Gain Ratio undefined, and how does C4.5 handle it? Give the smallest concrete example.

Recall Solution

Gain Ratio $= I G / SplitInfo$ blows up (division by zero) exactly when $SplitInfo = 0$ . Since $SplitInfo = - \sum_{v} \frac{∣ S _{v} ∣}{∣ S ∣} lo g_{2} \frac{∣ S _{v} ∣}{∣ S ∣}$ is itself an entropy of the child-size distribution, it is $0$ iff all data fall into a single branch — i.e. the split has only one non-empty child.

Smallest example: an attribute that takes the same value for all 6 examples. Then there is one child $S_{1} = S$ with $\frac{∣ S _{1} ∣}{∣ S ∣} = 1$ : $SplitInfo = - 1 \cdot lo g_{2} 1 = 0, GainRatio = \frac{I G}{0} (undefined) .$

The critical subtlety — it's actually $\frac{0}{0}$ , not $\frac{c}{0}$ . A single-branch split also removes no mess, because the one child is identical to the parent: $I G = H (S) - 1 \cdot H (S_{1}) = H (S) - H (S) = 0.$ So both numerator and denominator vanish: $GainRatio = \frac{I G}{SplitInfo} = \frac{0}{0}$ , an indeterminate form — not a "big number", not "infinity", simply undefined. Students who imagine a huge Gain Ratio here are wrong in the opposite direction; there is nothing to gain at all.

How C4.5 handles it: such a split is simply rejected / skipped — a candidate that leaves everything in one branch is never chosen. In practice C4.5 only considers attributes whose $I G$ is at least the average gain first; a zero- $I G$ (hence $\frac{0}{0}$ ) candidate fails that screen and never reaches the division.

Exercise 4.3

Refer to Figure s01. Point $X$ marks the weighted child entropy (on the straight chord); point $Y$ marks the true entropy of the mixed parent (on the curve). Explain, using the figure, why information gain can never be negative.

Recall Solution

The red curve is binary entropy $H (p)$ ; it is concave (bulges upward). Look at the figure:

The two children of a split sit at their own $p$ -values on the curve.
The parent's $p$ is the weighted average of the children's $p$ -values — it lands at $Y$ on the curve (the true entropy).
The weighted average of the two children's entropies lands at $X$ , which is on the straight dashed chord below the curve.

Because the curve is concave, the chord is always at or below the curve: $X \leq Y$ . So

\;\Longrightarrow\; IG = Y - X \ge 0.$$ Splitting can only remove uncertainty (or leave it unchanged), never add it.

Level 5 — Mastery

Exercise 5.1 (full split competition)

Parent: 14 examples, 9 Yes, 5 No ( $H (S) \approx 0.940$ bits). Two candidate attributes:

Outlook (3 values):
- Sunny (5): 2 Yes, 3 No
- Overcast (4): 4 Yes, 0 No
- Rain (5): 3 Yes, 2 No
Humidity (2 values):
- High (7): 3 Yes, 4 No
- Normal (7): 6 Yes, 1 No

Compute $I G$ for both and decide which the tree picks.

Recall Solution

Parent: $H (S) = - \frac{9}{14} lo g_{2} \frac{9}{14} - \frac{5}{14} lo g_{2} \frac{5}{14} \approx 0.940$ .

--- Candidate 1: Outlook ---

Children.

Sunny (2/5, 3/5): $H = - \frac{2}{5} lo g_{2} \frac{2}{5} - \frac{3}{5} lo g_{2} \frac{3}{5} \approx 0.971$ .
Overcast (4/0): pure → $H = 0$ .
Rain (3/5, 2/5): same distribution as Sunny by symmetry → $H \approx 0.971$ .

Weighted after (widths from Figure s02): $\frac{5}{14} (0.971) + \frac{4}{14} (0) + \frac{5}{14} (0.971) = \frac{10}{14} (0.971) \approx 0.694.$ $I G_{Outlook} = 0.940 - 0.694 \approx 0.246 bits.$

--- Candidate 2: Humidity ---

Children.

High (3/7, 4/7): $H = - \frac{3}{7} lo g_{2} \frac{3}{7} - \frac{4}{7} lo g_{2} \frac{4}{7} \approx 0.985$ .
Normal (6/7, 1/7): $H = - \frac{6}{7} lo g_{2} \frac{6}{7} - \frac{1}{7} lo g_{2} \frac{1}{7} \approx 0.592$ .

Weighted after: $\frac{7}{14} (0.985) + \frac{7}{14} (0.592) = 0.5 (0.985) + 0.5 (0.592) \approx 0.492 + 0.296 = 0.788.$ $I G_{Humidity} = 0.940 - 0.788 \approx 0.152 bits.$

--- Decision --- $I G_{Outlook} \approx 0.246 > I G_{Humidity} \approx 0.152.$ The tree splits on Outlook. Its pure "Overcast" child (entropy 0) is what makes it shine — it becomes a leaf immediately, removing more mess than Humidity's two still-mixed children.

Exercise 5.2 (base-invariance of ranking)

Recompute $I G_{Humidity}$ from 5.1 using natural log $ln$ instead of $lo g_{2}$ (units become nats). Does the choice of feature change?

Recall Solution

To convert an entropy measured in bits into nats, use $ln x = (lo g_{2} x) ln 2$ , so bits → nats means multiply by $ln 2 \approx 0.693$ (the nat is a larger unit, so the numeric value shrinks). Because $I G = H (S) - \sum_{v} \frac{∣ S _{v} ∣}{∣ S ∣} H (S_{v})$ is a linear combination of entropies, it scales by the same factor $ln 2$ : $I G_{Humidity}^{(l n)} = 0.152 \times ln 2 \approx 0.152 \times 0.693 \approx 0.105 nats.$ Likewise $I G_{Outlook}^{(l n)} \approx 0.246 \times ln 2 \approx 0.246 \times 0.693 \approx 0.171$ nats. The numbers shrink but the ordering is unchanged ( $0.171 > 0.105$ ), so the tree still picks Outlook. Ranking of splits is base-independent; only the units differ.

(If you instead went from nats back to bits you would multiply by $1/ ln 2 \approx 1.4427$ — the inverse conversion. Here we go bits→nats, hence the factor $ln 2$ .)

Recap

Recall What changes across levels?

L1 asks what the definitions say. L2 asks you to plug in numbers. L3 makes you compare splits. L4 exposes the high-cardinality bias, the SplitInfo=0 ( $\frac{0}{0}$ ) edge case, and the concavity guarantee. L5 runs a full multi-feature competition and proves base-invariance. The single formula $I G = H (S) - \sum_{v} \frac{∣ S _{v} ∣}{∣ S ∣} H (S_{v})$ carries all of it.

Connections

Parent: Entropy and Information Gain
Decision Trees — these gains choose each node's question.
ID3 and C4.5 Algorithms — ID3 uses $I G$ , C4.5 uses Gain Ratio (Exercises 4.1–4.2).
Gini Impurity — the log-free cousin from Exercise 2.3 and Figure s03.
Overfitting and Pruning — the ID-column trap in 4.1 is exactly why pure leaves overfit.