256
$\begingroup$

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?

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

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:

Comparative 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.
| cite | improve this answer | |
$\endgroup$
  • 10
    $\begingroup$ 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. $\endgroup$ – Alexander Rodin Jul 13 '16 at 9:26
  • 2
    $\begingroup$ @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? $\endgroup$ – Alexander Galkin Jul 18 '16 at 19:47
  • $\begingroup$ @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. $\endgroup$ – Alexander Rodin Jul 19 '16 at 11:13
  • 3
    $\begingroup$ In your first sentence you say Boosting decreases bias, but in the comparison table you say it increases predictive force. Are these both true? $\endgroup$ – Ben Lindsay Oct 12 '16 at 15:59
73
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 5
    $\begingroup$ Commenting each of the points to answer why is it so and how it is achieved would be a great improvement in your answer. $\endgroup$ – Tim Dec 16 '15 at 8:12
  • 2
    $\begingroup$ Can you share any document/link which explains that boosting reduce variance and how it does it? Just want to understand in more depth $\endgroup$ – GeorgeOfTheRF Dec 16 '15 at 13:55
  • 1
    $\begingroup$ 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. $\endgroup$ – yuqian Dec 17 '15 at 1:01
46
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ +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/…) $\endgroup$ – Mark Horvath Dec 17 '16 at 21:46
22
$\begingroup$

See my ensemble learning blog post

enter image description here

Sources for this image:

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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.
| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

enter image description here

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.