Bootstrap aggregating, commonly called bagging, is an ensemble meta-algorithm in Machine learning designed to improve the stability and accuracy of classification and regression algorithms. It reduces variance and helps mitigate overfitting. Although bagging is frequently applied to decision tree methods, it can be used with any type of model. It is a special case of the broader ensemble averaging approach, where multiple models are combined to produce a single prediction.
The technique was introduced by Thomas Dietterich in the 1990s, though the term "bagging" was coined by Michael Jordan in a 1994 paper. Bagging has since become a foundational tool in machine learning, particularly in the development of random forests and other ensemble methods.
Core Idea
The core idea behind bagging is to leverage the power of averaging. Individual models trained on slightly different subsets of the training data tend to have uncorrelated errors. By averaging their predictions, these errors cancel out, leading to a more robust and accurate final model. This is especially beneficial for unstable algorithms, where small changes in the training data can lead to large changes in the learned model.
The Bagging Algorithm
Given a standard training set \( D \) of size \( n \), bagging generates \( m \) new training sets \( D_i \), each of size \( n' \), by sampling from \( D \) uniformly and with replacement. This sampling process is known as bootstrapping. When \( n' = n \), for large \( n \), each \( D_i \) is expected to contain about 63.2% of the unique samples from \( D \), with the rest being duplicates. This fraction arises from the limit \( 1 - 1/e \). Sampling with replacement ensures that each bootstrap sample is independent of the others, as the selection of each sample does not depend on previous selections.
After generating the \( m \) bootstrap samples, \( m \) models are fitted, one on each sample. For regression tasks, the final prediction is the average of the individual model outputs. For classification tasks, the final prediction is determined by voting, typically a majority vote.
Key Terms: Original, Bootstrap, and Out-of-Bag Datasets
In bootstrap aggregating, three types of datasets are relevant: the original dataset, the bootstrap dataset, and the out-of-bag dataset. The original dataset is the given training data. The bootstrap dataset is created by randomly sampling from the original dataset with replacement, and it has the same size as the original. For example, if the original dataset consists of 12 people named Emily, Jessie, George, Constantine, Lexi, Theodore, John, James, Rachel, Anthony, Ellie, and Jamal, a bootstrap sample might include James, Ellie, Constantine, Lexi, John, Constantine, Theodore, Constantine, Anthony, Lexi, Constantine, and Theodore. Here, Constantine appears four times, Lexi twice, and Theodore twice.
The out-of-bag dataset consists of the observations that were not selected in the bootstrap sample. In the example, the out-of-bag set would be Emily, Jessie, George, Rachel, and Jamal. Since sets ignore duplicates, the difference is taken between the original set and the unique elements of the bootstrap set.
Application to Decision Trees and Random Forests
Bagging is often used with decision trees, leading to the creation of random forests. In a random forest, each tree is trained on a bootstrap sample, and additionally, at each split, only a small random subset of features is considered. This introduces further diversity among the trees, making the ensemble more robust.
To build a decision tree from a bootstrap dataset, the algorithm examines each feature and determines how well it separates the samples into positive and negative classes. This is often done using a confusion matrix, which lists true positives, false positives, true negatives, and false negatives. Features are ranked based on metrics such as information gain or a measure of "goodness." The top feature is used to partition the samples into two sets: those that possess the feature and those that do not. This process is repeated recursively for each subset until a stopping criterion, such as maximum depth, is reached. At the leaves, samples are classified as positive or negative based on the majority class.
Random forests, which combine bagging with random feature selection, have been shown to achieve high accuracy and are widely used in practice. The number of trees in the forest affects performance; for instance, a model with 50 trees generally performs better than one with 10 trees, as the chance of an observation being left out of all bootstrap samples decreases with more trees.
Effects on Different Algorithms
Bagging leads to improvements for unstable procedures, which include artificial neural networks, classification and regression trees, and subset selection in linear regression. It has also been shown to improve preimage learning. On the other hand, bagging can mildly degrade the performance of stable methods such as k-nearest neighbors, because averaging over similar models does not reduce variance significantly and may introduce bias.
Theoretical Insights
The effectiveness of bagging is rooted in variance reduction. For a model with high variance, such as a deep decision tree, small perturbations in the training data can lead to very different models. By averaging over multiple models trained on bootstrap samples, the variance of the final prediction is reduced, often without a significant increase in bias. This is particularly important in high-dimensional settings, such as those encountered in Deep learning and Artificial intelligence applications.
Practical Considerations
Bagging is computationally efficient because each model can be trained independently, making it easy to parallelize. This has contributed to its popularity in large-scale machine learning pipelines, including those used by cloud providers like Amazon Web Services and Google Cloud. In practice, the number of bootstrap samples \( m \) is often chosen based on available computational resources, with typical values ranging from 10 to a few hundred.
Relation to Other Ensemble Methods
Bagging is closely related to other ensemble techniques, such as boosting and stacking. While boosting focuses on sequentially training models to correct errors, bagging trains models in parallel and combines them by averaging or voting. This distinction makes bagging particularly suitable for reducing variance, whereas boosting is more effective at reducing bias. Random forests, a specific implementation of bagging with decision trees, are among the most widely used ensemble methods in machine learning.
Conclusion
Bagging remains a fundamental technique in machine learning, offering a simple yet powerful way to improve model stability and accuracy. Its principles have influenced the development of more advanced ensemble methods and continue to be relevant in modern applications, from traditional tabular data to complex domains like neural networks and large language models.