Bootstrap aggregating

Given a standard training set ${\displaystyle D}$ of size n, bagging generates m new training sets ${\displaystyle D_{i}}$, each of size n′, by sampling from D uniformly and with replacement. By sampling with replacement, some observations may be repeated in each ${\displaystyle D_{i}}$. If n′=n, then for large n the set ${\displaystyle D_{i}}$ is expected to have the fraction (1 - 1/e) (≈63.2%) of the unique examples of D, the rest being duplicates.[1] This kind of sample is known as a bootstrap sample. Sampling with replacement ensures each bootstrap is independent from its peers, as it does not depend on previous chosen samples when sampling. Then, m models are fitted using the above m bootstrap samples and combined by averaging the output (for regression) or voting (for classification).

An illustration for the concept of bootstrap aggregating

Bagging leads to "improvements for unstable procedures",[2] which include, for example, artificial neural networks, classification and regression trees, and subset selection in linear regression.[3] Bagging was shown to improve preimage learning.[4][5] On the other hand, it can mildly degrade the performance of stable methods such as K-nearest neighbors.[2]

While the techniques described above utilize random forests and bagging (otherwise known as bootstrapping), there are certain techniques that can be used in order to improve their execution and voting time, their prediction accuracy, and their overall performance. The following are key steps in creating an efficient random forest:

1. Specify the maximum depth of trees: Instead of allowing your random forest to continue until all nodes are pure, it is better to cut it off at a certain point in order to further decrease chances of overfitting.
2. Prune the dataset: Using an extremely large dataset may prove to create results that is less indicative of the data provided than a smaller set that more accurately represents what is being focused on.
   • Continue pruning the data at each node split rather than just in the original bagging process.
3. Decide on accuracy or speed: Depending on the desired results, increasing or decreasing the number of trees within the forest can help. Increasing the number of trees generally provides more accurate results while decreasing the number of trees will provide quicker results.

Flow chart of the bagging algorithm when used for classification

For classification, use a training set ${\displaystyle D}$, Inducer ${\displaystyle I}$ and the number of bootstrap samples ${\displaystyle m}$ as input. Generate a classifier ${\displaystyle C^{*}}$ as output[14]

1. Create ${\displaystyle m}$ new training sets ${\displaystyle D_{i}}$, from ${\displaystyle D}$ with replacement
2. Classifier ${\displaystyle C_{i}}$ is built from each set ${\displaystyle D_{i}}$ using ${\displaystyle I}$ to determine the classification of set ${\displaystyle D_{i}}$
3. Finally classifier ${\displaystyle C^{*}}$ is generated by using the previously created set of classifiers ${\displaystyle C_{i}}$ on the original data set ${\displaystyle D}$, the classification predicted most often by the sub-classifiers ${\displaystyle C_{i}}$ is the final classification

for i = 1 to m {
    D' = bootstrap sample from D    (sample with replacement)
    Ci = I(D')
}
C*(x) = argmax #{i:Ci(x)=y}         (most often predicted label y)
         y∈Y   

To illustrate the basic principles of bagging, below is an analysis on the relationship between ozone and temperature (data from Rousseeuw and Leroy (1986), analysis done in R).

The relationship between temperature and ozone appears to be nonlinear in this data set, based on the scatter plot. To mathematically describe this relationship, LOESS smoothers (with bandwidth 0.5) are used. Rather than building a single smoother for the complete data set, 100 bootstrap samples were drawn. Each sample is composed of a random subset of the original data and maintains a semblance of the master set’s distribution and variability. For each bootstrap sample, a LOESS smoother was fit. Predictions from these 100 smoothers were then made across the range of the data. The black lines represent these initial predictions. The lines lack agreement in their predictions and tend to overfit their data points: evident by the wobbly flow of the lines.

By taking the average of 100 smoothers, each corresponding to a subset of the original data set, we arrive at one bagged predictor (red line). The red line's flow is stable and does not overly conform to any data point(s).

Advantages:

• Many weak learners aggregated typically outperform a single learner over the entire set, and has less overfit
• Removes variance in high-variance low-bias weak learner,[15] which can improve efficiency (statistics)
• Can be performed in parallel, as each separate bootstrap can be processed on its own before combination[16]

Disadvantages:

• For weak learner with high bias, bagging will also carry high bias into its aggregate[15]
• Loss of interpretability of a model.
• Can be computationally expensive depending on the data set

The concept of bootstrap aggregating is derived from the concept of bootstrapping which was developed by Bradley Efron.[17] Bootstrap aggregating was proposed by Leo Breiman who also coined the abbreviated term "bagging" (bootstrap aggregating). Breiman developed the concept of bagging in 1994 to improve classification by combining classifications of randomly generated training sets. He argued, "If perturbing the learning set can cause significant changes in the predictor constructed, then bagging can improve accuracy".[3]

• Boosting (meta-algorithm)
• Bootstrapping (statistics)
• Cross-validation (statistics)
• Out-of-bag error
• Random forest
• Random subspace method (attribute bagging)
• Resampled efficient frontier
• Predictive analysis: Classification and regression trees

• Breiman, Leo (1996). "Bagging predictors". Machine Learning. 24 (2): 123–140. CiteSeerX 10.1.1.32.9399. doi:10.1007/BF00058655. S2CID 47328136.
• Alfaro, E., Gámez, M. and García, N. (2012). "adabag: An R package for classification with AdaBoost.M1, AdaBoost-SAMME and Bagging". {{cite journal}}: Cite journal requires |journal= (help)CS1 maint: multiple names: authors list (link)
• Kotsiantis, Sotiris (2014). "Bagging and boosting variants for handling classifications problems: a survey". Knowledge Eng. Review. 29 (1): 78–100. doi:10.1017/S0269888913000313. S2CID 27301684.
• Boehmke, Bradley; Greenwell, Brandon (2019). "Bagging". Hands-On Machine Learning with R. Chapman & Hall. pp. 191–202. ISBN 978-1-138-49568-5.