Bagging stands for Bootstrap AGGregatING. It was proposed by Leo Breiman in 1996 as an ensemble method designed to reduce the variance of high-variance, low-bias models — most notably unpruned decision trees.
The key insight is simple: averaging many noisy but approximately unbiased estimates reduces noise. If each estimate has variance \(\sigma^2\), the average of \(B\) independent estimates has variance \(\sigma^2 / B\).
Imagine we had access to \(B\) independent training sets drawn from the same population. We could train a model on each and average their predictions:
\[ \hat{f}_{\text{avg}}(x) = \frac{1}{B} \sum_{b=1}^{B} \hat{f}_b(x) \]
The variance of this average would be:
\[ \text{Var}\left(\hat{f}_{\text{avg}}\right) = \frac{\sigma^2}{B} \]
Problem: in practice we only have one training set.
Solution: use the bootstrap to simulate multiple training sets! We sample with replacement from our single dataset to create \(B\) pseudo-independent training sets.
The bagging procedure consists of three steps:
For \(b = 1, 2, \ldots, B\): draw a sample of size \(n\) with replacement from the original training data \(\mathcal{D} = \{(x_1, y_1), \ldots, (x_n, y_n)\}\). Each bootstrap sample \(\mathcal{D}^{*b}\) has the same size as the original but contains duplicates.
Train a base learner \(\hat{f}_b\) (typically an unpruned decision tree — high variance, low bias) on each bootstrap sample \(\mathcal{D}^{*b}\).
Regression:
\[ \hat{f}_{\text{bag}}(x) = \frac{1}{B} \sum_{b=1}^{B} \hat{f}_b(x) \]
Classification: majority vote or average of class probabilities:
\[ \hat{C}_{\text{bag}}(x) = \arg\max_k \sum_{b=1}^{B} \mathbb{1}\left(\hat{C}_b(x) = k\right) \]
or equivalently, using probability averaging:
\[ \hat{p}_k(x) = \frac{1}{B} \sum_{b=1}^{B} \hat{p}_{b,k}(x) \]
The explanation lies in the bias-variance decomposition. For a single model:
\[ \text{MSE} = \text{Bias}^2 + \text{Variance} \]
Bagging does NOT reduce bias — each bootstrapped tree has approximately the same expected prediction as a tree trained on the full dataset. However, it does reduce variance through averaging.
More formally, if we have \(B\) trees each with variance \(\sigma^2\) and pairwise correlation \(\rho\), the variance of the bagged ensemble is:
\[ \text{Var}(\hat{f}_{\text{bag}}) = \rho \sigma^2 + \frac{1 - \rho}{B} \sigma^2 \]
As \(B \to \infty\), the second term vanishes, leaving \(\rho \sigma^2\). The variance reduction is bounded by the correlation between the individual trees. The less correlated the trees, the greater the benefit of bagging.
Each bootstrap sample of size \(n\) drawn with replacement leaves out a fraction of the original observations. The probability that observation \(i\) is not selected in any single draw is:
\[ P(\text{not selected}) = \left(1 - \frac{1}{n}\right)^n \xrightarrow{n \to \infty} e^{-1} \approx 0.368 \]
So each bootstrap sample contains approximately 63.2% of the unique observations, leaving ~36.8% "out of bag".
The OOB prediction for observation \(i\) is the aggregate prediction from all trees for which \(i\) was not in the training set:
\[ \hat{f}_{\text{OOB}}(x_i) = \frac{1}{|S_i|} \sum_{b \in S_i} \hat{f}_b(x_i) \]
where \(S_i = \{b : (x_i, y_i) \notin \mathcal{D}^{*b}\}\).
This provides an essentially free cross-validation estimate of the generalization error — no need for a separate validation set or expensive k-fold CV.
Rule of thumb: the more unstable the base learner, the more bagging helps. If the base learner barely changes when you perturb the training data, bagging will have little effect.
Standard bagging uses all \(p\) features at each split. If one feature is very strong, most trees will use it at the top split, making the trees highly correlated. Recall from above:
\[ \text{Var}(\hat{f}_{\text{bag}}) = \rho \sigma^2 + \frac{1 - \rho}{B} \sigma^2 \]
High correlation \(\rho\) limits the variance reduction achievable by bagging.
Random Forest addresses this by adding random feature subsampling: at each split, only a random subset of \(m \leq p\) features is considered (typically \(m = \sqrt{p}\) for classification, \(m = p/3\) for regression). This decorrelates the trees, reducing \(\rho\) and achieving further variance reduction beyond what plain bagging can offer.