Part 2 · Machine Learning Basics

2.5 Decision trees and ensembles

Deciding by asking a series of questions

10-minute readAdvancedPrerequisite: 2.4 Logistic regression▶ Video (about 5 min)

What you will learn

Explain how a decision tree decides by stacking yes/no questions, and how the questions are chosen (Gini impurity)
Explain why the majority vote of many models (an ensemble) performs better, and the assumption behind it (independent mistakes)
Explain why decision trees are easy to read, and their weaknesses when grown too deep or used outside the training range

Build intuition

Let us add one more clue to the cut-in prediction of 2.4: “is the turn signal on?”. Across 20 recorded situations, neither the lateral speed alone nor the turn signal alone separates the cases cleanly. Cars drifting over slowly often cut in if their turn signal is on, and cars with no signal sometimes cut in if they drift over fast.

A person would probably ask questions in sequence: “Is it drifting over fast?” “Is the turn signal on?”. A decision tree builds this sequence of questions automatically from data.

A decision tree learned from 20 situations. Answer the questions from the top down; the leaf (colored box) you reach gives the decision. “3/4” means that 3 of the 4 situations in that leaf were cut-ins. The numbers are an illustrative example.

Reading it is just a matter of answering the questions from the top. For “lateral speed 0.3 m/s, turn signal on”, the first answer is “no”, the next is “yes”, and the one after that (at least 0.25?) is “yes”, which leads to a “cut in” leaf. Logistic regression had a single straight boundary; a decision tree can shift the boundary depending on the conditions — “from 0.25 m/s with the signal on, from 0.6 m/s without it”. This tree gets only one of the 20 situations wrong.

Check with math

① Choosing questions: Gini impurity

How mixed a box is between “cut in” and “no cut-in” is measured by the Gini impurity:

$$G = 1 - \sum_{k} p_k^{2}$$

$p_k$ is the share of class k in the box. If everything belongs to the same class, G = 0 (no mixing at all); a 50/50 mix of two classes gives G = 0.5 (the most mixed). The initial 20 situations (9 cut-ins, 11 not) have G = 1 − 0.45² − 0.55² ≈ 0.495.

For each candidate question, we take the impurities of the two boxes after the split and average them, weighted by the number of situations:

Candidate first question	Impurity after the split (weighted average)
Lateral speed ≥ 0.6 m/s	0.316 (the smallest)
Lateral speed ≥ 0.25 m/s	0.360
Turn signal on	0.375
(no split)	0.495

Splitting on “speed ≥ 0.6”, for example, gives a “yes” box with 6 cut-ins out of 7 (G ≈ 0.245) and a “no” box with 3 out of 13 (G ≈ 0.355); the average is (7 × 0.245 + 13 × 0.355) ÷ 20 ≈ 0.316. Choosing the question that lowers the impurity most, and repeating the same step in each resulting box, produces the tree in the figure. Decision trees are built this way, one question at a time — not by gradient descent.

② Ensembles: stronger by majority vote

A single tree is unstable: a small change in the data can change its shape a lot. So we build many models and take a majority vote. This is called an ensemble. If three models are each 80% correct and their mistakes are independent (1.1), the probability that the majority vote is correct is:

$$0.8^3 + 3 \times 0.8^2 \times 0.2 = 0.896$$

That is the sum of the cases where all three are right and where exactly one is wrong. With five models it rises to about 94%, and with eleven to about 99% (the binomial distribution of 1.3). Two methods are especially common:

Random forest: build many trees, each with randomly varied data and candidate questions, and take the majority vote (or the average, for numeric predictions)
Gradient boosting: add trees one at a time, each one making up for the mistakes of the trees before it

The calculation above, however, rests on the assumption that the mistakes are independent. Models trained on the same data tend to fail together in the same difficult situations (backlighting, for example), so the benefit of voting is much smaller than the calculation suggests. It is the same problem as the common cause in 1.1.

Summary

A decision tree decides by stacking yes/no questions. Each question is chosen to lower the impurity after the split (the Gini impurity) the most
A small tree is readable but unstable. Majority votes or averages of many models (ensembles) improve accuracy and stability
Voting helps most when the mistakes are independent. Models built from the same data with the same method tend to fail together through common causes

Quick quiz

Q1. A box contains three cut-in situations and one situation without a cut-in. What is its Gini impurity?

The shares are 0.75 and 0.25, so G = 1 − 0.75² − 0.25² = 1 − 0.5625 − 0.0625 = 0.375.

Q2. How does the tree in the figure classify “lateral speed 0.8 m/s, no turn signal”?

The first question (at least 0.6 m/s?) is “yes” and the next (turn signal?) is “no”, which leads to the “Cut in 3/4” leaf. The decision is “cut in”, but one of the four situations in that leaf did not cut in, so it is far from certain.

Q3. Three models are each 90% correct. If their mistakes are independent, what is the probability that the majority vote is correct?

0.9³ + 3 × 0.9² × 0.1 = 0.729 + 0.243 = 0.972, or about 97%.

Q4. Why is a majority vote of three models trained on the same data not as strong as the calculation in Q3?

Models trained on the same data tend to fail together in the same difficult situations, so their mistakes are not independent (a common cause). To get the benefit, combine different data, different methods and different sensors so that the models fail in different ways.