Five decision stumps are fitted to the Wisconsin breast cancer data (569 tumors, 30 measurements of cell nuclei in images of fine-needle aspirates; Wolberg, Mangasarian, Street and Street, 1993), each allowed a single question about one of those measurements. Tested on 171 tumors held out from training, the best two, which ask about the worst concave points and the worst area, are right 90.1% and 90.6% of the time. The other three, on texture, smoothness and compactness, manage between 70.2% and 74.9%. Asked to vote, with the majority deciding, the five stumps are right 88.9% of the time: better than their average member, but worse than their best. Weighted so that the stronger stumps count for more, the same five votes are right 91.8% of the time, better than any one of them.
An ensemble model combines the predictions of several models, called base models or members, into one prediction. The example shows both sides of the idea. A combination can outperform every model in it, and it can also be dragged down by its weaker members. Which happens depends on how accurate the members are, how their errors relate to each other, and how they are combined. This article works out those conditions, for votes and for averages, and introduces the three families of methods that build ensembles on purpose: Bagging, Boosting and Stacking.
What an ensemble is
An ensemble has two parts: a set of base models and a rule for combining them. For classification the simplest rule is the majority vote (with more than two classes, the plurality vote): each model names a class and the most common answer wins. A soft vote averages the predicted class probabilities instead and picks the class with the highest average. For regression the simplest rule is the average of the predicted numbers. Each rule has a weighted version, in which some members count for more than others, and the weights can be fixed in advance or learned from data.
The members can be the same kind of model fitted to different versions of the data, or different kinds of model fitted to the same data. A random forest, which averages hundreds of decision trees grown on resampled data, is the best-known ensemble; this topic covers the general methods it belongs to.
Why a vote can beat its voters
Suppose $B$ classifiers each predict a two-class outcome correctly with probability $p$, and suppose, for the moment, that their errors are independent: whether one is right on a given case says nothing about whether another is. The number of correct votes $S$ on a case then has a binomial distribution, $S \sim \text{Bin}(B, p)$, and with $B$ odd the majority is right when $S > B/2$:
$$\Pr(\text{majority correct}) = \sum_{k = (B+1)/2}^{B} \binom{B}{k} p^k (1 - p)^{B - k}.$$
For three voters, each right with probability 0.7, the majority is right when all three are right, with probability $0.7^3 = 0.343$, or when exactly two are, in one of three ways, with probability $3 \times 0.7^2 \times 0.3 = 0.441$. The total is 0.784, better than any single voter. With eleven voters the sum has six terms, for 6 to 11 correct votes, and comes to 0.9218; its largest term, 0.2568, is the probability of exactly eight correct votes. Dietterich (2000) gives the standard illustration: 21 classifiers, each with error rate 0.3, whose majority is wrong only when 11 or more of them are wrong at once, which happens with probability 0.026. The same calculation gives 0.0264.
| Voters $B$ | $p = 0.45$ | $p = 0.55$ | $p = 0.6$ | $p = 0.7$ |
|---|---|---|---|---|
| 1 | 0.4500 | 0.5500 | 0.6000 | 0.7000 |
| 5 | 0.4069 | 0.5931 | 0.6826 | 0.8369 |
| 11 | 0.3669 | 0.6331 | 0.7535 | 0.9218 |
| 21 | 0.3210 | 0.6790 | 0.8256 | 0.9736 |
| 101 | 0.1562 | 0.8438 | 0.9791 | 1.0000 |
When each voter is better than a coin flip, the majority's accuracy rises toward 1 as voters are added, and the better the voters, the faster it rises. When each voter is worse than a coin flip, the majority's accuracy falls toward 0: a vote of 101 voters each right 45% of the time is right only 15.6% of the time. By the law of large numbers, the fraction of correct votes approaches $p$, so the majority settles on whichever side of one half $p$ is on. Hastie, Tibshirani and Friedman (2009, §8.7) make the same argument for bagging a classifier and note the idea's popular name, the "wisdom of crowds", together with its caveat: the voters must be independent. Voting amplifies competence and amplifies incompetence just as readily, so it needs members that are each better than chance (Dietterich, 2000).
Independence is the catch
Models fitted to the same data make many of the same mistakes, because the hard cases are hard for all of them. A simple way to see what this does to a vote is a model of dependence in which, on each case, with probability $\rho$ all $B$ voters copy one shared vote, which is right with probability $p$, and otherwise they vote independently. Each voter is still right with probability $p$, and the correctness of any two voters has correlation $\rho$. The majority is right with probability
$$\rho\, p + (1 - \rho) \Pr\bigl(\text{Bin}(B, p) > B/2\bigr).$$
As $B$ grows, the second probability goes to 1 (for $p > 1/2$), but the first term does not change: on the fraction $\rho$ of cases where the voters move together, the ensemble is exactly as good as one voter. With $p = 0.7$ the accuracy can never exceed $0.7\rho + (1 - \rho)$, which is 0.97 for $\rho = 0.1$, 0.91 for $\rho = 0.3$ and 0.82 for $\rho = 0.6$, and it gets close to that ceiling after a few dozen voters. A simulation of 200,000 votes of 21 such voters with $\rho = 0.3$ (seed 742) gives an accuracy of 0.8917 against the formula's 0.8915, and a correlation between two voters of 0.302.
This is the classification counterpart of a result derived in Random Forests for averages: $B$ predictions with variance $\sigma^2$ and pairwise correlation $\rho$ average to a prediction with variance $\rho\sigma^2 + (1 - \rho)\sigma^2/B$, which falls toward the floor $\rho\sigma^2$, not toward zero. In both cases adding members removes only the part of their errors that is not shared. Every ensemble method is, in one way or another, a device for making the members' errors less alike without making the members much worse.
Back to the five stumps
The five breast cancer stumps were fitted to 398 tumors (a stratified 70/30 split, the split used in Random Forests) and tested on the other 171. Each stump asks whether one measurement is below a threshold and predicts benign if it is.
| Stump | Rule (benign if) | Test accuracy | Errors |
|---|---|---|---|
| worst concave points | ≤ 0.1423 | 0.901 | 17 |
| worst area | ≤ 874.85 | 0.906 | 16 |
| mean texture | ≤ 19.365 | 0.725 | 47 |
| worst smoothness | ≤ 0.1364 | 0.702 | 51 |
| mean compactness | ≤ 0.0976 | 0.749 | 43 |
| majority vote | 3 of 5 | 0.889 | 19 |
Their mean accuracy is 0.796. Five independent voters with that accuracy would form a majority that is right with probability 0.939, and five independent voters with the stumps' own unequal accuracies would reach 0.945. The actual vote reaches 0.889, so independence is not the whole story. The correlations between the stumps' correctness are small on average, 0.115, but range up to 0.438, and the errors cluster: on 19 tumors three or more stumps are wrong together, against about 10 expected under independence.
The second problem is the unequal accuracy. A majority vote counts every member equally, so the three weak stumps can outvote the two strong ones, and on these data they sometimes do. Weighting fixes this. If the members are independent given the true class and member $k$ is right with probability $p_k$ whichever the true class, the log-odds that a case belongs to a class, given the votes, is the prior log-odds plus $\ln[p_k / (1 - p_k)]$ for each member voting for that class and minus the same amount for each voting against: the reasoning of naive Bayes, applied to votes instead of features. The best combination of independent votes therefore weights each one by the log-odds of its accuracy. Estimating each $p_k$ from the training data gives weights of 2.54 for each of the two strong stumps, 1.41 for compactness, 1.03 for texture and 0.95 for smoothness. The two strong stumps together (5.09) now outweigh the other three (3.39), so the weak stumps decide only when the strong ones disagree. The weighted vote makes 14 errors, an accuracy of 0.918, better than the best stump. AdaBoost gives each of its members a weight of exactly half this log-odds, computed on reweighted data, and Stacking learns the weights by fitting a model to the members' predictions.
Averaging numbers: the ambiguity decomposition
For regression, the effect of averaging can be written exactly, for any set of predictions and any single case, without assumptions about independence. Let $f_1, \dots, f_B$ be the members' predictions for a case with outcome $y$, and $\bar{f} = \frac{1}{B}\sum_k f_k$ their average. Write each member's error as the ensemble's error plus the member's distance from the average, $f_k - y = (\bar{f} - y) + (f_k - \bar{f})$, square, and average over the members:
$$\frac{1}{B}\sum_{k=1}^{B} (f_k - y)^2 = (\bar{f} - y)^2 + \frac{2}{B}(\bar{f} - y)\sum_{k=1}^{B} (f_k - \bar{f}) + \frac{1}{B}\sum_{k=1}^{B} (f_k - \bar{f})^2.$$
The middle sum is zero, because the deviations from an average add to zero. Rearranging,
$$(\bar{f} - y)^2 = \underbrace{\frac{1}{B}\sum_{k} (f_k - y)^2}_{\text{average member error}} - \underbrace{\frac{1}{B}\sum_{k} (f_k - \bar{f})^2}_{\text{ambiguity}}.$$
Krogh and Vedelsby (1995) derived this identity for ensembles of neural networks and called the second term the ambiguity: the spread of the members' predictions around their average, a measure of how much they disagree. It needs no knowledge of $y$, and it cannot be negative, so the squared error of the average is never larger than the average squared error of the members. It is smaller by exactly the amount the members disagree. Averaging the identity over test cases gives the same statement for mean squared errors.
The diabetes study used throughout the regression articles (442 patients, ten baseline measurements, disease progression after a year; Efron, Hastie, Johnstone and Tibshirani, 2004) shows the identity at work. Three models were fitted to 300 patients and tested on the other 142: least squares on all ten inputs, 20-nearest-neighbor regression on standardized inputs (see K-Nearest Neighbors) and a depth-3 regression tree.
| Model | Test MSE | Test $R^2$ |
|---|---|---|
| least squares | 3,086.1 | 0.420 |
| 20-nearest neighbors | 3,173.6 | 0.404 |
| depth-3 tree | 4,287.5 | 0.195 |
| average of the three | 3,136.5 | 0.411 |
| average of the first two | 3,008.0 | 0.435 |
For the three-model average, the members' mean MSE is 3,515.8 and their mean ambiguity is 379.3; the difference, 3,136.5, is the ensemble's MSE to the last digit. The average beats the typical member by a wide margin but not the best one, because the tree is much worse than the others, and much of its disagreement with them is simply error. Averaging only least squares and nearest neighbors does better than either: their mean MSE is 3,129.9 and their ambiguity 121.9, enough to bring the average to 3,008.0, below the better member's 3,086.1. Their errors are highly correlated, 0.927, yet the remaining disagreement is worth more than the gap in accuracy between them.
The identity explains the shape of every ensemble method. To improve on the average member, the members must disagree; to improve on the best member, they must disagree by more than they differ in accuracy. Disagreement bought by making members worse, as with the depth-3 tree, gains nothing.
Where diversity comes from
Identical models make identical predictions, and combining them changes nothing. Krogh and Vedelsby (1995) put the point directly: there is no more information in a million identical networks than in one. Ensemble methods differ mainly in how they make their members different:
- Different data. Bagging fits each member to a bootstrap sample, a random resample of the training cases, so each sees a slightly different dataset.
- Different emphasis. Boosting fits each member to a reweighted version of the data in which the cases the ensemble so far handles badly count for more.
- Different inputs. A random forest restricts each split of each tree to a random subset of the inputs.
- Different algorithms. Stacking combines models built on different assumptions, such as a linear model, a nearest-neighbor model and a forest, and learns how much to trust each.
- Different starting points. Methods that search for a solution from a random start, such as neural networks trained by gradient descent, give different answers on each run, and an average of several runs is often better than any one.
Dietterich (2000) gives three reasons why a combination can be better than the best single model a method can find. The first is statistical: with limited data, many models fit the training data about equally well, and averaging them reduces the risk of choosing a poor one. The second is computational: training procedures such as greedy tree growing and gradient descent find local optima, and combining several runs can come closer to the best model than any run does. The third is representational: a weighted combination of models can represent functions that no single member can, as a sum of axis-aligned decision stumps can approximate a diagonal boundary that no single stump can draw. The Boosting article shows this last case.
Three families of methods
The rest of this topic treats the three standard ways of building an ensemble.
Bagging (bootstrap aggregating; Breiman, 1996a) fits the same kind of model to many bootstrap samples of the training data and averages the results or takes a vote. It reduces variance, so it helps methods whose fitted model changes a lot when the data change, such as fully grown decision trees, and does little for stable methods such as least squares. The members are fitted independently, so they can be fitted in parallel.
Boosting fits models in sequence, each to a version of the data that emphasizes what the ensemble so far gets wrong, and adds them with weights. AdaBoost (Freund and Schapire, 1997) reweights the cases; gradient boosting (Friedman, 2001) fits each new model to the errors of the current ensemble. Boosting builds a flexible model out of simple ones, such as stumps or small trees, and reduces bias as well as variance. Each member depends on the ones before it, so the members must be fitted one at a time.
Stacking (Wolpert, 1992; Breiman, 1996b) combines different kinds of model by fitting a second-level model, the meta model, to their predictions. To keep the meta model from simply trusting whichever member fits its own training data best, it is fitted to cross-validated predictions.
| Bagging | Boosting | Stacking | |
|---|---|---|---|
| Members | one kind, usually flexible (deep trees) | one kind, usually simple (stumps, small trees) | several different kinds |
| Source of diversity | bootstrap samples | reweighted cases or fitted residuals | different algorithms |
| Combination | plain average or vote | weighted sum, weights set by the algorithm | meta model fitted to cross-validated predictions |
| Fitting | parallel | sequential | members in parallel, then the meta model |
| Mainly reduces | variance | bias, and variance | depends on the members |
The table is a summary of typical use, not a set of rules. Bagging can be applied to any model, boosting to trees of any size, and stacking can include bagged and boosted members among its base models.
Costs and limits
An ensemble gives up the readability of its members. One stump or one small tree can be checked by a person; a weighted vote of 500 trees cannot, and has to be understood through summaries such as the variable importance measures described in Random Forests. It also costs more to fit, store and evaluate, roughly in proportion to the number of members.
The gains have limits too. Combining models cannot remove errors they all share, as the correlated-voter calculation shows, and members worse than chance make a vote worse. When one model already captures the structure in the data, combining it with weaker models may add little: on the diabetes data, a linear regression on the ten inputs predicts better under cross-validation than a random forest of 500 trees (see Random Forests), and the Stacking article finds that a stack of four models does no better than the linear model alone. Whether an ensemble is worth its costs is an empirical question, answered by comparing it with its best member on data neither has seen (Cross-Validation).
In Python
scikit-learn combines fitted models of different kinds with VotingClassifier and VotingRegressor:
from sklearn.datasets import load_breast_cancer
from sklearn.ensemble import RandomForestClassifier, VotingClassifier
from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import StratifiedKFold, cross_val_score
from sklearn.naive_bayes import GaussianNB
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
X, y = load_breast_cancer(return_X_y=True)
vote = VotingClassifier(
estimators=[('logistic', make_pipeline(StandardScaler(), LogisticRegression(max_iter=5000))),
('bayes', GaussianNB()),
('forest', RandomForestClassifier(500, random_state=0))],
voting='soft') # 'hard' counts votes; 'soft' averages probabilities
cv = StratifiedKFold(10, shuffle=True, random_state=0)
print(cross_val_score(vote, X, y, cv=cv).mean())
voting='hard' is the majority vote and voting='soft' averages the predicted probabilities; the optional weights argument gives a weighted vote. The bagging, boosting and stacking classes are introduced in the articles that follow. The numbers in this article are computed by tools/experiments/data-science/introduction-to-ensemble-models.py in the site's repository.
References
- Breiman, L. (1996a). Bagging predictors. Machine Learning, 24(2), 123–140. Read in the technical report version (No. 421, Department of Statistics, University of California, Berkeley, September 1994). record · 3 pages
- Breiman, L. (1996b). Stacked regressions. Machine Learning, 24(1), 49–64. record · 2 pages
- Dietterich, T. G. (2000). Ensemble methods in machine learning. In J. Kittler and F. Roli (Eds.), Multiple Classifier Systems (Lecture Notes in Computer Science, Vol. 1857, pp. 1–15). Springer. record
- Efron, B., Hastie, T., Johnstone, I., and Tibshirani, R. (2004). Least angle regression. The Annals of Statistics, 32(2), 407–499. record · 12 pages
- Freund, Y., and Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1), 119–139. Read in the authors' preprint of December 19, 1996. record · 2 pages
- Friedman, J. H. (2001). Greedy function approximation: A gradient boosting machine. The Annals of Statistics, 29(5), 1189–1232. Read in the author's preprint (IMS 1999 Reitz Lecture, modified April 19, 2001). record · 2 pages
- Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. record · 23 pages
- Krogh, A., and Vedelsby, J. (1995). Neural network ensembles, cross validation, and active learning. In G. Tesauro, D. Touretzky and T. Leen (Eds.), Advances in Neural Information Processing Systems 7 (pp. 231–238). MIT Press. record
- Wolberg, W., Mangasarian, O., Street, N., and Street, W. (1993). Breast Cancer Wisconsin (Diagnostic) [Data set]. UCI Machine Learning Repository. https://doi.org/10.24432/C5DW2B record · 14 pages
- Wolpert, D. H. (1992). Stacked generalization. Neural Networks, 5(2), 241–259. Read in the Los Alamos National Laboratory technical report version (LA-UR-90-3460), which quotations follow. record · 2 pages