liveBook · Manning

Chapter 9: From single trees to random forests: Leo Breiman and the logic of ensemble learning

What you will learn in chapter 9 of Timeless Algorithms, The Foundational Ideas

This introduction explains why unstable decision trees can benefit from an ensemble and contrasts Breiman’s approach to generalization with Vapnik’s.

After this chapter you will be able to

What it builds on

Section by section

Introduction

This introduction explains why unstable decision trees can benefit from an ensemble and contrasts Breiman’s approach to generalization with Vapnik’s.

Key terms: decision trees, unstable, generalize, randomness, diversity, aggregation, ensemble, generalization, support vector machines

9.1 The strengths and limitations of single decision trees

This section explains how a single decision tree builds and makes predictions, why it is useful, and why its flexibility can make it unreliable on new data.

Key terms: root, split, impurity, entropy, information gain, node, conditional decisions, nonlinear relationships, interactions, plotted tree

9.1.1 Instability and sensitivity to early splits

This section explains why greedy split choices make a single decision tree sensitive to small changes in its training data, especially near the root.

Key terms: greedily, candidate splits, immediate improvement, root splits, features, thresholds, branches, instability, training sample, new observations

9.1.2 Depth, overfitting, and variance

This section explains how deeper decision trees gain expressive power but become more prone to overfitting and high variance.

Key terms: split, node, depth, expressive power, noise, overfitting, training performance, generalization, high-variance models, variance

9.1.3 Why pruning is not enough

The section explains why pruning improves a decision tree but cannot remove its sample-dependent instability, motivating the use of varied trees whose predictions are combined.

Key terms: maximum depth, minimum number of observations, minimum improvement, pruned, generalization, pruned tree, instability, single sample, variance, nonlinear relationships

9.2 Bagging: randomness in the observations

The section explains how bagging turns the sensitivity of unstable models, especially decision trees, into more stable predictions by combining models trained on varied observation samples.

Key terms: bagging, unstable learning methods, voting, averaging, random forests, randomness in observations, randomness in features

9.2.1 How bagging creates different training sets

This section explains how bootstrap sampling gives bagged decision trees different training observations, why some observations are omitted, and how those differences can produce varied trees whose predictions are combined.

Key terms: bagging, bootstrap sampling, sampling with replacement, aggregation, out-of-bag observations, bootstrap sample, decision tree, candidate splits

9.2.2 Aggregation: turning variation into stability

This section explains how bagging combines tree predictions and why aggregation can make an ensemble more stable than its individual trees.

Key terms: bagging, classification, regression, votes, averages, aggregation, bootstrap sample, ensemble, variance, sample-specific effects

9.2.3 What bagging fixes—and what it does not

This section explains how bagging stabilizes decision trees, why correlated trees limit its gains, and how random forests add diversity beyond bagging.

Key terms: bagging, bootstrap sample, high variance, aggregation, bootstrap sampling, correlated errors, diversity, early splits, random forests, randomly selected subset

9.3 Random forests: randomness in the features

The section explains how random forests add random feature selection to bagging so that trees make less similar errors and aggregation works better.

Key terms: bagging, bootstrap sampling, predictors, random feature selection, split, aggregation, dominant predictors, diversity, correlated errors

9.3.1 Random feature selection at each split

This section explains how random forests restrict the features considered at each split while retaining ordinary tree splitting and adding diversity beyond bagging.

Key terms: input features, random subset, node, split, m, p, bootstrap sampling, random feature selection, with replacement, without replacement

9.3.2 Creating diversity by limiting choice

This section explains how limiting feature choices at each split makes random-forest trees less alike, and why that diversity must be balanced against each tree’s predictive strength.

Key terms: bagging, dominant predictor, random feature selection, feature subset, early splits, structural diversity, correlated, voting, averaging, variance

9.3.3 The complete random forest algorithm

This section explains how random forests train varied decision trees using bootstrap samples and random feature subsets, then combine their predictions.

Key terms: bootstrap sample, random feature selection, greedy recursive splitting, impurity or loss criterion, aggregation, classification, regression, votes, averaged

9.4 Why random forests generalize

This section explains why random forests generalize: they combine useful individual trees whose errors differ, then stabilize predictions through aggregation.

Key terms: strength, low correlation, random feature selection, forest margin, geometric margin, variance, diversification, aggregation, limiting level of generalization error, individual strength

9.4.1 Classification margins: measuring collective confidence

This section defines Breiman’s classification margin from tree votes and shows how margin signs and distributions help evaluate a random forest without changing how it is trained.

Key terms: Breiman’s margin, known class, vote share, generalization error, margin distribution, classification error, out-of-bag margins, geometric margin, candidate features, formal margin

9.4.2 Balancing tree strength and correlation

The section explains why random forests generalize best when their trees make useful predictions without making the same errors, and how feature selection affects that balance.

Key terms: forest margin, strength, correlation, generalization error, upper bound, average correlation, regression forest, prediction variance, systematic bias, mean squared error

9.4.3 Why adding trees stabilizes the forest

This section explains why adding randomized trees stabilizes a forest’s predictions without guaranteeing that those predictions are accurate.

Key terms: depth, bootstrap sample, randomly selected feature subsets, limiting value, expected prediction, expected vote share, out-of-bag error, tree strength, correlation, finite ensemble

9.5 Out-of-bag evaluation

The section explains how bootstrap sampling lets a random forest evaluate its predictions using out-of-bag observations, and where that evaluation is useful or limited.

Key terms: bootstrap sample, out-of-bag observations, out-of-bag prediction, internal validation, out-of-bag error rate, mean squared error, mean absolute error, k-fold cross-validation, fixed folds, overlapping validation sets

9.6 Variable importance: recovering interpretation

The section explains why feature importance is harder to interpret in a random forest than in a single tree and introduces ways to measure it across the ensemble.

Key terms: decision tree, splits, importance scores, random forest, out-of-bag observations, feature, variable importance

9.6.1 Measuring variable importance

This section explains how random forests measure variable importance through out-of-bag permutation and accumulated split improvements, and how to interpret the resulting scores.

Key terms: permutation importance, out-of-bag performance, baseline error, permutation-importance score, classification error, mean squared error, impurity-based importance, weighted reduction, Gini impurity, entropy

9.6.2 interpreting importance responsibly

This section explains what random-forest variable-importance scores can reveal and why redundancy, scoring methods, causality, and global aggregation limit their interpretation.

Key terms: permutation importance, correlated predictors, redundancy, impurity-based importance, splitting points, sample-specific patterns, variable importance, causality, proxy, intervention

9.7 Random forests versus support vector machines

This section contrasts how support vector machines and random forests achieve generalization, use margins, and provide evidence for interpreting predictions.

Key terms: generalization, variance, soft-margin SVM, random forests, aggregation, margin, geometric margin, classification violations, random forest margin, support vectors

9.8 The enduring legacy of random forests

The section explains why random forests endure: they organize unstable trees into a reliable ensemble, provide evidence about performance, and call for a different kind of interpretation.

Key terms: bagging, bootstrap samples, random feature selection, tree strength, correlation, aggregation, structured or tabular data, out-of-bag observations, variable importance, predictive performance

9.9 Summary

Where this is used later

Concepts explained in this chapter

← Chapter 8: Learning to generalize: Vladimir Vapnik and support vector machines Chapter 10: From foundational algorithms to modern AI: David J.C. MacKay and the unifying logic of learning →

These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.