Skip to main content

Bagging (Bootstrap Aggregation)

Source: Unit 3 §2

The idea​

Problem: splitting the data into disjoint subsets gives each learner too few instances, which brings back overfitting and high variance - the very thing the ensemble was supposed to fix.

Solution - bagging: randomly sample with replacement from the dataset to create new datasets of the same size as the original.

Exam cueWhat the name unpacks to

Bagging = Bootstrap AGGregation. Sample with replacement, train a model on each sample, then aggregate the models' predictions.

Originaldatan rowssubset 1also n rowsmodel 1subset 2also n rowsmodel 2subset 3also n rowsmodel 3sample WITHreplacementcombinevote / average= predictionthe three branches never talk to each other: PARALLEL and INDEPENDENT
One dataset fans out into same-size bootstrap samples. The models never see each other, which is why they can be trained in parallel.

The 63% / 37% rule​

For a sufficiently large sample drawn with replacement, each bootstrap set contains about 63% (roughly two thirds) of the original unique data; about 37% (roughly one third) is left out.

P(a specific point is NOT selected)=(1−1n)n  ⟶  1e≈0.368as n→∞P(\text{a specific point is NOT selected}) = \left(1 - \frac{1}{n}\right)^{n} \;\longrightarrow\; \frac{1}{e} \approx 0.368 \quad \text{as } n \to \infty
≈ 63% in-bagunique rows this model trained on≈ 37% out-of-bagnever seen: test the model hereone bootstrap sample, viewed as a share of the original rows(1 − 1/n)ⁿ → 1/e ≈ 0.368
Sampling n rows with replacement from n rows misses about a third of them. Those rows are free validation data.

Out-of-bag (OOB) error​

FactsFree validation, no holdout required
  • The roughly one third left out of each subset is that learner's out-of-bag (OOB) examples.
  • Measure a learner's error only on the samples it did NOT train on, then average across learners.
  • Accumulate the OOB error over all data points to get an average error estimate.
  • This is close to leave-one-out cross-validation, and it needs no separate validation set.

How many learners?​

NumbersThe practical settings
  • Research shows that around 100 learners are usually enough.
  • The output can be formulated as class probabilities rather than a hard vote.
Best practiceReach for bagging when the base model is unstable

Bagging attacks variance, so it pays off most on low-bias, high-variance base learners - unpruned decision trees being the canonical case. On a high-bias model such as a decision stump there is little variance to average away, and bagging buys almost nothing.

0%0 of 70 pages studied