Bootstrap aggregating, commonly known as bagging, is an ensemble learning method in machine learning designed to improve the accuracy and robustness of predictive models. It works by generating multiple bootstrap samples (random subsets with replacement) from the original training dataset, training a separate base model on each sample, and then aggregating their predictions. For regression tasks, the final prediction is typically the average of all base model outputs; for classification, it is the majority vote. Bagging primarily reduces variance, helping to mitigate overfitting, and is particularly effective for high-variance algorithms like decision trees.
The technique was introduced by Leo Breiman in 1994 in his paper "Bagging Predictors." It is a foundational concept in ensemble learning, distinct from boosting (which sequentially corrects errors) and stacking (which combines diverse models via a meta-learner). Bagging is widely used in practice, most notably as the core of random forests, where it is combined with feature subsampling. Its simplicity and effectiveness have made it a standard tool in both academic research and industrial applications, from finance to healthcare.
Historical Development
Bagging emerged from the broader statistical and machine learning research of the early 1990s, a period marked by growing interest in combining multiple models to improve generalization. Leo Breiman, a statistician at the University of California, Berkeley, formalized the approach in 1994, building on earlier work on bootstrap methods by Bradley Efron. Breiman demonstrated both theoretically and empirically that averaging predictions from models trained on perturbed datasets could reduce error, especially for unstable learners whose outputs change significantly with small data variations.
The method gained rapid traction after the introduction of random forests by Breiman in 2001, which extended bagging by also randomly selecting a subset of features for each split in decision trees. This innovation further decorrelated the base models, leading to substantial performance gains. Since then, bagging has been integrated into numerous software libraries, including scikit-learn, R's randomForest package, and TensorFlow Decision Forests, making it accessible to practitioners worldwide.
Algorithmic Details
The bagging algorithm proceeds in a straightforward manner. Given a training set of size n, the process generates B bootstrap samples, each of size n, drawn uniformly with replacement. This means some original instances may appear multiple times in a sample, while others are omitted (approximately 63.2% of unique instances appear in any given sample, with the rest being duplicates). For each sample, a base model is trained independently, often using the same algorithm and hyperparameters. The base models can be decision trees, neural networks, or other learners.
Aggregation depends on the task. For regression, the predictions are averaged: \( \hat{f}(x) = \frac{1}{B} \sum_{b=1}^{B} \hat{f}_b(x) \). For classification, the final class is determined by majority voting among the base models. The number of bootstrap samples B is a key hyperparameter; typical values range from 50 to 500, with diminishing returns beyond a few hundred. Bagging does not require cross-validation for the base models, as out-of-bag samples (the instances not included in a given bootstrap sample) can be used to estimate generalization error without a separate validation set.
Theoretical Foundations
The effectiveness of bagging stems from variance reduction. For a base model with prediction variance \( \sigma^2 \) and pairwise correlation \( \rho \) among models, the variance of the ensemble average is approximately \( \rho \sigma^2 + (1-\rho)\sigma^2/B \). As B increases, the second term vanishes, leaving \( \rho \sigma^2 \). Thus, bagging works best when base models are unstable (high variance) but not too correlated. Decision trees are ideal because small data perturbations lead to different splits, yet the overall structure remains similar enough to keep correlation moderate.
Breiman's original analysis showed that bagging can reduce mean squared error for regression and misclassification rate for classification, provided the base learner is unstable. It does not significantly help stable learners like linear regression, where variance is already low. The method also provides a natural mechanism for uncertainty estimation through the spread of base model predictions, which can be used to construct prediction intervals.
Practical Applications
Bagging is applied across diverse domains. In finance, it is used for credit scoring and fraud detection, where reducing false positives is critical. In healthcare, bagged decision trees help predict patient outcomes and diagnose diseases from electronic health records. In remote sensing, random forests (a bagging variant) classify land cover from satellite imagery. The method is also common in natural language processing for text classification, though deep learning models often rely on other regularization techniques.
One notable application is in ensemble methods for Machine learning competitions, where bagging is frequently combined with boosting or used as a final step to stabilize predictions. For example, in the Netflix Prize and Kaggle competitions, participants often bag their best models to squeeze out small accuracy gains. In industry, companies like Amazon Web Services and Google Cloud offer managed services that include bagging implementations, enabling scalable model training without manual orchestration.
Limitations and Extensions
Bagging has several limitations. It does not reduce bias; if the base model is systematically underfitting, bagging will not correct that. It also increases computational cost linearly with the number of base models, though training can be parallelized easily since each model is independent. Memory usage can be high when storing many models. Furthermore, bagging is less effective for very large datasets where a single model already generalizes well, or for stable algorithms like linear support vector machines.
Extensions address some of these issues. Random forests add feature subsampling to further decorrelate trees. Pasting (or subbagging) trains on smaller random samples without replacement, reducing computational load. Bragging (bootstrap aggregating with gradient boosting) combines bagging with boosting for improved accuracy. For neural networks, a related technique called deep ensembles trains multiple networks with different random initializations, effectively applying bagging at the weight level. These variants highlight the enduring influence of Breiman's original idea on modern ensemble learning.