Unit 3: Twenty Questions
A model you can read.
Unit 3 of 13 in AI and machine learning for kids. Its 4 lessons are One Question Is Not Enough, Which Question Is Best?, Growing the Whole Tree and A Tree That Learned Too Much — below is everything each one explains, and a question or two from it to try.
Every sample on this page is plain Python with no libraries, run before it shipped, and prints exactly what it says it prints.
This unit opens with a fortnight’s trial of everything — no card needed — or with a family plan, bought in the iPhone app. The first two units of every track are free for ever. Try it in the app.
❓ One Question Is Not Enough
A third fruit arrives
Limes are bumpy like an orange, but light like an apple. Suddenly the shop has three answers, and every rule you have written so far only knows two.
Python
fruits = [
[150, 2, "apple"],
[170, 3, "apple"],
[140, 1, "apple"],
[180, 7, "orange"],
[165, 8, "orange"],
[190, 9, "orange"],
[155, 7, "lime"],
[145, 8, "lime"],
]
for weight, bumpiness, name in fruits:
print(name, weight, bumpiness)It prints
apple 150 2 apple 170 3 apple 140 1 orange 180 7 orange 165 8 orange 190 9 lime 155 7 lime 145 8
The old rule calls the limes oranges
Unit 1's threshold on bumpiness is not wrong exactly — the limes really are bumpy. It has simply run out of things to say. There is no number you could put in it that would help.
Python
fruits = [
[150, 2, "apple"],
[180, 7, "orange"],
[155, 7, "lime"],
[145, 8, "lime"],
]
for weight, bumpiness, name in fruits:
guess = "orange" if bumpiness >= 5 else "apple"
print(name, "->", guess)It prints
apple -> apple orange -> orange lime -> orange lime -> orange
So ask a second question — but only where it is needed
Bumpy fruit still needs sorting out, and there weight does the job: oranges are heavy, limes are not. Apples were settled by the first question and need nothing more.
Questions inside questions like this make a decision tree.
Python
def classify(weight, bumpiness):
if bumpiness >= 5:
if weight >= 160:
return "orange"
return "lime"
return "apple"
print(classify(150, 2))
print(classify(180, 7))
print(classify(145, 8))It prints
apple orange lime
Every fruit takes one path down
A tree is not a list of rules that all get checked. Each fruit answers the first question, goes down that side, answers the next one there, and stops at a leaf — the label at the bottom.
Which means the tree can always tell you *why*: the questions it asked on the way down are the reason.
Try it yourself
Why can a tree do something a single threshold cannot?
- It uses bigger numbers
- It can ask a different next question depending on the first answer
- It looks at all the training data every time
- It is trained for longer
What does this print?
Python
def classify(weight, bumpiness):
if bumpiness >= 5:
if weight >= 160:
return "orange"
return "lime"
return "apple"
print(classify(170, 3), classify(155, 7))Answer them in the app
🔎 Which Question Is Best?
Nobody should be choosing the questions
You picked "bumpiness >= 5" because you looked at the table. A learner has to find it, and to find it, it needs a way to say one question is better than another.
Here is a simple one: split the fruit with the question, then answer each side with whatever label is commonest there. Count the mistakes. Fewer is better.
Counting the mistakes on one side
A group of three oranges and two limes gets answered "orange", so it makes two mistakes. A group that is all one label makes none — that group is pure, and there is nothing left to ask it.
Python
def mistakes(group):
names = [f[2] for f in group]
best = 0
for name in sorted(set(names)):
if names.count(name) > best:
best = names.count(name)
return len(group) - best
bumpy = [[180, 7, "orange"], [165, 8, "orange"], [190, 9, "orange"], [155, 7, "lime"], [145, 8, "lime"]]
smooth = [[150, 2, "apple"], [170, 3, "apple"], [140, 1, "apple"]]
print(mistakes(bumpy))
print(mistakes(smooth))It prints
2 0
A question is scored by both its sides
Add the mistakes on the yes side to the mistakes on the no side. Bumpiness scores 2. Weight scores 3, so it is the worse first question — which matches what you saw by eye.
Python
fruits = [
[150, 2, "apple"],
[170, 3, "apple"],
[140, 1, "apple"],
[180, 7, "orange"],
[165, 8, "orange"],
[190, 9, "orange"],
[155, 7, "lime"],
[145, 8, "lime"],
]
def mistakes(group):
names = [f[2] for f in group]
best = 0
for name in sorted(set(names)):
if names.count(name) > best:
best = names.count(name)
return len(group) - best
def score(feature, threshold):
yes = [f for f in fruits if f[feature] >= threshold]
no = [f for f in fruits if f[feature] < threshold]
return mistakes(yes) + mistakes(no)
print("bumpiness >= 5:", score(1, 5))
print("weight >= 160:", score(0, 160))It prints
bumpiness >= 5: 2 weight >= 160: 3
Now try every question there is
Both features, and every value that actually appears in the data as the threshold. That is a few dozen questions, and the computer scores them all in no time.
This is unit 1's search again, one level up: the thing being searched for is a question rather than a number.
Python
fruits = [
[150, 2, "apple"],
[170, 3, "apple"],
[140, 1, "apple"],
[180, 7, "orange"],
[165, 8, "orange"],
[190, 9, "orange"],
[155, 7, "lime"],
[145, 8, "lime"],
]
def mistakes(group):
names = [f[2] for f in group]
best = 0
for name in sorted(set(names)):
if names.count(name) > best:
best = names.count(name)
return len(group) - best
def score(feature, threshold):
yes = [f for f in fruits if f[feature] >= threshold]
no = [f for f in fruits if f[feature] < threshold]
return mistakes(yes) + mistakes(no)
best_feature = 0
best_threshold = 0
best_score = len(fruits)
for feature in [0, 1]:
for f in fruits:
s = score(feature, f[feature])
if s < best_score:
best_score = s
best_feature = feature
best_threshold = f[feature]
print(best_feature, best_threshold, best_score)It prints
1 7 2
Feature 1, threshold 7
The computer chose "is bumpiness at least 7?" — very nearly the question you chose by eye, and it never looked at the table.
Only values from the data are tried, because a threshold of 6 and a threshold of 7 cut this fruit into exactly the same two piles. Anything between two neighbouring values is the same question wearing a different number.
Try it yourself
A question splits the fruit into a pure group and a group of 4 oranges and 1 lime. What does it score?
- 0
- 1
- 4
- 5
Answer it in the app
🌳 Growing the Whole Tree
Do the same thing again, on each side
Find the best question. It leaves two smaller piles. Now find the best question for each of those piles, and for their piles, and so on.
A job that calls itself on a smaller version of itself is recursion, and a tree is what recursion looks like when you draw it.
Knowing when to stop
Stop when a group is pure — every fruit in it has the same label — because no question could improve on an answer that is already right.
Stop as well if no question separates the group at all, which happens when two fruits have identical features and different labels. Then answer with whatever is commonest and accept the mistake.
Python
def mistakes(group):
names = [f[2] for f in group]
best = 0
for name in sorted(set(names)):
if names.count(name) > best:
best = names.count(name)
return len(group) - best
def majority(group):
names = [f[2] for f in group]
best = names[0]
for name in sorted(set(names)):
if names.count(name) > names.count(best):
best = name
return best
limes = [[155, 7, "lime"], [145, 8, "lime"]]
mixed = [[180, 7, "orange"], [155, 7, "lime"]]
print(mistakes(limes) == 0, majority(limes))
print(mistakes(mixed) == 0, majority(mixed))It prints
True lime False orange
The whole thing, growing itself
Indent by the depth and the shape appears. Two questions, three leaves, and nobody wrote a single if about fruit.
Python
fruits = [
[150, 2, "apple"],
[170, 3, "apple"],
[140, 1, "apple"],
[180, 7, "orange"],
[165, 8, "orange"],
[190, 9, "orange"],
[155, 7, "lime"],
[145, 8, "lime"],
]
def mistakes(group):
names = [f[2] for f in group]
best = 0
for name in sorted(set(names)):
if names.count(name) > best:
best = names.count(name)
return len(group) - best
def majority(group):
names = [f[2] for f in group]
best = names[0]
for name in sorted(set(names)):
if names.count(name) > names.count(best):
best = name
return best
def best_split(group):
best = None
best_score = len(group) + 1
for feature in [0, 1]:
for f in group:
threshold = f[feature]
yes = [g for g in group if g[feature] >= threshold]
no = [g for g in group if g[feature] < threshold]
if len(yes) == 0 or len(no) == 0:
continue
s = mistakes(yes) + mistakes(no)
if s < best_score:
best_score = s
best = [feature, threshold]
return best
def grow(group, depth):
pad = " " * depth
split = best_split(group)
if mistakes(group) == 0 or split is None:
print(pad + majority(group))
return
feature, threshold = split
name = "bumpiness" if feature == 1 else "weight"
print(pad + "is " + name + " >= " + str(threshold) + "?")
grow([g for g in group if g[feature] >= threshold], depth + 1)
grow([g for g in group if g[feature] < threshold], depth + 1)
grow(fruits, 0)It prints
is bumpiness >= 7?
is weight >= 165?
orange
lime
apple
Read it out loud
*Is it bumpy? Then is it heavy? Then it is an orange, otherwise a lime. Not bumpy? Apple.*
That is the entire model, in a sentence a person can check, argue with, and correct. Hold on to that — nothing else in this track can do it.
Try it yourself
What stops grow from calling itself for ever?
- A counter
- Each group is smaller than the last, and pure groups stop
- Python stops it automatically
- It only runs twice
Answer it in the app
🏆 A Tree That Learned Too Much
Somebody typed the label wrong
A ninth fruit joins the pile: 185g, bumpiness 8 — plainly an orange — but whoever wrote the labels put "apple".
One wrong row out of nine. Watch what the tree does about it.
Python
fruits = [
[150, 2, "apple"],
[170, 3, "apple"],
[140, 1, "apple"],
[180, 7, "orange"],
[165, 8, "orange"],
[190, 9, "orange"],
[155, 7, "lime"],
[145, 8, "lime"],
[185, 8, "apple"],
]
print(len(fruits), "fruits, and a label that is wrong")It prints
9 fruits, and a label that is wrong
It builds a tower to reach one fruit
The rule was "keep asking until the group is pure", so it kept asking. Look at the bottom: is weight >= 185? — a question invented for exactly one fruit, that no greengrocer has ever asked.
Zero mistakes on the fruit it was given. It has learned the typo.
Python
fruits = [
[150, 2, "apple"],
[170, 3, "apple"],
[140, 1, "apple"],
[180, 7, "orange"],
[165, 8, "orange"],
[190, 9, "orange"],
[155, 7, "lime"],
[145, 8, "lime"],
[185, 8, "apple"],
]
def mistakes(group):
names = [f[2] for f in group]
best = 0
for name in sorted(set(names)):
if names.count(name) > best:
best = names.count(name)
return len(group) - best
def majority(group):
names = [f[2] for f in group]
best = names[0]
for name in sorted(set(names)):
if names.count(name) > names.count(best):
best = name
return best
def best_split(group):
best = None
best_score = len(group) + 1
for feature in [0, 1]:
for f in group:
threshold = f[feature]
yes = [g for g in group if g[feature] >= threshold]
no = [g for g in group if g[feature] < threshold]
if len(yes) == 0 or len(no) == 0:
continue
s = mistakes(yes) + mistakes(no)
if s < best_score:
best_score = s
best = [feature, threshold]
return best
def grow(group, depth, limit):
pad = " " * depth
split = best_split(group)
if mistakes(group) == 0 or split is None or depth >= limit:
print(pad + majority(group))
return
feature, threshold = split
name = "bumpiness" if feature == 1 else "weight"
print(pad + "is " + name + " >= " + str(threshold) + "?")
grow([g for g in group if g[feature] >= threshold], depth + 1, limit)
grow([g for g in group if g[feature] < threshold], depth + 1, limit)
grow(fruits, 0, 99)It prints
is bumpiness >= 7?
is weight >= 165?
is weight >= 180?
is weight >= 190?
orange
is weight >= 185?
apple
orange
orange
lime
apple
And now a real orange pays for it
A perfectly ordinary 186g bumpy orange walks into that carved-out band and comes out an apple. The tree is not confused — it is doing exactly what it was told, on a rule that was never about fruit.
Python
def deep_tree(weight, bumpiness):
if bumpiness >= 7:
if weight >= 165:
if weight >= 180:
if weight >= 190:
return "orange"
if weight >= 185:
return "apple"
return "orange"
return "orange"
return "lime"
return "apple"
def small_tree(weight, bumpiness):
if bumpiness >= 7:
if weight >= 165:
return "orange"
return "lime"
return "apple"
print("deep tree: ", deep_tree(186, 8))
print("small tree:", small_tree(186, 8))It prints
deep tree: apple small tree: orange
The cure is to stop early
Give the tree a depth limit and it cannot build the tower. At a limit of 2 it gets the typo wrong — 1 mistake on its training data — and gets the real orange right.
A model that is worse on the data it was given and better on everything else is the one you want. Unit 6 will show you the same trade with a network, where you cannot see the rule at all.
Try it yourself
Tree A makes 0 mistakes on the training fruit; tree B makes 1. Which do you ship?
- A, obviously
- Whichever does better on fruit neither of them has seen
- B, because simpler is always right
- Neither — retrain until both are 0
A bank refuses someone a loan. Why might a tree be a better choice than a network there?
- Trees are more accurate
- A tree can show the questions it asked, so a person can check whether they were fair
- Trees are faster
- Networks cannot handle money
Answer them in the app