Random forests and gradient boosting

One decision tree changes a lot when its training data changes. Learn two ways to combine many trees into a stronger model: average trees grown on resampled data (bagging and random forests), or add small trees one at a time, each fixing what the others still get wrong (gradient boosting).

Lesson 8 stepsPractice 5 problemsExercise Python, 8 functionsQuiz 5 questions

Warm-up

One question before the lesson. Choose an answer and check it.

A hundred people each guess how many sweets are in a jar. Which is usually closest to the true number?

A typical person’s guess.The largest guess.The average of all hundred guesses.

Show the answer

C: The average of all hundred guesses. Each guess is off, some too high and some too low, so in the average the errors partly cancel. Averaging many trees works for the same reason, as long as the trees make different mistakes.

Step 1 One tree, many trees

01/08

Lesson 7 split Lesson 2’s 10 students once. Keep splitting until every leaf holds one student, and the regression tree fits all 10 scores exactly: its training error is 0. Like Lesson 2’s degree-9 curve, it has high variance: change the training data a little, and the tree changes a lot.

To see this, make new training sets from the same 10 students. Draw a student at random 10 times, putting each one back before the next draw, and grow a full tree on each set. Here is the tree on all 10, then the first five such sets, with what each tree predicts for a student who studied 4 hours:

Training set	Students drawn	Leaves	Prediction at 4 hours
all 10	1, 2, 3, 4, 5, 6, 7, 8, 9, 10	10	80.7
1	1, 3, 5, 6, 7, 7, 8, 10, 10, 10	7	80.7
2	1, 2, 2, 3, 4, 5, 5, 5, 5, 8	6	71.6
3	1, 2, 3, 3, 3, 5, 6, 6, 7, 8	7	80.7
4	2, 2, 3, 4, 5, 8, 8, 8, 8, 10	6	71.6
5	1, 2, 2, 3, 3, 5, 6, 7, 8, 9	8	80.7

Across all 100 sets, the prediction at 4 hours runs from 64.3 to 80.7, while the true pattern from Lesson 2 gives 75.2. Each tree predicts the score of whichever student in its set studied closest to 4 hours, so the answer depends on who was drawn. A fully grown tree on one input works like Lesson 6’s nearest neighbour with k = 1.

Try it yourself

Average more and more trees and watch the prediction settle and the validation error fall, then draw new samples to see how much a single tree changes. Then boost: add rounds one at a time, change the learning rate, and find the round where the validation error is lowest.

Trees 1

average of the trees true pattern

Filled dots: the 10 training students. Hollow dots: the 10 validation students.

Validation error 121.6

Average of 1 tree: mean squared error on the 10 validation students = 1215.83 ÷ 10 = 121.583

With these samples, one tree scores 121.6 and all 100 average to 39.6.

Show the calculation

Student	Hours x	Score y	The trees say	Average ŷ	(y − ŷ)²
1	0.5	44.8	31.9	31.9	166.41
2	1.2	52.1	31.9	31.9	408.04
3	2	61.9	58.5	58.5	11.56
4	2.6	66.5	58.5	58.5	64
5	3.6	70.5	71.6	71.6	1.21
6	4.2	73.9	80.7	80.7	46.24
7	5.5	90.5	73.7	73.7	282.24
8	5.8	85.5	73.7	73.7	139.24
9	6.5	82.9	73.7	73.7	84.64
10	7.7	85	81.5	81.5	12.25

Add trees and watch the average settle, then draw new samples and compare one tree with many.

Practice problems

Work each problem out on paper, then type your answer and press Check. Every problem has hints and a full solution.

Score: 0 of 10 points

Problem 1
1 point
A bootstrap sample draws 4 times from 4 students, with replacement. What is the chance that one particular student is never drawn? Give it to 2 decimal places.
Hint 1
One draw misses that student with chance 1 − 1/4.
Hint 2
The draws are independent, so multiply that chance by itself 4 times.
Solution
one draw misses: 1 − 1/4 = 0.75
all 4 miss: 0.75⁴ = 0.75 × 0.75 × 0.75 × 0.75 = 0.3164
Problem 2
2 points
Five trees of a forest predict 62, 70, 66, 58 and 69 for a student whose real score is 61. The forest predicts the average of the five. What is the forest’s squared error for this student?
Hint 1
Average the five predictions first.
Hint 2
Then subtract the real score and square the result.
Solution
average = (62 + 70 + 66 + 58 + 69) ÷ 5 = 325 ÷ 5 = 65
squared error = (65 − 61)² = 4² = 16
Problem 3
2 points
Three students studied 1, 2 and 3 hours and scored 48, 60 and 66. Boosting starts every prediction at the mean score. Round 1’s stump asks: did they study less than 1.5 hours? Each leaf predicts the mean residual of its students, and the learning rate is 0.5. After round 1, what is the prediction for the student who studied 3 hours?
Hint 1
Start at the mean of the three scores. Each residual is a score minus that start.
Hint 2
The student at 3 hours is on the no side. Its leaf is the mean residual of that side. Add 0.5 times it to the start.
Solution
start = (48 + 60 + 66) ÷ 3 = 174 ÷ 3 = 58
residuals: 48 − 58 = −10, 60 − 58 = 2, 66 − 58 = 8
no side’s leaf: (2 + 8) ÷ 2 = 5
new prediction = 58 + 0.5 × 5 = 58 + 2.5 = 60.5
Problem 4
2 points
A boosted classifier gives a student who passed (y = 1) a log-odds of z = 0.5. What residual y − p does the next tree fit for this student? Give it to 2 decimal places.
Hint 1
Turn z into a probability first: p = σ(z) = 1 ÷ (1 + e^(−z)).
Hint 2
Then take p from y, which is 1.
Solution
e^(−0.5) = 0.6065
p = 1 ÷ (1 + 0.6065) = 1 ÷ 1.6065 = 0.6225
y − p = 1 − 0.6225 = 0.3775
Problem 5
3 points
The next tree puts this student in a leaf with value 0.4, and the learning rate is 0.5. What is the student’s new probability of passing? Give it to 2 decimal places.
Hint 1
Add the learning rate times the leaf to z.
Hint 2
Then turn the new z into a probability with the sigmoid.
Solution
new z = 0.5 + 0.5 × 0.4 = 0.5 + 0.2 = 0.7
e^(−0.7) = 0.4966
p = 1 ÷ (1 + 0.4966) = 1 ÷ 1.4966 = 0.6682

Programming exercise

Write bootstrap samples, bagged regression trees and gradient boosting in plain Python. Save ensemble.py and test_ensemble.py in the same folder, fill in each function in ensemble.py, and run the tests:

python test_ensemble.py

"""Random forests and gradient boosting: programming exercise. Write bagged regression trees and gradient boosting in plain Python, on oneinput: hours studied, predicting a test score. Run the tests from this folder:     python test_ensemble.py xs is a list of hours and ys the list of scores that go with them. A tree isa dictionary. A leaf is {"leaf": value}, the score it predicts. A questionis {"threshold": t, "below": tree, "above": tree}, where below is the treefor the hours less than t."""  def bootstrap(n, rng):    """Return a bootstrap sample of the positions 0 to n - 1: n draws, each made with rng.randrange(n), so a position can come up more than once."""    raise NotImplementedError  def fit_stump(xs, ys):    """Return (threshold, below, above) for the one question that lowers the squared error most.     Try every threshold halfway between two neighbouring different values of    xs. below is the mean of the ys whose x is less than the threshold, and    above is the mean of the rest. The squared error of a side is the sum of    (y - its mean)**2. If two thresholds tie, keep the smaller. Return None    if no threshold lowers the squared error of the whole group.    """    raise NotImplementedError  def fit_tree(xs, ys):    """Grow a regression tree all the way: split with fit_stump's question, then grow each side the same way, until fit_stump returns None. A leaf predicts the mean of its ys."""    raise NotImplementedError  def predict_tree(tree, x):    """Follow the tree's questions for x and return the value of the leaf it reaches."""    raise NotImplementedError  def bag(xs, ys, count, rng):    """Return a list of count trees, each grown with fit_tree on its own bootstrap sample of the points, drawn with bootstrap(len(xs), rng)."""    raise NotImplementedError  def predict_bag(trees, x):    """Return the average of the trees' predictions for x."""    raise NotImplementedError  def boost(xs, ys, rounds, rate):    """Gradient boosting with stumps.     Start every prediction at the mean of ys. Each round, find each point's    residual (its y minus its current prediction), fit a stump to the    residuals with fit_stump, and keep it. Stop early if fit_stump returns    None. Return a dictionary: {"start": the mean, "rate": rate, "stumps":    the list of (threshold, below, above), in the order they were fitted}.    """    raise NotImplementedError  def predict_boost(model, x):    """Return the start plus rate times each stump's value for x: below if x is less than its threshold, above otherwise."""    raise NotImplementedError

Stuck? Write bootstrap and fit_stump first. fit_tree splits with fit_stump’s search, then calls itself on each side until a side cannot be split. boost keeps a list of stumps and adds rate times each one. The Solution tab has one way to write each function.

In practice: forests and boosting in real projects

Which to try first. For a table of numbers and categories, gradient-boosted trees (XGBoost, LightGBM, CatBoost, or scikit-learn’s HistGradientBoostingClassifier) are a common first choice, and a random forest is a strong baseline that needs almost no tuning. Compare them on the same validation set, as this lesson does.

Tuning boosting. The settings that matter most are the learning rate, the number of rounds and the depth of each tree. Use a small learning rate, such as 0.1, and let early stopping choose the rounds: XGBoost’s early_stopping_rounds and LightGBM’s early_stopping callback stop once the validation error has not improved for that many rounds. scikit-learn’s gradient boosting grows trees of depth 3 by default, and XGBoost of depth 6.

Tuning forests. More trees never make a forest overfit. They make it steadier and slower, so use as many as time allows: scikit-learn’s default is 100. oob_score=True reports the out-of-bag score without a separate validation set. max_features, how many inputs each question may look at, is the setting most worth trying.

Test your knowledge

01What is bagging, and why does it help?Show answer
Bagging trains many models, each on a bootstrap sample of the training data (drawn with replacement), and averages their predictions or takes a vote. Their errors go different ways, so the average has lower variance than any one model, while each model keeps its low bias.
02How is a random forest different from bagged trees?Show answer
At each split, a random forest looks at only a random subset of the inputs, such as the square root of their number. The trees then ask different questions and make less similar mistakes, so averaging them removes more of the variance.
03What is the out-of-bag score?Show answer
Each bootstrap sample leaves out about a third of the training examples. Predicting each example with only the trees that never saw it, and scoring those predictions, estimates performance on new data without a separate validation set.
04In gradient boosting, what does each new tree fit, and why is it called gradient boosting?Show answer
Each tree fits the downhill direction of the loss with respect to the current predictions: minus its gradient. For squared error that is the residual, y minus the prediction, and for log loss it is y − p. Adding a small step of each tree is gradient descent on the predictions.
05Can adding more trees make a model overfit?Show answer
In a random forest, no: more trees only average away more variance, and the error levels off. In boosting, yes: every round fits the training data more closely, so the number of rounds is chosen on a validation set, with early stopping.

Exit ticket

One last question on the main idea of the lesson.

You add more trees to a random forest, and more rounds to gradient boosting. Which can start to overfit?

The random forest, with more trees.Gradient boosting, with more rounds.Neither: more is always better.

Show the answer

B: Gradient boosting, with more rounds. A forest’s trees are averaged, so more of them only make the average steadier: in this lesson its error on new students is 32.5 with 20 trees and 31.8 with 100. Each boosting round fits the training students more closely. With η = 0.1, the validation error is lowest after 33 rounds, 38.6, and 47.6 after 100.