Decision trees & ID3 (information gain)

◈ 3 cards

Build a decision tree top-down with information gain: entropy I(C) = −Σ p·log₂ p, gain = I(C) − E(P), and Occam’s Razor as the bias.

Decision trees

A decision tree classifies an instance by walking from the root down: each internal node tests one attribute, each branch is a value of that attribute, each leaf is a class label. The path from root to leaf reads as a rule — trees are directly interpretable.

ID3 (Quinlan 1986) induces such a tree top-down and greedily: at each node it picks the attribute that best separates the remaining examples, partitions on it, and recurses on each partition until every partition is pure (one class) or attributes run out.

Information gain — the split criterion

“Best attribute” is made precise with Shannon’s entropy. For a set $C$ split among classes with proportions $p_{i}$ ,

$I (C) = - i \sum p_{i} lo g_{2} p_{i} (bits of “surprise” / impurity) .$

A pure set has $I = 0$ ; a 50/50 split has $I = 1$ bit. Testing attribute $P$ partitions $C$ into subsets $C_{v}$ ; the expected remaining information is the size-weighted average impurity

$E (P) = v \sum \frac{∣ C _{v} ∣}{∣ C ∣} I (C_{v}),$

and the information gain of testing $P$ is the impurity it removes:

$gain (P) = I (C) - E (P) .$

ID3 splits on the attribute of maximum gain.

Worked example — PlayTennis root split

Take 14 day-records labeled play = yes/no (9 yes, 5 no). The base impurity is $I (C) = - \frac{9}{14} lo g_{2} \frac{9}{14} - \frac{5}{14} lo g_{2} \frac{5}{14} \approx 0.940$ bits.

Testing outlook (sunny / overcast / rainy) cleanly carves out the all-yes overcast group, leaving little residual impurity — it removes about 0.247 bits. Testing wind barely separates the classes — only about 0.048 bits. So ID3 makes outlook the root. The exercise computes both gains from the raw table.

Occam’s Razor, operationalized. Maximizing gain at each step tends to produce the smallest tree consistent with the data — and empirically smaller trees generalize better. That is L8.1’s simplicity bias built straight into the algorithm.

The ID3 choice made explicit. Both attributes are scored the same way — partition the 14 records, take the size-weighted average entropy of the parts, and subtract that from the 0.940 bits you started with. Outlook removes five times as much impurity as wind, so it becomes the root.

What the winning gain bought: the overcast branch is <em>pure</em> after one test — four yes records, zero no — so it becomes a leaf immediately and contributes nothing to the remaining impurity. The other two branches are still mixed, so ID3 recurses on each with the attributes it has not used yet.