Class 7 · Decision Trees · Mini-module
A decision tree is a game of twenty questions. The only skill that matters is knowing which question to ask first.
Seven hundred and twelve people boarded the Titanic with a recorded age. Two hundred and eighty-eight of them lived. You don't get to see who.
Here is the game. You may ask one yes-or-no question about every passenger. Sex, age, ticket price, where they boarded, anything in the manifest. Each answer sends the passenger onto one of two decks. Then you bet on each deck: everyone on this deck lived, everyone on that deck died. Pick the question that makes those bets easy.
A decision tree plays exactly this game, over and over. It asks a question, splits the people into two groups, then asks another question inside each group, until each group is almost entirely one kind of person. The whole tree is built one question at a time, and it is greedy: at every step it grabs the single best question available right now.
So you need a way to score a question. You need a number that says how mixed a deck is, and a number that says how much a question cleaned up the mix. Play first. The numbers will make sense afterward.
Try it
Before you click anything: which question do you think sorts survivors from the rest most cleanly? Make a private guess. Then test every question and watch the two meters.
Two measures of chaos
Both meters measure the same thing, chaos, and they almost always agree. A deck where everyone shares the same fate has zero chaos. A deck split exactly in half is as chaotic as it gets. The two rulers just disagree slightly on how to count what happens in between.
Entropy comes from information theory. It measures surprise, counted in bits. A pure deck holds no surprise. You already know the answer before you look, so it costs zero bits to describe. A deck split fifty-fifty is a coin you cannot call: maximum surprise, one full bit.
The right-hand form is the only one you need here, because every deck has two kinds of people: those who lived with probability p, and the rest. Plug in p = 0.5 and you get exactly one bit. Plug in p = 1 and you get zero.
Gini asks a blunter question. Pull two people off the deck at random. What are the chances they had different fates? On a pure deck, zero. On a fifty-fifty deck, one in two.
Gini tops out at 0.5, entropy at 1.0, so the meters live on different scales. The shape is the same: both peak when the deck is evenly split, both fall to zero when it is pure. Drag your eye back to the toy and you will see them rise and fall together.
Two decks. Deck A holds 50 survivors and 50 who died. Deck B holds 90 survivors and 10 who died. Which deck is purer?
A mixed deck is not a problem yet. A question is good or bad depending on whether it leaves the decks purer than it found them. That difference is information gain.
Take the chaos you started with. Subtract the chaos you end up with. The catch is in that fraction nk/n. The children are weighted by how many people land in each. A question that perfectly purifies a closet of ten people while leaving the ballroom of seven hundred untouched has barely moved the average. The weighting is the whole point.
This is why "women and children first" splits unevenly on the meter. Both halves of that phrase are true. Only one is a good first question.
Watch what happens with sex, the strongest question on the ship.
Now run the same arithmetic on age. Children did live more often, 57 percent against 39. But there were only 68 of them in a jar of 712. Their pure little deck cannot outvote the enormous, still-mixed deck of everyone else. The gain comes out near 0.009 bits. Almost nothing. The "obvious" feature loses, and it loses for a reason you can read straight off the formula.
A question splits 712 people. One child has 10 people, all survivors, perfectly pure. The other child has 702 people, still badly mixed. Is this a strong first question?
Try the coin flip in the toy. It sorts 712 people onto two decks in under a second. Both decks come out as mixed as the jar you started with: roughly 40 percent survivors on each side, same as before. Entropy after the split equals entropy before. Information gain: essentially zero.
This is the lesson that makes "information" concrete. A question can be elaborate, expensive, clever-sounding, and still separate nothing. If the two decks have the same mix as the deck they came from, the question taught you nothing about who lived.
The coin flip does not land at a perfect zero. It scores about 0.001 bits, a hair above nothing, purely by luck of the shuffle. Hold onto that hair. A greedy tree will chase it. Given enough useless questions, one of them will look slightly better than zero by chance, and a tree with no restraint will split on it and call the noise a pattern. That is overfitting, and you meet it properly in the next class.
Which question has an information gain of about zero?
For the curious. Not required, and it will not be on the exam in this form. But if you have ever wondered why two measures of chaos exist when they mostly agree, here is the seam.
Entropy borrows directly from Claude Shannon's work on communication. The surprise of an event of probability p is log2(1/p) bits. Rare events are surprising, certain events are not. Entropy is just the average surprise across the deck. The base-two choice is why the unit is bits: one bit is the surprise of a fair coin. Use a natural log instead and the unit becomes nats. The tree does not care which base you pick, because every gain is a difference and the base cancels out.
Gini has a second reading that decision-tree libraries quietly rely on. Suppose you label each person by guessing randomly in proportion to the deck's mix. The probability you guess wrong is exactly 1 − Σ pi², which is Gini. So Gini is your expected error rate from a lazy guess. It needs no logarithm, which is part of why CART, the algorithm behind most tree libraries, uses it by default. It is cheaper to compute, and it almost never changes the answer.
Take a parent of 20 survivors and 36 who died, and two candidate questions that split it differently.
Split B carves off a perfectly pure deck of fourteen. Entropy is thrilled by purity and rewards that deck heavily, so it ranks B first. Gini looks at split B's other deck, an almost even 20 against 22, shrugs, and prefers split A's two moderately clean decks instead. They disagree, but by a sliver: Gini's two scores are 0.371 and 0.374. In a real tree this rarely changes the final shape, and when it does, the tree that follows usually fixes it on the next split. That is why nobody argues much about which to use.
Plain information gain has a bias. It loves questions with many possible answers. Split passengers by their exact ticket number and every deck holds one person, perfectly pure, enormous apparent gain, and a model that has memorized the manifest. The fix is gain ratio, which divides the gain by how much the question fragments the data. It is the reason a tree should be suspicious of any feature that is almost a unique identifier.
Try without AI · reflection
A subscription business wants to predict churn. Here are eight customers. Four churned, four stayed. You may ask one question first.
| Customer | Opened the app last week | On premium plan | Churned |
|---|
Without computing anything, decide which question you would ask first to predict churn: "opened the app last week" or "on premium plan". Write one sentence saying why, using the word purity.
Then, if you want the satisfaction: split the eight customers by each question, count survivors and churners on each deck, and work out the information gain by hand. One question should come out near a full bit. The other should come out at zero, a premium-plan coin flip. You have already seen this exact shape on the Titanic.
Bring your one sentence to class. The point is the reasoning, not the arithmetic.