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?
What's the similarities and differences between these 3 methods:
Which is the best one? And why?
Can you give me an example for each?
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:
Producing a distribution of simple ML models on subsets of the original data.
Combining the distribution into one "aggregated" model.
Here is a short description of all three methods:
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.
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.
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:
Bagging:
parallel ensemble: each model is built independently
aim to decrease variance, not bias
suitable for high variance low bias models (complex models)
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:
sequential ensemble: try to add new models that do well where previous models lack
aim to decrease bias, not variance
suitable for low variance high bias models
an example of a tree based method is gradient boosting
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.
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).
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.
Random Forest
, which eliminate variance and does not have overfitting issue.GBM
and XGBoost
, which eliminate the variance but have overfitting issue.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.