What a decision tree is — twenty questions
Somebody is thinking of an animal and you get yes-or-no questions. Nobody opens with “is it a dolphin?”, and the reason nobody does is how a decision tree gets built.
Which kind is your problem? ended the last path by sorting problems into kinds. This path builds a model.
It builds a decision tree first, for one reason. A decision tree is a list of yes-or-no questions that ends in an answer. You can read every question it asks. So you can check its reasoning against your own before trusting any arithmetic.
Start with a version everybody has played. Somebody is thinking of an animal, and you get yes-or-no questions.
Think of an animal and the machine will name it
16 animals are in play. There are 8 questions you are allowed to ask. Think of one animal and answer honestly.
A yes-or-no game over sixteen animals. It opens with "Does it live in water?". After each answer it says how many animals are still possible: sixteen, then about eight, then about four. Answering yes four times in a row names the crocodile. The deepest animal in the game takes 5 questions.
Does it live in water?
16 animals still possible
It never opens with “is it a dolphin?” Every question it asks was chosen before you arrived, and chosen on one rule. The rest of this lesson is that rule.
Guessing one animal at a time takes 15 questions. Splitting the field takes 4.
There is another way to play. Is it a dolphin? Is it a shark? Is it a crocodile? It works. Sixteen animals, and fifteen no answers identify the last one.
Same animals. Same answers. Only the questions changed. That is the whole of what a decision tree gets right.
The best question is the one whose worse answer leaves the least behind
A question sends some animals to the yes side and the rest to the no side. What matters is the pile you are left with when the answer goes the unhelpful way.
The shorter the bar, the better the question. The two ends of that chart are the best and worst openings available.
| Question | Splits the 16 into | Left if the answer is unhelpful |
|---|---|---|
| Does it live in water? | 7 and 9 | 9 |
| Can it fly? | 3 and 13 | 13 |
Does it live in water?
- Splits the 16 into
- 7 and 9
- Left if the answer is unhelpful
- 9
Can it fly?
- Splits the 16 into
- 3 and 13
- Left if the answer is unhelpful
- 13
An even split leaves you the least to do next. A lopsided one barely helps.
Ask the best question again on whatever is left
Once you have asked it, you are playing a smaller game. Seven animals, or nine. So do the same thing again on each side.
That is the whole algorithm. Pick the most even question, ask it, and repeat on each side. It is six lines of code in the notebook, and it is a real decision tree.
Choosing questions well costs 4.1 questions. Guessing costs 8.4.
Most animals take four questions. The tallest bars are still well under the other strategy's average.
| Way of asking | Questions on average | Worst case |
|---|---|---|
| Ask the most even question | 4.1 | 5 |
| Guess one animal at a time | 8.4 | 15 |
Ask the most even question
- Questions on average
- 4.1
- Worst case
- 5
Guess one animal at a time
- Questions on average
- 8.4
- Worst case
- 15
Sixteen animals cannot be separated in fewer than 4 perfect halvings. So 4.1 is within a tenth of the best score anybody could get here. The robot with a bow asked for that habit: find the best possible score before judging the real one.
Every leaf holds one animal, so nothing was predicted
Each block at the bottom of that picture holds one animal. Ask four questions and you do not have an opinion about which animal it is. You have the animal.
A tree with one answer in every leaf has stored what it was told. It has not learned anything. Nothing was ever uncertain, so nothing was ever predicted. That describes a lookup table, and Not everything is a learning problem is about not calling one a model.
Next: two films answer every question the same way, and one flopped
The next lesson changes one thing. Twenty-four films, and whether each one made money.
Two of them answer all five questions identically, and one of them flopped. No question is left to ask. The leaf holds a mixture. Then “most even” stops working, and something has to replace it.
content/notebooks/decision-trees/twenty-questions.ipynb
Add an animal, remove a question, or change how ties are broken. Worth trying: delete the legs question and see which animals stop being separable.
Show the code5 cells
QUESTIONS = {
"water": "Does it live in water?",
"flies": "Can it fly?",
"feathers": "Does it have feathers?",
"fur": "Does it have fur or hair?",
"eggs": "Does it lay eggs?",
"hunts": "Does it hunt other animals?",
"big": "Is it bigger than a person?",
"legs": "Does it have legs?",
}
KEYS = list(QUESTIONS)
# water flies feath fur eggs hunts big legs
ANIMALS = {
"Dolphin": (1, 0, 0, 0, 0, 1, 1, 0),
"Shark": (1, 0, 0, 0, 1, 1, 1, 0),
"Crocodile": (1, 0, 0, 0, 1, 1, 1, 1),
"Goldfish": (1, 0, 0, 0, 1, 0, 0, 0),
"Octopus": (1, 0, 0, 0, 1, 1, 0, 0),
"Penguin": (1, 0, 1, 0, 1, 1, 0, 1),
"Duck": (1, 1, 1, 0, 1, 0, 0, 1),
"Eagle": (0, 1, 1, 0, 1, 1, 0, 1),
"Ostrich": (0, 0, 1, 0, 1, 0, 1, 1),
"Chicken": (0, 0, 1, 0, 1, 0, 0, 1),
"Bat": (0, 1, 0, 1, 0, 1, 0, 1),
"Elephant": (0, 0, 0, 1, 0, 0, 1, 1),
"Lion": (0, 0, 0, 1, 0, 1, 1, 1),
"Cat": (0, 0, 0, 1, 0, 1, 0, 1),
"Mouse": (0, 0, 0, 1, 0, 0, 0, 1),
"Snake": (0, 0, 0, 0, 1, 1, 0, 0),
}
assert len(set(ANIMALS.values())) == len(ANIMALS), "two animals answer identically"
record("n_animals", len(ANIMALS))
record("n_questions", len(QUESTIONS))def split(animals, feature):
"""(yes-side, no-side) — the animals that answer yes, and those that answer no."""
i = KEYS.index(feature)
yes = {n: v for n, v in animals.items() if v[i]}
no = {n: v for n, v in animals.items() if not v[i]}
return yes, no
scored = []
for f in KEYS:
yes, no = split(ANIMALS, f)
scored.append((f, len(yes), len(no), abs(len(yes) - len(no))))
scored.sort(key=lambda r: (r[3], r[0]))
for f, ny, nn, gap in scored:
print(f"{QUESTIONS[f]:<32} yes {ny:>2} no {nn:>2} worst case {max(ny, nn):>2} left")
first = scored[0]
record("first_question", QUESTIONS[first[0]])
record("first_yes", first[1])
record("first_no", first[2])
record("worst_question", QUESTIONS[scored[-1][0]])
record("worst_left", max(scored[-1][1], scored[-1][2]))
def plot(ax):
labels = [QUESTIONS[f].rstrip("?") for f, *_ in scored][::-1]
worst = [max(ny, nn) for _, ny, nn, _ in scored][::-1]
colors = ["#e2574c" if w == min(worst) else "#9aa0aa" for w in worst]
ax.barh(labels, worst, color=colors)
ax.axvline(len(ANIMALS) / 2, ls="--", lw=1.2, color="#3b6fd4")
ax.set_xlabel("Animals still possible, if the answer goes the wrong way")
ax.set_xlim(0, len(ANIMALS))
ax.grid(axis="y", visible=False)
save_fig("first-question-choice", plot, figsize=(7, 4.0))def build_tree(animals):
if len(animals) == 1:
return {"leaf": next(iter(animals))}
usable = [f for f in KEYS if all(split(animals, f))]
if not usable:
return {"leaf": " or ".join(sorted(animals))}
best = min(usable, key=lambda f: (abs(len(split(animals, f)[0]) - len(split(animals, f)[1])), f))
yes, no = split(animals, best)
return {"q": QUESTIONS[best], "yes": build_tree(yes), "no": build_tree(no)}
TREE = build_tree(ANIMALS)
record("tree", TREE)
def depths(node, d=0):
if "leaf" in node:
return {node["leaf"]: d}
return {**depths(node["yes"], d + 1), **depths(node["no"], d + 1)}
tree_depth = depths(TREE)
for name in sorted(tree_depth, key=tree_depth.get):
print(f"{name:<12} {tree_depth[name]} questions")
best_avg = record("best_avg", round(sum(tree_depth.values()) / len(tree_depth), 1))
best_worst = record("best_worst", max(tree_depth.values()))
record("perfect", 4) # log2(16): four perfect halvings would do it# Fifteen guesses is enough for sixteen animals: fifteen no's identify the last.
naive_depth = {name: min(i + 1, len(ANIMALS) - 1) for i, name in enumerate(ANIMALS)}
naive_avg = record("naive_avg", round(sum(naive_depth.values()) / len(naive_depth), 1))
record("naive_worst", max(naive_depth.values()))
record("times_more", round(naive_avg / best_avg, 1))
def plot(ax):
order = sorted(ANIMALS, key=lambda n: (tree_depth[n], n))
ax.bar(range(len(order)), [tree_depth[n] for n in order], color="#e2574c", width=0.68)
ax.axhline(best_avg, ls="--", lw=1.2, color="#e2574c")
ax.axhline(naive_avg, ls="--", lw=1.2, color="#9aa0aa")
ax.text(0.2, best_avg + 0.25, f"asking the splitting question: {best_avg} on average",
fontsize=9.5, color="#e2574c")
ax.text(0.2, naive_avg + 0.25, f"one animal at a time: {naive_avg} on average",
fontsize=9.5, color="#77777f")
ax.set_xticks(range(len(order)))
ax.set_xticklabels(order, rotation=55, ha="right", fontsize=9)
ax.set_ylabel("Questions to name it")
ax.set_ylim(0, max(naive_avg, max(tree_depth.values())) + 1.6)
ax.grid(axis="x", visible=False)
save_fig("questions-per-animal", plot, figsize=(7, 4.4))
def plot2(ax):
steps = range(0, len(ANIMALS))
halving = [max(1, len(ANIMALS) / 2 ** k) for k in steps]
one_at_a_time = [max(1, len(ANIMALS) - k) for k in steps]
ax.plot(list(steps), halving, marker="o", ms=4, color="#e2574c",
label="split the field")
ax.plot(list(steps), one_at_a_time, marker="o", ms=4, color="#9aa0aa",
label="one animal at a time")
ax.set_xlabel("Questions asked")
ax.set_ylabel("Animals still possible")
ax.legend(frameon=False)
save_fig("what-is-left", plot2, figsize=(7, 3.8))def leaves(node):
return [node["leaf"]] if "leaf" in node else leaves(node["yes"]) + leaves(node["no"])
def spans(node, x0, x1, d, out):
out.append((d, x0, x1, len(leaves(node))))
if "leaf" in node:
return
share = len(leaves(node["yes"])) / len(leaves(node))
xm = x0 + (x1 - x0) * share
spans(node["yes"], x0, xm, d + 1, out)
spans(node["no"], xm, x1, d + 1, out)
blocks = []
spans(TREE, 0.0, 1.0, 0, blocks)
def plot3(ax):
rows = max(d for d, *_ in blocks)
for d, x0, x1, n in blocks:
ax.add_patch(plt.Rectangle((x0, -d - 0.86), x1 - x0, 0.72,
facecolor="#e2574c", alpha=0.16 + 0.1 * min(d, 4),
edgecolor="#e2574c", lw=1.0))
if (x1 - x0) > 0.055:
ax.text((x0 + x1) / 2, -d - 0.5, str(n), ha="center", va="center", fontsize=10)
for d in range(rows + 1):
ax.text(-0.012, -d - 0.5, f"{d}", ha="right", va="center", fontsize=9, color="#77777f")
ax.set_xlim(-0.06, 1.01)
ax.set_ylim(-rows - 1.05, 0.02)
ax.set_ylabel("Questions asked")
ax.set_yticks([])
ax.set_xticks([])
ax.grid(visible=False)
for side in ("left", "bottom"):
ax.spines[side].set_visible(False)
import matplotlib.pyplot as plt
save_fig("carving-up-the-field", plot3, figsize=(7, 3.6))Related lessons
Base rates — what a piece of evidence is actually worth
A face-recognition system that is 99.9% accurate and almost entirely wrong, and a number that sent an innocent woman to prison. Both are the same arithmetic, and it is the arithmetic that decides what any piece of evidence is worth.
ReadConfirmation and survivorship — what you never looked for
Two questions about evidence you did not go looking for. One is a rule you have to discover, and one is a pattern in five famous people — and in both, the thing that would have told you the truth is the thing nobody checks.
ReadLoss aversion, sunk cost and regression — what it costs you
Four questions you answer about yourself rather than about a scenario, and your own answers are the finding. Then the pattern that makes praise look useless and criticism look like it works, whatever you actually do.
Read