Ensembles: bagging and boosting
Ensemble methods combine many simple models (base learners) to make a stronger predictor; bagging reduces variance by bootstrap aggregation while boosting sequentially reweights data to reduce error and bias (AdaBoost is the main algorithm).
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Ensemble methods are used by engineers to get more accurate and stable predictions than a single model. Bagging (bootstrap aggregating) helps when a model has high variance (like decision trees); boosting (e.g. AdaBoost) helps convert many weak learners into a strong one and can reduce bias and training error.
Key ideas
- Bagging (Bootstrap Aggregating): train the same learning algorithm many times on different bootstrap samples (sample with replacement of the training set) and combine their outputs by majority vote (classification) or average (regression). Bagging reduces the variance of unstable learners.
- Assumption used for analysis: base learners are identically distributed with variance σ^2 and pairwise correlation ρ.
- With M base learners, the variance of the averaged predictor is σ^2((1−ρ)/M + ρ). Derivation: see Formulas and derivation step-by-step below.
- Bootstrap sample: from dataset of size N, draw N items with replacement; some items repeat, about 63.2% of original items appear at least once on average. The remaining ~36.8% left out per bootstrap forms the out-of-bag (OOB) set for that model and can be used to estimate generalization error without a separate validation set.
- Boosting: build learners sequentially. Each learner focuses more on examples misclassified by previous learners by reweighting training examples. The final classifier is a weighted sum of base learners.
- AdaBoost (Discrete AdaBoost): At round t we train a weak learner h_t on weighted training set. Compute weighted error ε_t = sum_{i: h_t(x_i)≠y_i} w_i / sum w_i. Compute weight α_t = 0.5 · ln((1−ε_t)/ε_t). Update example weights: multiply by exp(−α_t · y_i · h_t(x_i)) and renormalize. Final classifier: H(x)=sign(Σ_t α_t h_t(x)).
- AdaBoost minimizes an exponential loss on the training set and increases the margins of correctly classified examples.
- Bias and variance: bagging mainly reduces variance, not bias. Boosting can reduce bias (and variance) because later learners can compensate earlier errors.
Diagrams to draw (exam answers often want these):
- For bagging: draw a box labelled "Training data (N)". Arrows to 3 boxes labelled "Bootstrap sample 1", "Bootstrap sample 2", "Bootstrap sample 3" (each box contains repeated indices, write examples like 1,4,2,2,5). From each bootstrap box, draw arrow to a model tree (label M1, M2, M3). From models, draw arrows to a voting box that outputs final prediction (majority vote). Label that voting as "majority vote".
- For boosting: draw a sequence: Training data + equal weights -> train h1 -> compute errors -> reweight examples (increase weights of misclassified) -> train h2 -> ... -> combine with weights α1, α2, ... -> final sign(Σα_th_t(x)).
Formulas
ε_t = (Σ_{i: h_t(x_i) ≠ y_i} w_i) / (Σ_i w_i) — weighted error of weak learner at round t; w_i dimensionless weights; applies in AdaBoost.
α_t = 0.5 · ln((1 − ε_t)/ε_t) — weight of weak learner h_t; ln is natural logarithm; dimensionless; valid when 0 < ε_t < 1. In practice we also require ε_t < 0.5 so that α_t > 0; if ε_t > 0.5, flip the learner’s predictions to make the error < 0.5 or stop.
w_i ← w_i · exp(−α_t · y_i · h_t(x_i)) then renormalize so Σ_i w_i = 1 — AdaBoost weight update; y_i, h_t(x_i) ∈ {−1,+1}.
H(x) = sign(Σ_t α_t · h_t(x)) — final AdaBoost classifier.
Var(average of M predictors) = σ^2 · ((1 − ρ)/M + ρ) — variance of bagged predictor assuming each predictor has variance σ^2 and pairwise correlation ρ; σ^2 is variance (squared units of prediction), ρ is correlation (dimensionless).
approx. fraction of distinct examples in a bootstrap sample ≈ 1 − e^{−1} ≈ 0.632 — fraction appears at least once for large N; dimensionless.
Notes on symbols: ε_t dimensionless error fraction, α_t dimensionless, w_i dimensionless probability weight. ln is natural log.
Derivation (variance reduction formula, step-by-step):
- Let predictions of M base learners on a fixed input x be random variables Z_1,...,Z_M, each with mean μ and variance Var(Z_i)=σ^2.
- Assume Cov(Z_i,Z_j)=ρ·σ^2 for i≠j (pairwise equal covariance assumption).
- Average prediction Z̄ = (1/M) Σ_i Z_i. Var(Z̄) = (1/M^2) [Σ_i Var(Z_i) + Σ_{i≠j} Cov(Z_i,Z_j)].
- Substitute Var and Cov: Var(Z̄) = (1/M^2)[Mσ^2 + M(M−1)ρσ^2] = σ^2[(1−ρ)/M + ρ].
- Conclusion: as M→∞, Var(Z̄)→ρσ^2; if base learners are independent (ρ=0), Var→0.
Assumptions: identical variances and equal pairwise correlation. Real ensembles may not satisfy these exactly.
Worked examples
Example 1 — Bagging (small classification trace) Training instances 1..5 with true labels y = [+1,+1,−1,+1,−1]. We build 3 bootstrap models. Bootstrap samples (size 5 with replacement):
- Sample 1 indices: [1,2,2,4,5] -> model M1 predictions on all instances: [+1,+1,−1,+1,−1].
- Sample 2 indices: [2,3,3,5,5] -> model M2 predictions: [+1,+1,−1,−1,−1]. (M2 misclassifies instance 4)
- Sample 3 indices: [1,1,3,4,5] -> model M3 predictions: [+1,−1,−1,+1,−1]. (M3 misclassifies instance 2) Majority vote per instance: 1: [+1,+1,+1] -> +1 2: [+1,+1,−1] -> +1 (two +1 votes) 3: [−1,−1,−1] -> −1 4: [+1,−1,+1] -> +1 5: [−1,−1,−1] -> −1 Ensemble prediction equals true labels for all instances → accuracy = 100%. (Shows bagging can correct individual model mistakes by majority vote.)
Example 2 — AdaBoost (tiny numerical trace) Dataset: x1,x2,x3 with labels y = [+1,+1,−1]. Initial weights w_i = 1/3 each. Round 1: choose h1(x)=+1 for all x.
- Weighted error ε1 = weight of misclassified x3 = 1/3.
- α1 = 0.5·ln((1−1/3)/(1/3)) = 0.5·ln(2) = 0.34657359.
- Update weights (before normalization): correct examples multiply by exp(−α1)=0.70710678 -> w1'=w2'=0.23570226; misclassified w3'=1/3·1.41421356=0.47140452. Normalize by sum 0.942809 -> w1=w2=0.25, w3=0.5. Round 2: choose h2 that predicts +1 for x1 and −1 for x2 and x3.
- Weighted error ε2 = weight of misclassified x2 = 0.25.
- α2 = 0.5·ln((1−0.25)/0.25) = 0.5·ln(3) = 0.54930614.
- Update weights (not needed further here) -> final normalized weights are [0.1667, 0.5, 0.3333]. Final classifier H(x)=sign(α1·h1(x)+α2·h2(x)). Compute sums:
- x1: α1·(+1)+α2·(+1)=0.3465736+0.5493061=0.8958797 -> predicts +1 (correct).
- x2: 0.3465736+0.5493061·(−1)=−0.2027325 -> predicts −1 (wrong).
- x3: 0.3465736·(+1)+0.5493061·(−1)=−0.2027325 -> predicts −1 (correct). Final ensemble error = 1/3; weights and α computed above are exact to the digits shown. Final predictions listed; arithmetic checked.
Example 3 — Show effect of bagging on variance (short theoretical) Assume single-tree variance σ^2 = 1 and pairwise correlation ρ = 0.2. For M = 5 trees, Var(ensemble) = 1·((1−0.2)/5 + 0.2) = (0.8/5 + 0.2) = 0.16 + 0.2 = 0.36. So variance reduced from 1 to 0.36.
Common mistakes
- Using α_t formula with ε_t = 0 or 1 (undefined). AdaBoost requires 0 < ε_t < 1; if ε_t = 0 take α_t → ∞ in theory; in practice a perfect classifier can stop or be given large weight carefully.
- Forgetting to renormalize weights after AdaBoost updates.
- Thinking boosting always improves test accuracy; boosting may overfit noisy labels if weak learners become too complex.
- For bagging, wrongly assuming base learners must be different algorithms — they are usually same algorithm with different training samples.
For your exam
Types of questions:
- Definitions: define ensemble, bagging, bootstrap, boosting, weak learner, AdaBoost steps.
- Short notes: compare bagging vs boosting; why bagging reduces variance; what is the role of α_t in AdaBoost.
- Derivations: derive variance reduction formula for bagging under equal-correlation assumption; derive AdaBoost weight update using minimization of exponential loss (optional higher-level).
- Numerical traces: run AdaBoost for 2 rounds on a tiny dataset (show weights, ε_t, α_t, updates); simulate bagging votes on small set.
- Diagrams: draw architecture of bagging and boosting with labels. What full-marks answers include: precise definitions (bold key terms), assumptions stated, step-by-step algebra for formulas, clear diagrams as described, and numeric steps with normalization and final predictions.
Quick check
- What is a bootstrap sample? 2. Write the AdaBoost update for α_t. 3. How does bagging combine classifiers for classification?
Answers: A bootstrap sample is an N-size sample drawn with replacement from the training set (so some examples repeat and about 63.2% of distinct examples appear);
α_t = 0.5 · ln((1−ε_t)/ε_t); bagging combines classifiers by majority vote (classification) or averaging (regression).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?