Decision Trees
Chapter Seventy-Nine
Syllabus topic Module 2, "Decision trees"
Pages 280 to 284 of 378
In one line
A decision tree is a sequence of yes-or-no questions arranged so that each answer narrows the possibilities, and information gain is how the questions are chosen.
In the wording you can write in an examination: a decision tree is a classifier in which each internal node tests one attribute, each branch corresponds to an outcome of that test, and each leaf carries a class label. It is built top down by choosing, at each node, the attribute whose test most reduces the uncertainty of the labels, measured as the difference between the entropy before the split and the weighted average entropy after it, which is called the information gain.
Entropy, from scratch
What it measures. How mixed a set of labels is. All one label: no uncertainty. An even split: maximum uncertainty.
The formula. For labels with proportions p1, p2 and so on, the entropy is the negative sum of each p times the logarithm of that p to base two.
entropy = - (p1 log2 p1) - (p2 log2 p2) - ...
Worked, for two labels.
| Split | Proportions | Entropy | In words |
|---|---|---|---|
| 8 of one, 0 of the other | 1 and 0 | 0 | pure, no uncertainty |
| 6 and 2 | 0.75 and 0.25 | 0.8113 | mostly one |
| 4 and 4 | 0.5 and 0.5 | 1 | maximally mixed |
And the unit is the bit, which is the unit of [Laghu and Guru as One Bit]. An even two-way split carries one bit of uncertainty because settling it takes exactly one yes-or-no answer.
Information gain
The definition. The entropy before the split, minus the weighted average of the entropies of the branches, where each branch is weighted by the fraction of rows it takes.
gain = entropy(before)
= - (fraction going yes) * entropy(yes branch)
= - (fraction going no) * entropy(no branch)
Why weighted. A branch with one row should not count as much as a branch with seven. Weighting by size is what makes the measure the expected remaining uncertainty.
Why it cannot be negative. Splitting can never increase the expected uncertainty, so the gain is at least zero, and it is exactly zero when the attribute tells you nothing.
The tree, built
"""Entropy, information gain and a decision tree, on a small table of our own."""
import math
# Our own table, invented for this chapter and not taken from any source:
# whether a nightly batch job finished on time.
ATTRS = ["big input", "index missing", "backup running"]
ROWS = [
# (big input, index missing, backup running), label
((0, 0, 0), "on time"),
((0, 0, 1), "on time"),
((1, 0, 0), "on time"),
((1, 0, 1), "late"),
((0, 1, 0), "on time"),
((0, 1, 1), "late"),
((1, 1, 0), "late"),
((1, 1, 1), "late"),
]
def entropy(labels):
n = len(labels)
if n == 0:
return 0.0
out = 0.0
for lab in sorted(set(labels)):
p = labels.count(lab) / n
out -= p * math.log2(p)
return out
def split(rows, i):
return ([r for r in rows if r[0][i] == 1],
[r for r in rows if r[0][i] == 0])
def gain(rows, i):
before = entropy([r[1] for r in rows])
yes, no = split(rows, i)
n = len(rows)
after = (len(yes) / n) * entropy([r[1] for r in yes]) \
+ (len(no) / n) * entropy([r[1] for r in no])
return before - after
def build(rows, available, depth=0):
labels = [r[1] for r in rows]
if len(set(labels)) <= 1:
return labels[0] if labels else None
scored = [(gain(rows, i), i) for i in available]
scored = [(g, i) for g, i in scored if g > 1e-12]
if not scored:
return sorted(set(labels))
g, best = max(scored, key=lambda t: (t[0], -t[1]))
rest = [i for i in available if i != best]
yes, no = split(rows, best)
return (ATTRS[best], round(g, 4), build(yes, rest, depth + 1), build(no, rest, depth + 1))
def render(node, indent=0, label=""):
pad = " " * indent
if not isinstance(node, tuple):
return "%s%s-> %s" % (pad, label, node)
attr, g, yes, no = node
return "\n".join([
"%s%s%s? (gain %.4f)" % (pad, label, attr, g),
render(yes, indent + 4, "yes: "),
render(no, indent + 4, "no: "),
])
print("the table")
print(" %-11s %-14s %-15s %s" % tuple(ATTRS + ["label"]))
for values, lab in ROWS:
print(" %-11d %-14d %-15d %s" % (values[0], values[1], values[2], lab))
labels = [r[1] for r in ROWS]
print()
print("labels: %d on time, %d late" % (labels.count("on time"), labels.count("late")))
print("entropy before any split: %.4f bits" % entropy(labels))
print()
print("information gain of each attribute")
for i, a in enumerate(ATTRS):
yes, no = split(ROWS, i)
print(" %-15s gain %.4f yes-branch entropy %.4f (%d rows) no-branch entropy %.4f (%d rows)"
% (a, gain(ROWS, i), entropy([r[1] for r in yes]), len(yes),
entropy([r[1] for r in no]), len(no)))
print()
print("the tree")
tree = build(ROWS, list(range(len(ATTRS))))
print(render(tree))
print()
print("checking the tree against every row of the table")
def classify(node, values):
while isinstance(node, tuple):
attr, _, yes, no = node
node = yes if values[ATTRS.index(attr)] == 1 else no
return node
wrong = [(v, lab, classify(tree, v)) for v, lab in ROWS if classify(tree, v) != lab]
print(" rows classified wrongly:", len(wrong) if wrong else "none, all 8 correct")Decision Trees
the table
big input index missing backup running label
0 0 0 on time
0 0 1 on time
1 0 0 on time
1 0 1 late
0 1 0 on time
0 1 1 late
1 1 0 late
1 1 1 late
labels: 4 on time, 4 late
entropy before any split: 1.0000 bits
information gain of each attribute
big input gain 0.1887 yes-branch entropy 0.8113 (4 rows) no-branch entropy 0.8113 (4 rows)
index missing gain 0.1887 yes-branch entropy 0.8113 (4 rows) no-branch entropy 0.8113 (4 rows)
backup running gain 0.1887 yes-branch entropy 0.8113 (4 rows) no-branch entropy 0.8113 (4 rows)
the tree
big input? (gain 0.1887)
yes: index missing? (gain 0.3113)
yes: -> late
no: backup running? (gain 1.0000)
yes: -> late
no: -> on time
no: index missing? (gain 0.3113)
yes: backup running? (gain 1.0000)
yes: -> late
no: -> on time
no: -> on time
checking the tree against every row of the table
rows classified wrongly: none, all 8 correctDecision Trees
Reading the output
Entropy before any split is exactly 1 bit, because four rows are on time and four are late. That is the maximally mixed case.
And all three attributes have the same gain, 0.1887. That is not a bug and it is the most instructive thing in the output.
Why. The table was constructed so that the job is late when at least two of the three conditions hold. The rule is symmetric in the three attributes, so no one of them is a better first question than another, and the measure correctly reports that.
How the tie is broken. The program takes the highest gain and, among equals, the earliest attribute. The choice is arbitrary and it must be made, which is worth knowing: an implementation that did not state its tie-break would build different trees on different runs.
Then the gains rise as you descend. 0.1887 at the root, 0.3113 at the second level, 1.0000 at the third. Each question is more informative than the last, because the earlier questions have already removed the easy cases and what remains is a cleaner problem. A gain of 1.0000 means the attribute settles the answer completely for the rows that reach it.
And the tree classifies all eight rows correctly, which the program checks rather than asserting.
Reading a tree
To classify. Start at the root. Answer its question about your case. Follow that branch. Repeat until a leaf.
To explain a classification. Read the path. "Big input yes, index missing no, backup running yes, therefore late." The path IS the explanation, which is why a decision tree is an intrinsically interpretable model in the sense of [Explainable AI, and Why a Five-Member Answer Is an Explanation].
To read the rule the tree encodes. Each root-to-leaf path is one IF-THEN rule, so a tree with five leaves is five rules. [Rule-Based Systems] is about the same knowledge in the other shape.
Decision Trees
Overfitting
The one thing a chapter on decision trees must warn about.
What it is. A tree grown until every leaf is pure fits the training data exactly, including its accidents, and then performs badly on new cases.
Why trees are especially prone. Nothing stops the algorithm splitting until each leaf holds one row. A tree with as many leaves as rows has learned the table and nothing else.
The standard remedies. Stop early, when a node has too few rows or the best gain is too small. Or grow the tree fully and then prune, removing subtrees that do not improve performance on data held back from training.
And the honest note for this paper. With eight rows there is no held-out data and the question does not arise. With three rows, in the next chapter, it arises very sharply indeed.
What a decision tree is NOT
It is not unique. A different tie-break, or a different measure, gives a different tree for the same data. Several trees can classify the same table perfectly.
It is not a probability model. A leaf says "late". It does not say how likely late is, unless the implementation is extended to report the proportions at the leaf.
It is not good at everything. A relationship like "late when the sum of two numbers exceeds a threshold" needs a staircase of many splits, because each split tests one attribute. That is the standard weakness and it is why other methods exist.
And information gain is not the only measure. The Gini impurity is the common alternative and usually gives a similar tree. Naming one alternative is worth a mark.
Quick revision
- Entropy measures how mixed the labels are, in bits: 0 when pure, 1 when evenly split two ways.
- Information gain is the entropy before a split minus the weighted average entropy after it, and it is never negative.
- The tree is built top down by taking the attribute of highest gain at each node.
- In the worked table all three attributes tie at the root, because the rule is symmetric, and the tie-break must be stated or the tree is not reproducible.
- Gains rise with depth, because earlier questions remove the easy cases.
- A root-to-leaf path is an explanation and is also an IF-THEN rule.
- Overfitting: a tree grown to purity learns the table. Remedies are early stopping and pruning.
Test yourself
1. Compute the entropy of a set of labels that is six of one kind and two of another.
The proportions are 0.75 and 0.25, so the entropy is minus 0.75 times the logarithm of 0.75 to base two, minus 0.25 times the logarithm of 0.25 to base two, which is 0.8113 bits.
Decision Trees
2. Define information gain and say why the branch entropies are weighted.
It is the entropy of the labels before the split minus the weighted average of the entropies of the branches. The branches are weighted by the fraction of rows each receives, so that the result is the expected remaining uncertainty rather than an unweighted average.
3. Why do all three attributes have the same gain at the root of the worked tree?
Because the table encodes a symmetric rule: the job is late when at least two of the three conditions hold. No attribute is a better first question than another, and the measure reports that correctly.
4. What is overfitting in a decision tree, and give two remedies.
Growing the tree until every leaf is pure, so that it fits the accidents of the training data and performs badly on new cases. The remedies are stopping early, when a node has too few rows or the best gain is too small, and pruning a fully grown tree using data held back from training.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself for the same subject.