Decision trees

After this page you can take a table of labelled examples, build the decision tree by hand the way the algorithm would, compute its training error, and say exactly why the error-rate splitting criterion has to be thrown away.

The apartment problem

Four hundred apartments are listed and you cannot tour four hundred. You need a cheap rule that says go see this one or skip it, explainable to your roommate. So you write one down — not as a formula, but as a sequence of questions:

Read it out loud and it is a policy: if the rent is low and the deposit is low, go; if the rent is low, the deposit high, but you are within 2 miles, go; if the rent is high, you only bother within a mile. That is a decision tree.

Anatomy, and what interpretability actually buys you

Concretely, you can audit it ("rejected because the deposit was high and it's 2.3 miles out"), debug it, deploy it legally where decisions must be justified, and edit it by hand. The cost is accuracy on hard problems: trees carve feature space into axis-aligned boxes (see below), so a diagonal rule costs a staircase of splits.

Rule-based vs. learned: the actual ML question

Where did Figure 1 come from? You made it up: you already knew rent matters more than bus access, and you guessed the thresholds. That is a rule-based approach, legitimate when you have the rules. The notes' objection is two-part:

• You often don't have the rules. Nobody can write down, from first principles, which combination of 40 blood-panel numbers indicates sepsis.
• The setting is too complex. Even where rules exist, with $d = 30$ binary attributes there are $2^{30}$ possible inputs and astronomically many trees. Hand-authoring is hopeless.

What the examples comprise

First say precisely what one "example" is. In the apartment problem:

• Each example is one prospective apartment.
• $x$ is the vector of answers to the five questions: "Rent low?", "Deposit low?", "Within 1 mi?", "Within 2 mi?", "Near bus stop?"
• $y$ is the answer to "should I go check this apartment out or not?"

Written formally, exactly as the notes have it:

Now generalise. For the rest of the chapter:

Inference: running a new point down the tree

Prediction is trivial, and that is the point. Given a new apartment $x^{(\mathrm{new})} \in \X$: start at the root, answer the question, follow the matching branch, repeat, and output the label of the leaf you land in.

The key building block: the decision stump

Trees are recursive, so start with the smallest tree that still does something — the notes' key building block:

Constructing a stump, in three steps

The pre-reading gives the recipe:

1. Select the attribute and split criterion. Which feature does the node test, and what test? For binary features the test is just "$x_b = 1$?"; for real-valued features you also pick a threshold.
2. Split the training dataset into subsets by passing each training point through the decision node. Each leaf then holds a subset of the training data.
3. Each leaf predicts by majority vote among the output values $y^{(i)}$ of the points that landed there. A tie-breaking scheme must be specified.

Why majority vote is the right leaf label

The recursive construction algorithm

From a stump to a tree is one idea: do it again on each leaf. Each leaf holds a subset; run the stump procedure on that subset; repeat until a stopping criterion fires. The algorithm exactly as the notes state it:

Algorithm 1  Decision Tree Construction

1: function DT(dataset S, set of attributes A ⊆ {1, 2, ..., d})
2:     if A = ∅  or  all examples in S have the same label then
3:         return a leaf with value = majority vote of labels in S
4:     end if
5:     let b = BestAttribute(S, A) ∈ A
6:     let LeftNode  = DT( {(x,y) ∈ S | x_b = 1},  A \ {b} )
7:     let RightNode = DT( {(x,y) ∈ S | x_b = 0},  A \ {b} )
8:     return the tree           "Is the b-th attribute equal to 1?"
                                    /  Yes            No  \
                                LeftNode            RightNode
9: end function

It is called initially with the whole training set and the whole attribute list:

The recursion in words, line by line

• Line 2 — the two base cases. $A = \emptyset$: every attribute on this path is used up, so no split is possible. Same label throughout $S$: the node is pure and splitting cannot beat the zero error it already has.
• Line 3 — the leaf. Majority vote, as proved above; needed even in the first base case, where $S$ may be mixed.
• Line 5 — the only interesting line. BestAttribute is a black box for now, and swapping implementations is what distinguishes the algorithms in the literature (see below and Chapter 7).
• Lines 6–7 — the partition. $x_b$ is $1$ or $0$, so every point goes to exactly one child and $|S_{\text{left}}| + |S_{\text{right}}| = |S|$. Removing $b$ from $A$ shrinks both arguments, so the recursion terminates at depth $\le d$.
• Line 8 — assembling. The recursive calls return sub-trees, not labels.

A wrinkle worth naming: "Is $x_b = 1$?" vs "Is $x_b = 0$?"

The pseudocode always asks "Is $x_b = 1$?", while the notes' worked example asks "Is $x_2 = 0$?". Not different algorithms: "is it 0?" is the same split with the branches swapped. The phrasing is cosmetic — keep the partition straight and the labels take care of themselves.

BestAttribute, version 1: minimise training error

We need to fill in BestAttribute. The notes' first proposal is the most obvious one:

A finite search you can do by hand: for each $b \in A$, split $S$ into the $x_b = 1$ and $x_b = 0$ groups, majority-vote each, add the mistakes; smallest total wins. Leaf labels need no separate search — majority vote is already optimal given the split — so "choose attribute and labels" collapses to "choose attribute".

The poll example, solved completely

The notes pose this question and answer only "In poll." Here is the full answer, every split, every count.

Step 0 — the root before any split

Rows 1, 2, 3 have $y=0$ and rows 4–8 have $y=1$: 3 zeros, 5 ones. Majority-voting the whole dataset without splitting predicts $\hat y = 1$ and is wrong on the 3 zeros — a baseline training error of $3/8$, which any split has to beat.

Step 1 — try every attribute as a stump

Adding the two branches of each split gives the totals:

Step 2 — recurse on the impure branch

The calls are DT({rows 5,6,7,8}, A = {1,3}) and DT({rows 1,2,3,4}, A = {1,3}).

The $x_2 = 1$ branch holds rows 5–8, all with $y = 1$: line 2 fires, return a leaf with value $1$. The $x_2 = 0$ branch holds rows 1–4 with labels $0,0,0,1$ — not pure, and $A = \{1,3\}$ is not empty, so recurse on:

$x_1$ resolves this node completely. Both of its children are pure, so both are immediately leaves, and the recursion stops.

Step 3 — the finished tree

Assembling the pieces gives exactly the tree in the notes (written in the notes' "Is $x_2 = 0$?" phrasing):

Step 4 — verify zero training error by running all 8 rows through it

The last column sums to $0$, so the error rate is $\tfrac{1}{8}\cdot 0 = 0$: a perfect fit to this training set. (Whether that is good is another question — see stopping criteria.)

Build the tree yourself

Reading a split table is not the same as feeling it. The 8 rows below are live: click any leaf to select it, split it on an attribute, and watch the counts flow into the children and the training error drop.

Greediness: why this algorithm is not optimal, and why we do it anyway

The notes are careful to flag this, and you should be too:

Why it is suboptimal. True ERM would search over all trees of a given size; greedy commits to the root split on a one-step lookahead, judging each attribute by what it does alone and never reconsidering — and a split that looks useless alone can be indispensable in combination. Why we do it anyway: finding the smallest consistent tree is NP-hard, while greedy costs $O(N \cdot d)$ per node.

The canonical failure: XOR

How the algorithm still recovers

The part people forget — run the algorithm literally on XOR:

1. At the root, all attributes tie. BestAttribute breaks the tie somehow — say it returns $x_1$.
2. Left child ($x_1 = 1$) holds rows 3, 4 with labels $1, 0$. Not pure, and $A = \{2\}$ is not empty, so recurse. The only choice is $x_2$: row 3 has $x_2{=}0$ (label 1), row 4 has $x_2{=}1$ (label 0). Both children pure.
3. Right child ($x_1=0$) holds rows 1, 2. Split on $x_2$: both children pure.

Final tree: depth 2, zero training error, perfect. The greedy criterion was blind, but the recursion kept going anyway because the stopping rule was "pure or out of attributes", not "gain is zero".

Evaluating decision trees

The pre-reading asks: here are two decision trees for the Iris task — which is better?

The measure for classification is the classification error rate:

Naming the symbols: $N$ is how many examples you are evaluating on, $y^{(i)}$ the true label, $\hat y^{(i)} = h(x^{(i)})$ the tree's prediction, and $\1(\cdot)$ the indicator, contributing $1$ for a mismatch. The sum counts mistakes; dividing by $N$ makes it a rate, comparable across dataset sizes.

This is the empirical risk $\hat R(h)$ from Chapter 5 with the zero-one loss $\ell(y,\hat y) = \1(y \ne \hat y)$ plugged in — the general machinery specialised to classification.

The Iris comparison, worked in full

Counting the crosses and dividing by $N = 7$:

Model A performs better on this dataset — the pre-reading's conclusion. Note the qualifier: seven flowers is far too few to conclude that petal measurements beat sepal measurements in general, since one flower is 14 percentage points of error rate.

Two more reconstructed examples

reconstruction The pre-reading illustrates "using decision trees" with two figures that did not survive PDF extraction — a cesarean-section tree and the Iris species tree — redrawn here. The structures are mine, not the professor's, though the attributes are standard for each problem.

Extension: beyond binary attributes, and decision boundaries

The notes list several extensions. Start with the one that changes the picture most.

Attributes with more than $\{0,1\}$ values

Two cases, handled differently.

• Categorical with $m$ values (colour $\in$ {red, green, blue}): either split into $m$ branches at once, or binarise — test "colour = red?" and let the No branch test the rest. Multi-way splits consume the attribute in one node; binary tests let you return to it.
• Real-valued (e.g. petal length $\in \R$). You cannot enumerate the values, so the node tests a threshold: "Is $x_j \ge t$?" Now BestAttribute must choose both $j$ and $t$.

Here is the notes' example with $\X = \R^2$, $\Y = \{0,1\}$, splitting first at $x_2 = 4.5$ and then at $x_1 = 3.5$:

Why tree boundaries are always axis-aligned staircases

Consequence for a diagonal boundary. If the truth is $y = \1(x_1 + x_2 \ge 5)$ — a clean 45° line — a tree can never draw it. It can only approximate it with a staircase of alternating horizontal and vertical splits, each shaving off one rectangle: roughly $O(1/\varepsilon)$ splits to get within $\varepsilon$, and every extra split thins the data, so leaves get sparse and the fit gets noisy. A tree cuts only with a guillotine held parallel to the table edges.

How threshold candidates are chosen beyond syllabus

You do not search all of $\R$: sort the $N$ values of $x_j$ and take the midpoints between consecutive distinct values. The partition changes only when $t$ crosses a data value, so there are at most $N-1$ candidates. Petal lengths $1.4, 1.5, 4.1, 4.5, 4.8, 5.1, 6.0$ give $1.45, 2.8, 4.3, 4.65, 4.95, 5.55$ — six, not infinitely many.

Extensions: attribute reuse and stopping criteria

You need not remove the chosen attribute

Lines 6–7 pass $A \setminus \{b\}$ down, but the notes say this is optional. For binary attributes, keeping $b$ is wasteful rather than wrong: every point in the left child already has $x_b = 1$, so a second test on $b$ sends them all one way and leaves the other child empty.

Different stopping criteria

Options, from the notes and from practice:

Extension: the menu of BestAttribute criteria

The notes give three options, with the formula for each.

1. Minimise training error

Done above in full: split on each candidate attribute, majority-vote both children, add the mistakes, take the minimum. Simple, intuitive — and, as the next section shows, badly behaved.

2. Minimise Gini impurity beyond syllabus

The notes say "won't discuss here", so one line: for class proportions $p_k$,

the probability that two points drawn at random from the node have different labels; choose the split minimising the weighted average of $G$ over the children, exactly as with conditional entropy. It is the CART and scikit-learn default, behaves almost identically to entropy, and needs no logarithm.

3. Maximise mutual information

Instead of "how many mistakes would a stump make?", ask "how much of the uncertainty in the labels does this attribute remove?" Quantifying that needs entropy, which is all of Chapter 7. The criterion, stated now:

This is also called the information gain method.

Why error rate is a broken splitting criterion

The pre-reading drops a warning and moves on: "error rate as a splitting criterion is problematic and will [be replaced] with other splitting criteria such as mutual information." That sentence is the hinge between this chapter and the next, so here is the demonstration rather than the promise.

A dataset where every split has the same training error

No split at all. Majority vote $= 1$, wrong on rows 7 and 8: 2/8.

Split on $a$.

• $a=1$: rows 1, 2, 5, 7 → labels $1,1,1,0$ → 3 ones, 1 zero → vote 1 → 1 mistake.
• $a=0$: rows 3, 4, 6, 8 → labels $1,1,1,0$ → 3 ones, 1 zero → vote 1 → 1 mistake.
• Total: 2/8.

Split on $b$.

• $b=1$: rows 1, 2, 3, 4 → labels $1,1,1,1$ → pure → vote 1 → 0 mistakes.
• $b=0$: rows 5, 6, 7, 8 → labels $1,1,0,0$ → 2–2 tie → vote 1 (tie-break) → 2 mistakes.
• Total: 2/8.

Mutual information does have an opinion

The next chapter derives all of this; here is the punchline. With $H$ the entropy in bits:

The arithmetic, since you should be able to do it by hand:

Recap

Every statement worth memorising is in the Essentials box at the top. The one line to carry forward: error rate is a fine way to evaluate a finished tree and a bad way to choose a split, because it is blind to purity changes that do not flip a majority. Mutual information is not — that is Chapter 7, where $H$ and $I$ are built from scratch via a game of 20 questions.