Decision trees & information gain

Drag the dashed line left and right. Some spots leave both sides a genuine mix of orange and grey — barely worth the split. Somewhere in the middle, one side becomes almost entirely one class. That's the split that actually teaches you something.

A decision tree is greedy: at every node, it tries every possible threshold and keeps whichever one removes the most uncertainty. That removed uncertainty is information gain — the entropy chapter's own formula, applied to a parent and its two children:

• IG — the information gain: how much uncertainty a split removes.
• $H(\text{parent})$ — the entropy of the node before splitting.
• $H(\text{left})$, $H(\text{right})$ — the entropy of each child node after splitting.
• $n_L$, $n_R$ — the number of points that land in the left and right child.
• $n$ — the total number of points at the parent node.

1. The second term is the children's weighted entropy

   It's the entropy of each child node, weighted by how many points landed on that side — so a child with more points counts for more of the average.

2. A good split lowers that weighted average a lot

   A split is good exactly when the children's weighted average entropy is much lower than the parent's entropy you started with.

Now watch both sides' entropy directly instead of just the final gain. Push the split to an edge and one side goes empty (entropy 0, nothing left to weigh) while the other still holds the full mess. The best split isn't the one that empties a side fastest — it's the one that minimizes the weighted average.

This dataset is 6 of one class, 4 of the other.

1. Compute the parent's entropy

   $$-(0.6\log_2 0.6 + 0.4\log_2 0.4) \approx 0.971 \text{ bits}$$
2. Split at 5.5 and compute each child's entropy

   The left side ($x \le 5$) is 5 points, all one class — entropy $0$. The right side ($x \ge 6$) is 5 points, 4 of one class and 1 of the other:

   $$-(0.8\log_2 0.8 + 0.2\log_2 0.2) \approx 0.722$$
3. Weight the children by size

   $$\frac{5}{10}(0) + \frac{5}{10}(0.722) = 0.361$$
4. Subtract from the parent for the information gain

   $$0.971 - 0.361 \approx 0.610 \text{ bits}$$

   The largest of any threshold this dataset admits, even though the right side still isn't perfectly pure.