Bagging, boosting and stacking in machine learning

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

See my ensemble learning blog post

Sources for this image:

• Wikipedia
• sklearn

Answer 5

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.

Answer 6

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).

Answer 7

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.

Answer 8

Bagging

Bootstrap AGGregatING (Bagging) is an ensemble generation method that uses variations of samples used to train base classifiers. For each classifier to be generated, Bagging selects (with repetition) N samples from the training set with size N and train a base classifier. This is repeated until the desired size of the ensemble is reached.

Bagging should be used with unstable classifiers, that is, classifiers that are sensitive to variations in the training set such as Decision Trees and Perceptrons.

Random Subspace is an interesting similar approach that uses variations in the features instead of variations in the samples, usually indicated on datasets with multiple dimensions and sparse feature space.

Boosting

Boosting generates an ensemble by adding classifiers that correctly classify “difficult samples”. For each iteration, boosting updates the weights of the samples, so that, samples that are misclassified by the ensemble can have a higher weight, and therefore, higher probability of being selected for training the new classifier.

Boosting is an interesting approach but is very noise sensitive and is only effective using weak classifiers. There are several variations of Boosting techniques AdaBoost, BrownBoost (…), each one has its own weight update rule in order to avoid some specific problems (noise, class imbalance …).

Stacking

Stacking is a meta-learning approach in which an ensemble is used to “extract features” that will be used by another layer of the ensemble. The following image (from Kaggle Ensembling Guide) shows how this works.

First (Bottom) several different classifiers are trained with the training set, and their outputs (probabilities) are used to train the next layer (middle layer), finally, the outputs (probabilities) of the classifiers in the second layer are combined using the average (AVG).

There are several strategies using cross-validation, blending and other approaches to avoid stacking overfitting. But some general rules are to avoid such an approach on small datasets and try to use diverse classifiers so that they can “complement” each other.

Stacking has been used in several machine learning competitions such as Kaggle and Top Coder. It is definitely a must-know in machine learning.