Decision trees & ID3 (information gain)

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) = -\sum_i p_i \log_2 p_i \quad\text{(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) = \sum_v \frac{|C_v|}{|C|}\, I(C_v),$$

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

$$\text{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) = -\tfrac{9}{14}\log_2\tfrac{9}{14} - \tfrac{5}{14}\log_2\tfrac{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.