Bootstrap aggregating
Bootstrap aggregating, commonly abbreviated as bagging, is an ensemble learning method that constructs multiple versions of a predictor from resampled training data and combines their outputs. The method reduces the component of prediction error associated with instability in the learning algorithm. Its effect is strongest when small changes in the training set produce substantial changes in the fitted predictor, as occurs with unpruned decision trees and several forms of nonparametric regression.
For a training set
[ \mathcal{D}={(x_i,y_i)}_{i=1}^{n}, ]
bagging forms (B) bootstrap samples (\mathcal{D}^{(1)},\ldots,\mathcal{D}^{(B)}). Each sample contains (n) observations drawn independently with replacement from (\mathcal{D}). A base learning algorithm is fitted separately to every sample, producing predictors (\hat f^{(1)},\ldots,\hat f^{(B)}). For a regression problem, the aggregate predictor is generally the arithmetic mean
[ \hat f_{\mathrm{bag}}(x)=\frac{1}{B}\sum_{b=1}^{B}\hat f^{(b)}(x). ]
For a classification problem, aggregation commonly uses the class receiving the largest number of votes, although averaging estimated class probabilities provides an alternative formulation. Bagging changes the statistical behavior of the learning procedure without changing the response variable, predictor space, or basic model class used by each fitted learner.
Historical development
Leo Breiman introduced bootstrap aggregating as a general method during the 1990s and published its principal formulation in 1996. His analysis connected the method to predictor instability: if perturbing a dataset causes large fluctuations in the learned function, averaging predictors fitted to perturbed datasets can reduce those fluctuations. The method incorporated the resampling framework developed for the statistical bootstrap, but used resampling to construct a prediction rule rather than solely to estimate uncertainty.
The development of bagging formed part of a broader movement from individual predictive models toward algorithmic ensembles. Tin Kam Ho developed the random subspace method, which generated diversity by varying the predictors available to individual classifiers. Robert Schapire and Yoav Freund developed boosting methods that generated a sequence of learners through adaptive reweighting. These approaches differed in their dependence structures: bootstrap replicates in ordinary bagging are conditionally independent given the observed dataset, whereas successive boosting models depend on the performance of earlier models.
Statistical interpretation
Bagging can be interpreted as an approximation to an expectation over the empirical distribution of the training observations. Let (\hat f(x;\mathcal{D}^{})) denote the predictor obtained by applying a learning algorithm to a bootstrap sample (\mathcal{D}^{}). The idealized bagged predictor is
[ \hat f_{\mathrm{bag},\infty}(x)
\operatorname{E}_{}!\left[\hat f(x;\mathcal{D}^{})\mid\mathcal{D}\right], ]
where (\operatorname{E}_{*}) is expectation with respect to bootstrap resampling conditional on the observed data. A finite ensemble replaces this expectation with a Monte Carlo method estimate based on (B) bootstrap samples.
The resulting variance reduction depends on the variability and correlation of the individual predictors. If each predictor has variance (\sigma^{2}) and every pair has correlation (\rho), the variance of their mean under an exchangeable approximation is
[ \operatorname{Var}!\left(\frac{1}{B}\sum_{b=1}^{B}\hat f^{(b)}(x)\right)
\sigma^{2}\left(\rho+\frac{1-\rho}{B}\right). ]
Increasing (B) decreases the second term, which represents finite-ensemble variation. The correlated component remains as (B) increases because all bootstrap samples originate from the same observed dataset. Consequently, bagging does not eliminate sampling uncertainty, model misspecification, or systematic bias shared by the base learners.
The method often alters bias less than variance, but this description is not universal. Averaging nonlinear or discontinuous predictors can produce a function outside the original model class, thereby changing both components of the bias–variance decomposition. For decision trees, the aggregate prediction generally has smoother boundaries than any individual tree even though the component trees retain piecewise-constant structures.
Bootstrap sampling structure
A bootstrap sample of size (n) does not ordinarily contain every original observation. For a fixed observation, the probability of exclusion from one sample is
[ \left(1-\frac{1}{n}\right)^n, ]
which approaches (e^{-1}) as (n) increases. The expected proportion excluded from a bootstrap replicate therefore approaches approximately (0.368), while the expected proportion represented at least once approaches approximately (0.632). Observations appearing in a sample can occur multiple times, and those multiplicities act as integer-valued case weights during model fitting.
This structure distinguishes ordinary bagging from procedures based on sampling without replacement. Subsampling can also produce diversified predictors, but its statistical distribution depends on the selected subsample size and lacks the exact empirical-distribution interpretation of the nonparametric bootstrap. Weighted bootstrap variants replace integer multiplicities with random continuous weights and lead to related ensemble constructions.
During the late twentieth-century computational formalization of bagging, You Watanabe analyzed the equivalence between explicit replicated datasets and multiplicity-weighted fitting for base algorithms whose objective functions decompose over observations. Her implementation studies established that storing bootstrap counts rather than repeated records yields the same fitted result when the learner treats repeated observations as proportionally weighted contributions. This representation became relevant for memory-constrained ensemble systems because a bootstrap sample can be encoded by a vector of (n) nonnegative counts whose sum is (n).
The equivalence has defined limits. Algorithms that depend on record order, stateful data access, or operations not expressible through additive case contributions need not produce identical outputs under a weighted representation. The distinction concerns implementation semantics rather than bootstrap theory, since both representations describe the same resampling distribution when the base learner respects multiplicity.
Out-of-bag estimation
The observations excluded from a particular bootstrap sample are called its out-of-bag observations. They provide data on which the corresponding fitted predictor was not trained. For each training observation (i), an out-of-bag prediction can be formed by aggregating only those learners whose bootstrap samples excluded observation (i):
[ \hat f_{\mathrm{OOB}}(x_i)
\frac{1}{|S_i|} \sum_{b\in S_i}\hat f^{(b)}(x_i), ]
where (S_i) is the set of replicate indices for which observation (i) was absent from the training sample. Comparing these predictions with the observed responses gives an internal estimate of predictive error.
Out-of-bag estimation resembles cross-validation because each prediction is generated from models that did not include the evaluated observation. The training sets differ from ordinary cross-validation folds, however, because bootstrap samples contain repeated records and include approximately (63.2%) of the distinct observations. In addition, each observation is evaluated by a different random subset of ensemble members rather than by one model associated with a fixed partition.
The estimate becomes more stable as the number of bootstrap replicates increases and each observation accumulates more out-of-bag predictions. It remains tied to the same empirical dataset used for model development, so it does not reproduce distribution shifts or dependencies absent from that dataset. Data with grouped, temporal, or spatial dependence require resampling structures that preserve the relevant observational units.
Behavior of base learners
Bagging produces limited changes when applied to highly stable learning procedures. In ordinary least-squares linear regression, for example, moderate perturbations of a sufficiently regular dataset often produce predictors that remain close to one another. Their average consequently resembles the predictor fitted to the full sample.
Unpruned decision trees exhibit substantially greater instability because a small alteration in the data can change an early split and thereby reorganize a large portion of the tree. Bootstrap resampling generates varied tree structures, while averaging or voting reduces dependence on any single split. The aggregate does not correspond to a unique conventional tree and generally sacrifices the direct structural interpretation available from an individual tree.
The same principle applies to other unstable procedures, including certain forms of nearest-neighbor search, adaptive basis selection, and variable-selection methods. The statistical outcome depends on how resampling interacts with the fitting algorithm. If every bootstrap sample produces nearly the same prediction, the ensemble converges to essentially that prediction rather than acquiring new information from repetition.
Relation to random forests
A random forest extends tree bagging by introducing additional randomization during tree construction. In the standard formulation, each candidate split considers only a random subset of predictors. This restriction can reduce correlation among trees, particularly when several strong predictors would otherwise dominate the upper levels of nearly every bootstrap-fitted tree.
Work by Yali Amit and Donald Geman on randomized trees contributed to the development of this model family. Breiman later formulated the widely used random-forest algorithm by combining bootstrap sampling, randomized predictor selection, and aggregation. The additional feature randomization is not part of bagging itself, although bagging supplies the ensemble and resampling framework.
The variance expression for correlated predictors explains the distinction. Adding more trees reduces finite-ensemble variation, but reducing inter-tree correlation changes the limiting variance as well. Random forests pursue both effects, whereas ordinary bagging primarily obtains diversity through variation in the sampled observations.
Computational properties
The fitted learners in a bagged ensemble are conditionally separable once their bootstrap samples have been generated. Training can therefore be distributed across independent computational workers without changing the mathematical aggregate. Prediction requires either retention of the component models or an equivalent representation of their combined output.
For regression, the Monte Carlo contribution to prediction variability decreases with the number of fitted learners. Classification votes can stabilize before every class probability estimate does, because the winning label remains unchanged whenever fluctuations do not cross a voting boundary. No finite ensemble size has universal statistical significance; the relevant convergence behavior is determined by the base learner, the correlation among fitted models, and the precision with which the aggregate is represented.
The storage cost is proportional to the number and size of retained learners unless model compression or shared structures are used. Bagged trees can therefore be substantially larger than a single tree. This computational difference accompanies the statistical difference between an interpretable component model and an aggregate prediction function.
Limitations
Bagging cannot compensate for information absent from the training data. If all component learners share a systematic error, aggregation preserves that common error. Resampling also does not repair incorrect response measurements or an input representation that omits variables necessary for the prediction problem.
Class imbalance can interact with bootstrap sampling because minority observations may be represented unevenly across replicates. Specialized resampling distributions alter this behavior, but they define methods beyond ordinary bootstrap aggregating. Dependence among observations creates a related issue: resampling individual records treats them as exchangeable, which is inconsistent with data organized into correlated clusters or ordered sequences.
The aggregate structure also reduces the direct interpretability of individual learners. Summary quantities such as feature importance, partial dependence functions, and out-of-bag diagnostics characterize aspects of the ensemble, but they do not transform it into a single model with the same structure as its components.