Ensemble method
Topic of Ensembles, random forests, and boosting, part of Statistical learning · Also in Ensembles, random forests, and boosting
Ensemble method
| Type | Topic |
| Taught in | Ensembles, random forests, and boosting · Ensembles, random forests, and boosting |
| Part | Statistical learning |
| Questions using it | 1 |
A predictor that combines many fitted models by averaging or voting. It helps when the members are individually reasonable and their errors disagree; bagging, random forests and boosting are the main constructions.
In Ensembles, random forests, and boosting
If one tree changes substantially when the training sample is perturbed, fit many perturbed versions and combine their predictions. Bagging creates those versions by bootstrap resampling. A random forest also restricts which predictors compete at each split. Boosting takes a different route: each new learner responds to the current ensemble’s errors. This page derives what averaging guarantees, then the extra choices these algorithms make.
In Ensembles, random forests, and boosting, continued
There are two reasons to combine learners. Averaging can cancel variation among reasonably useful fits. Sequential correction can target structure left unexplained by an earlier fit. Tukey’s twicing applies a smoother to its own residuals, an early example of the second idea. Neither principle says that collecting arbitrary bad models makes a good one.
An error decomposition for regression
Main article: Ensemble error decomposition
Classification error is an indicator, and an average of indicators is not itself the indicator of a majority vote, so the clean algebra starts with a quantitative response. Suppose T models predict a number, with functions f_1,\ldots,f_T, and the ensemble predicts their average
f(x)=\frac1T\sum_{t=1}^T f_t(x).
Theorem 1 (Squared error of an average) If the response at this x is y, the squared error of the average splits into the average squared error of the members minus the sample variance of the members about their average:
\bigl(f(x)-y\bigr)^2 =\frac1T\sum_{t=1}^T\bigl(f_t(x)-y\bigr)^2 -\frac1T\sum_{t=1}^T\bigl(f_t(x)-f(x)\bigr)^2.
Write f_t-y=(f_t-f)+(f-y) and square:
(f_t-y)^2=(f_t-f)^2+2(f_t-f)(f-y)+(f-y)^2.
Average over t. The cross term vanishes because \frac1T\sum_t(f_t-f)=0 by definition of the average, and what remains is
\frac1T\sum_{t=1}^T(f_t-y)^2 =\frac1T\sum_{t=1}^T(f_t-f)^2+(f-y)^2,
which rearranges to the display. All three terms are non-negative. The squared error of the ensemble is therefore at most the average squared error of its members, and the gap is the diversity, the sample variance of the members about their average. The algebra used only the definition of the average and the expansion of a square. No model for y was required.
The design requirement is that the members be reasonably accurate, so that the first term is tolerable, and that they disagree, so that the diversity term is large. If every member were already the regression function, the diversity term would be zero and averaging would change nothing. The identity also applies componentwise to averaged class probabilities under squared error. It does not give the same guarantee for the zero–one loss after a majority vote, and it compares the ensemble with the average member, not with the best member. Diversity and individual accuracy cannot be varied independently without changing the first term. Adding noise merely to make predictors disagree need not help.
Where disagreement comes from
Main article: Where disagreement comes from
Separate variation caused by the dataset from variation caused by the fitting algorithm. A deterministic tree can be sensitive to a small data change. A neural network can also change because of its initial weights. Convexity addresses the optimisation problem, not sensitivity to data: a convex fit can still be unstable when the design is poorly conditioned. Evaluate stability in the setting at hand.
Two kinds of base learner do supply disagreement. One has many parameters relative to the sample and is hard to optimise, so different runs stop in different places. The other is constrained in size or structure and cannot fit the sample in only one way, so a small change in the data produces a different constrained fit. Trees are in the second group. Networks are in the first.
An average is already an ensemble in a setting that has nothing to do with classifiers. A signal from a distant spacecraft is received together with noise. Sending the same signal repeatedly and averaging the receptions lets independent noise cancel at the rate the central limit theorem describes, and leaves the signal. Each noisy reception is the analogue of one flawed classifier. The next two sections build the average in different ways: random forests, which average trees that were made to disagree, and boosting, which adds a learner aimed at the residual of the ones already fitted.
Used in
- Taught in Ensembles, random forests, and boosting · Ensembles, random forests, and boosting
- Also used in Support vector machines
- Questions that use it (1) — A tempting wrong turn (answer)
- All 7 questions on Ensembles, random forests, and boosting
See also
Bagging · Random forest · Boosting · AdaBoost · Squared error of an average · The reweighted error is one half · Why averaging helps · Ensemble error decomposition