Bagging and Other Ensemble Methods

A panel of forecasters

Imagine five forecasters who each predict tomorrow’s temperature. Each one is sometimes too high and sometimes too low. Take the average of their forecasts, and the high errors and low errors can cancel. That is the idea of model averaging: train several models, combine their predictions, and let the average answer. The methods built on it are called ensemble methods.

Drag the five forecasters, or use their sliders. Each numbered dot is one forecaster’s error, meaning its prediction minus the truth, which sits at zero. The teal diamond is the average error.

The readout gives the two numbers to compare. The average error is , the mean of the five errors. The ensemble’s squared error is the square of that average, . The readout also shows the average of the members’ squared errors. Squaring an average never gives a larger number than averaging the squares, so the ensemble’s squared error is never larger than that average. This inequality is added here and is not printed in the book.

Averaging and error correlation

The book studies a set of regression models. Model makes an error on each example. The errors have zero mean and follow a multivariate normal distribution, a bell-shaped spread for several numbers at once in which pairs of numbers can move together. The book states two properties of it:

Here is the variance of one model’s error, and is the covariance between the errors of two different models. The error of the average prediction is the mean of the individual errors, and Equations 7.50 and 7.51 give its expected squared error.

Read 7.51 term by term. The first term, , is the part that averaging shrinks, because it falls as the number of models grows. The second term does not shrink, because it depends on how much the models agree. Two extremes matter:

• Perfectly correlated errors. When , the expression equals for every . Averaging does not help at all.
• Unrelated errors. When , the expression equals , so the expected squared error falls in proportion to .

The dots come from 1500 random draws at each size, with errors built from one shared random part and one private part. They scatter around the curve by about the amount that sampling noise allows, which is what Equation 7.51 predicts.

Resampling with replacement

Model averaging helps only when the models disagree. Bagging, short for bootstrap aggregating, makes them disagree by giving each model its own training set. To build one set, draw as many examples as the original set has, one at a time, and put each draw back before the next. The same example can appear twice, and some examples never appear. The result is a bootstrap resample.

Model is trained on resample . Each resample has the same size as the original set, which has examples. The book says that on average about two thirds of the original examples appear in each resample. The expected fraction of distinct examples is with the same , which tends to 1 − 1/e for large . This formula is added here and is not printed in the book. The book’s “around 2/3” is a coarse figure, because the limit is about 0.632, a little below two thirds.

Each bar counts how often one original example was drawn. A bar of zero is an example the model never sees in that resample, and a bar of three or more is a duplicate that gets extra weight.

Bagged votes

Figure 7.5 in the book shows the idea with handwritten digits. A detector trained on one resample learns a loop at the top of the digit, and a detector trained on another learns a loop at the bottom. Each rule is brittle on its own. Averaging the votes gives full confidence only where both loops are present. The demo below rebuilds this on a one-dimensional toy problem, because every boundary can be computed and seen on a line. This rebuild is not the book’s figure.

Each member draws a resample, finds the mean position of each class in that resample, and puts its boundary halfway between the two means. If a resample misses one class, the member uses the boundary from the full dataset. The vote at a position is the share of members that call class 1, written .

Each member’s boundary is a sharp edge. The vote blends those edges, so it rises from 0 to 1 over the range where the boundaries disagree. With one member the vote is a step. With many members it is a ramp, and it reaches 1 only where every member calls the position class 1.

Diversity, boosting and cost

Bagging needs the members to differ. Neural networks differ even without resampling. Random initial parameters, random minibatch order, different hyperparameters, and non-deterministic implementations are often enough to make members make partly independent errors. A neural network ensemble can therefore gain from averaging while every member trains on the same dataset.

The price is compute. An ensemble of networks costs roughly times the training and the memory, and the same factor applies at test time. This is why the book notes that benchmark papers usually compare single models, while machine learning contests are usually won by averaging dozens of models, as in the Netflix Grand Prize.

Boosting builds the opposite kind of ensemble. Its ensemble has higher capacity than its members. The book mentions it for neural networks, where networks or hidden units are added one at a time. This module does not construct a boosting algorithm.

The curve for chosen correlation flattens quickly. Each extra model costs the same as the last one, but the shared part of the error stays. Only models with weakly related errors keep gaining cheaply.

• The average of models has an expected squared error of times plus times . The shared part limits the gain.
• With perfectly correlated errors averaging does nothing. With unrelated errors the expected squared error falls in proportion to .
• Bagging trains each model on a bootstrap resample. For large datasets about 63% of the original examples appear in each resample.
• Neural networks gain from averaging because random initialization, minibatch order and hyperparameters make their errors differ.
• Averaging costs about times the compute, which is why benchmarks usually report single models.

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 7.11 (pages 256–258), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.