Bagging, boosting and stacking in machine learning

What's the similarities and differences between these 3 methods:

• Bagging,
• Boosting,
• Stacking?

Which is the best one? And why?

Can you give me an example for each?

• for a textbook reference, I recommend: " Ensemble methods: foundations and algorithms" by Zhou, Zhi-Hua – Vadim Smolyakov Jul 2 '17 at 18:18
• See here a related question. – Ricardo Cruz Oct 31 '17 at 22:11

All three are so-called "meta-algorithms": approaches to combine several machine learning techniques into one predictive model in order to decrease the variance (bagging), bias (boosting) or improving the predictive force (stacking alias ensemble).

Every algorithm consists of two steps:

1. Producing a distribution of simple ML models on subsets of the original data.

2. Combining the distribution into one "aggregated" model.

Here is a short description of all three methods:

1. Bagging (stands for Bootstrap Aggregating) is a way to decrease the variance of your prediction by generating additional data for training from your original dataset using combinations with repetitions to produce multisets of the same cardinality/size as your original data. By increasing the size of your training set you can't improve the model predictive force, but just decrease the variance, narrowly tuning the prediction to expected outcome.

2. Boosting is a two-step approach, where one first uses subsets of the original data to produce a series of averagely performing models and then "boosts" their performance by combining them together using a particular cost function (=majority vote). Unlike bagging, in the classical boosting the subset creation is not random and depends upon the performance of the previous models: every new subsets contains the elements that were (likely to be) misclassified by previous models.

3. Stacking is a similar to boosting: you also apply several models to your original data. The difference here is, however, that you don't have just an empirical formula for your weight function, rather you introduce a meta-level and use another model/approach to estimate the input together with outputs of every model to estimate the weights or, in other words, to determine what models perform well and what badly given these input data.

Here is a comparison table: As you see, these all are different approaches to combine several models into a better one, and there is no single winner here: everything depends upon your domain and what you're going to do. You can still treat stacking as a sort of more advances boosting, however, the difficulty of finding a good approach for your meta-level makes it difficult to apply this approach in practice.

Short examples of each:

1. Bagging: Ozone data.
2. Boosting: is used to improve optical character recognition (OCR) accuracy.
3. Stacking: is used in classification of cancer microarrays in medicine.
• It seems like your boosting definition is different from the one in wiki (that you linked for) or in this paper. Both of them say that in boosting next classifier uses results of previously trained ones, but you don't mentioned that. The method you describe in other hand resembles some of voting/model averaging techniques. – Alexander Rodin Jul 13 '16 at 9:26
• @a-rodin: Thank you for pointing this important aspect, I completely re-wrote this section to better reflect this. As to your second remark, my understanding is that boosting is also a type of voting/averaging, or did I understand you wrong? – Alexander Galkin Jul 18 '16 at 19:47
• @AlexanderGalkin I had in mind Gradient boosting at the time of commenting: it doesn't looks like voting but rather as an iterative function approximation technique. However e.g. AdaBoost looks more like voting, so I won't argue about it. – Alexander Rodin Jul 19 '16 at 11:13
• In your first sentence you say Boosting decreases bias, but in the comparison table you say it increases predictive force. Are these both true? – Ben Lindsay Oct 12 '16 at 15:59

Bagging:

1. parallel ensemble: each model is built independently

2. aim to decrease variance, not bias

3. suitable for high variance low bias models (complex models)

4. an example of a tree based method is random forest, which develop fully grown trees (note that RF modifies the grown procedure to reduce the correlation between trees)

Boosting:

1. sequential ensemble: try to add new models that do well where previous models lack

2. aim to decrease bias, not variance

3. suitable for low variance high bias models

4. an example of a tree based method is gradient boosting

• Commenting each of the points to answer why is it so and how it is achieved would be a great improvement in your answer. – Tim Dec 16 '15 at 8:12
• Can you share any document/link which explains that boosting reduce variance and how it does it? Just want to understand in more depth – GeorgeOfTheRF Dec 16 '15 at 13:55
• Thanks Tim, I'll add some comments later. @ML_Pro, from the procedure of boosting (e.g. page 23 of cs.cornell.edu/courses/cs578/2005fa/…), it's understandable that boosting can reduce bias. – yuqian Dec 17 '15 at 1:01

Just to elaborate on Yuqian's answer a bit. The idea behind bagging is that when you OVERFIT with a nonparametric regression method (usually regression or classification trees, but can be just about any nonparametric method), you tend to go to the high variance, no (or low) bias part of the bias/variance tradeoff. This is because an overfitting model is very flexible (so low bias over many resamples from the same population, if those were available) but has high variability (if I collect a sample and overfit it, and you collect a sample and overfit it, our results will differ because the non-parametric regression tracks noise in the data). What can we do? We can take many resamples (from bootstrapping), each overfitting, and average them together. This should lead to the same bias (low) but cancel out some of the variance, at least in theory.

Gradient boosting at its heart works with UNDERFIT nonparametric regressions, that are too simple and thus aren't flexible enough to describe the real relationship in the data (i.e. biased) but, because they are under fitting, have low variance (you'd tend to get the same result if you collect new data sets). How do you correct for this? Basically, if you under fit, the RESIDUALS of your model still contain useful structure (information about the population), so you augment the tree you have (or whatever nonparametric predictor) with a tree built on the residuals. This should be more flexible than the original tree. You repeatedly generate more and more trees, each at step k augmented by a weighted tree based on a tree fitted to the residuals from step k-1. One of these trees should be optimal, so you either end up by weighting all these trees together or selecting one that appears to be the best fit. Thus gradient boosting is a way to build a bunch of more flexible candidate trees.

Like all nonparametric regression or classification approaches, sometimes bagging or boosting works great, sometimes one or the other approach is mediocre, and sometimes one or the other approach (or both) will crash and burn.

Also, both of these techniques can be applied to regression approaches other than trees, but they are most commonly associated with trees, perhaps because it is difficult to set parameters so as to avoid under fitting or overfitting.

• +1 for the overfit = variance, underfit = bias argument! One reason for using decision trees is that they are structurally unstable hence benefit more from slight changes of conditions. (abbottanalytics.com/assets/pdf/…) – Mark Horvath Dec 17 '16 at 21:46 Sources for this image:

To recap in short, Bagging and Boosting are normally used inside one algorithm, while Stacking is usually used to summarize several results from different algorithms.

• Bagging: Bootstrap subsets of features and samples to get several predictions and average(or other ways) the results, for example, Random Forest, which eliminate variance and does not have overfitting issue.
• Boosting: The difference from Bagging is that later model is trying to learn the error made by previous one, for example GBM and XGBoost, which eliminate the variance but have overfitting issue.
• Stacking: Normally used in competitions, when one uses multiple algorithms to train on the same data set and average(max, min or other combinations) the result in order to get a higher accuracy of prediction.

both bagging and boosting use a single learning algorithm for all steps; but they use different methods on handling training samples. both are ensemble learning method that combines decisions from multiple models
Bagging:
1. resamples training data to get M subsets (bootstrapping);
2. trains M classifiers(same algorithm) based on M datasets(different samples);
3. final classifier combines M outputs by voting;
samples weight equally;
classifiers weight equally;
decreases error by decreasing the variance
Boosting: here focus on adaboost algorithm
1. start with equal weight for all samples in the first round;
2. in the following M-1 rounds, increase weights of samples which are misclassified in last round, decrease weights of samples correctly classified in last round
3. using a weighted voting, final classifier combines multiple classifiers from previous rounds, and give larger weights to classifiers with less misclassifications.
step-wise reweights samples; weights for each round based on results from last round
re-weight samples(boosting) instead of resampling(bagging).

Bagging and boosting tend to use many homogeneous models.

Stacking combines results from heterogenous model types.

As no single model type tends to be the best fit across any entire distribution you can see why this may increase predictive power.