Intuition The one-line ideaIf you average many noisy but unbiased predictions, the noise cancels while the signal survives. Bagging manufactures "many" predictors from one dataset by resampling it, so we get the averaging benefit even with limited data.
Definition Bootstrap Aggregating (Bagging)Bagging = train the same learning algorithm on many bootstrap resamples of the training set, then aggregate their outputs (average for regression, majority vote for classification).
Bootstrap sample : draw n n n with replacement from a dataset of size n n n Aggregate : combine the B B B
The word literally decomposes: B ootstrap agg regating → Bagging .
Suppose each base model b b b f ^ b ( x ) \hat f_b(x) f ^ b ( x )
E [ f ^ b ( x ) ] = μ , V a r ( f ^ b ( x ) ) = σ 2 . \mathbb{E}[\hat f_b(x)] = \mu, \qquad \mathrm{Var}(\hat f_b(x)) = \sigma^2. E [ f ^ b ( x )] = μ , Var ( f ^ b ( x )) = σ 2 .
The bagged predictor is the average:
f ˉ ( x ) = 1 B ∑ b = 1 B f ^ b ( x ) . \bar f(x) = \frac{1}{B}\sum_{b=1}^{B}\hat f_b(x). f ˉ ( x ) = B 1 ∑ b = 1 B f ^ b ( x ) .
Step 1 — the mean is unchanged. Why? Expectation is linear:
E [ f ˉ ( x ) ] = 1 B ∑ b E [ f ^ b ( x ) ] = 1 B ⋅ B μ = μ . \mathbb{E}[\bar f(x)] = \frac{1}{B}\sum_b \mathbb{E}[\hat f_b(x)] = \frac{1}{B}\cdot B\mu = \mu. E [ f ˉ ( x )] = B 1 ∑ b E [ f ^ b ( x )] = B 1 ⋅ B μ = μ . not change bias. (This is crucial: it can only touch variance.)
Step 2 — the variance shrinks. Assume each model has variance σ 2 \sigma^2 σ 2 ρ \rho ρ V a r ( ∑ a i X i ) = ∑ i a i 2 V a r ( X i ) + ∑ i ≠ j a i a j C o v ( X i , X j ) \mathrm{Var}\big(\sum a_i X_i\big)=\sum_i a_i^2\mathrm{Var}(X_i)+\sum_{i\ne j}a_ia_j\mathrm{Cov}(X_i,X_j) Var ( ∑ a i X i ) = ∑ i a i 2 Var ( X i ) + ∑ i = j a i a j Cov ( X i , X j ) a i = 1 / B a_i=1/B a i = 1/ B
V a r ( f ˉ ) = 1 B 2 [ B σ 2 ⏟ diagonal + B ( B − 1 ) ρ σ 2 ⏟ off-diagonal ] . \mathrm{Var}(\bar f) = \frac{1}{B^2}\Big[\underbrace{B\sigma^2}_{\text{diagonal}} + \underbrace{B(B-1)\rho\sigma^2}_{\text{off-diagonal}}\Big]. Var ( f ˉ ) = B 2 1 [ diagonal B σ 2 + off-diagonal B ( B − 1 ) ρ σ 2 ] .
Step 3 — simplify.
V a r ( f ˉ ) = ρ σ 2 + 1 − ρ B σ 2 \boxed{\;\mathrm{Var}(\bar f) = \rho\sigma^2 + \frac{1-\rho}{B}\sigma^2\;} Var ( f ˉ ) = ρ σ 2 + B 1 − ρ σ 2
Intuition Reading the formula (the 80/20)Two knobs: more trees (B ↑ B\uparrow B ↑ 1 − ρ B \frac{1-\rho}{B} B 1 − ρ ρ σ 2 \rho\sigma^2 ρ σ 2 more diversity (ρ ↓ \rho\downarrow ρ ↓
Definition Bagging algorithmGiven training set D = { ( x i , y i ) } i = 1 n D=\{(x_i,y_i)\}_{i=1}^n D = {( x i , y i ) } i = 1 n B B B
For b = 1 , … , B b=1,\dots,B b = 1 , … , B D b D_b D b n n n D D D with replacement .
Train base model f ^ b \hat f_b f ^ b D b D_b D b
Predict :
Regression: f ˉ ( x ) = 1 B ∑ b f ^ b ( x ) \bar f(x)=\frac1B\sum_b \hat f_b(x) f ˉ ( x ) = B 1 ∑ b f ^ b ( x )
Classification: y ^ ( x ) = mode { f ^ b ( x ) } \hat y(x)=\text{mode}\{\hat f_b(x)\} y ^ ( x ) = mode { f ^ b ( x )}
Each bootstrap sample has size n n n with replacement , so some points appear multiple times and some are missing.
How many points are left out? The probability a specific point is not chosen in one draw is 1 − 1 n 1-\frac1n 1 − n 1 n n n
P ( point i absent ) = ( 1 − 1 n ) n → n → ∞ e − 1 ≈ 0.368. P(\text{point } i \text{ absent}) = \left(1-\frac1n\right)^n \xrightarrow{n\to\infty} e^{-1}\approx 0.368. P ( point i absent ) = ( 1 − n 1 ) n n → ∞ e − 1 ≈ 0.368.
Intuition Free validation set — OOB errorSince each point is OOB for ~37% of the trees, we can predict it using only the trees that never trained on it. Averaging these gives an honest test-like error estimate without a held-out set . That's why bagging gives cross-validation "for free."
Worked example 1. Variance drop with independent models (ρ = 0 \rho=0 ρ = 0 σ 2 = 4 \sigma^2 = 4 σ 2 = 4 B = 10 B=10 B = 10 independent models.
V a r ( f ˉ ) = 0 ⋅ 4 + 1 − 0 10 ⋅ 4 = 0.4. \mathrm{Var}(\bar f)=0\cdot 4 + \frac{1-0}{10}\cdot 4 = 0.4. Var ( f ˉ ) = 0 ⋅ 4 + 10 1 − 0 ⋅ 4 = 0.4. Why this step? With ρ = 0 \rho=0 ρ = 0 1 / B 1/B 1/ B 4 → 0.4 4\to0.4 4 → 0.4
Worked example 2. Correlated models (ρ = 0.5 \rho=0.5 ρ = 0.5 σ 2 = 4 \sigma^2=4 σ 2 = 4 ρ = 0.5 \rho=0.5 ρ = 0.5 B = 10 B=10 B = 10 V a r = 0.5 ⋅ 4 + 1 − 0.5 10 ⋅ 4 = 2 + 0.2 = 2.2. \mathrm{Var}=0.5\cdot4 + \frac{1-0.5}{10}\cdot4 = 2 + 0.2 = 2.2. Var = 0.5 ⋅ 4 + 10 1 − 0.5 ⋅ 4 = 2 + 0.2 = 2.2. Why this step? The floor ρ σ 2 = 2 \rho\sigma^2 = 2 ρ σ 2 = 2 B = ∞ B=\infty B = ∞ 2 2 2 correlation caps the benefit → motivates Random Forests.
Worked example 3. Majority vote (classification)5 independent classifiers each correct with p = 0.7 p=0.7 p = 0.7 ≥ 3 \ge 3 ≥ 3 P = ∑ k = 3 5 ( 5 k ) 0.7 k 0.3 5 − k P = \sum_{k=3}^{5}\binom{5}{k}0.7^k0.3^{5-k} P = ∑ k = 3 5 ( k 5 ) 0. 7 k 0. 3 5 − k = ( 5 3 ) ( .343 ) ( .09 ) + ( 5 4 ) ( .2401 ) ( .3 ) + ( 5 5 ) ( .16807 ) =\binom53(.343)(.09)+\binom54(.2401)(.3)+\binom55(.16807) = ( 3 5 ) ( .343 ) ( .09 ) + ( 4 5 ) ( .2401 ) ( .3 ) + ( 5 5 ) ( .16807 ) = 0.3087 + 0.36015 + 0.16807 ≈ 0.837. =0.3087+0.36015+0.16807 \approx 0.837. = 0.3087 + 0.36015 + 0.16807 ≈ 0.837. Why this step? Each vote is a Bernoulli trial; the ensemble is a binomial majority . Accuracy jumped 0.70 → 0.84 0.70\to0.84 0.70 → 0.84 only because votes were independent. Correlated errors would erase this gain.
Common mistake "Bagging reduces bias too."Why it feels right: ensembles perform better overall, so surely everything improves. The truth: Step 1 of the derivation showed E [ f ˉ ] = μ \mathbb{E}[\bar f]=\mu E [ f ˉ ] = μ variance . Fix: bag low-bias, high-variance learners (deep unpruned trees). Bagging a high-bias model (e.g. a shallow stump) gives you a slightly-less-noisy still-biased model — useless.
Common mistake "Bag stable models like linear regression to boost them."Why it feels right: more models = better, right? The truth: stable learners barely change across resamples, so f ^ b \hat f_b f ^ b ρ ≈ 1 \rho\approx1 ρ ≈ 1 ρ σ 2 ≈ σ 2 \rho\sigma^2\approx\sigma^2 ρ σ 2 ≈ σ 2 Fix: bag unstable learners (decision trees, neural nets), whose predictions swing with the data.
Common mistake "A bootstrap sample uses all n unique points."Why it feels right: it has size n n n The truth: with replacement means duplicates; ~37% of unique points are missing (the OOB set). Fix: remember e − 1 ≈ 0.37 e^{-1}\approx0.37 e − 1 ≈ 0.37
Common mistake "More trees can overfit."Why it feels right: in boosting, more rounds can overfit. The truth: in bagging, increasing B B B B → ∞ B\to\infty B → ∞ B B B Fix: pick B B B
Recall Feynman: explain to a 12-year-oldImagine one weather-guesser who's often wrong in random ways — sometimes too high, sometimes too low. Now ask many friends the same question, but give each friend a slightly shuffled copy of yesterday's weather facts. Each friend still guesses randomly-wrongly, but when you average all their guesses, the too-highs and too-lows cancel out and you land near the truth. The trick: shuffle the facts by picking cards from a deck and putting each card back before the next pick — so every friend gets a different deck. Some cards never get picked (about a third) — you use those to secretly grade each friend for free.
"BAG = Bootstrap, Average, Guessers-that-wobble."
And the magic number: "Bootstrap forgets a third" → e − 1 ≈ 37 % e^{-1}\approx 37\% e − 1 ≈ 37%
What does "bagging" stand for? Bootstrap AGGregating — train on bootstrap resamples, then aggregate.
A bootstrap sample of size n is drawn how? n points sampled with replacement from the n-point dataset.
Does bagging reduce bias or variance? Variance only; bias is unchanged because
E [ f ˉ ] = μ \mathbb{E}[\bar f]=\mu E [ f ˉ ] = μ .
Variance formula for a bagged ensemble? V a r ( f ˉ ) = ρ σ 2 + 1 − ρ B σ 2 \mathrm{Var}(\bar f)=\rho\sigma^2+\frac{1-\rho}{B}\sigma^2 Var ( f ˉ ) = ρ σ 2 + B 1 − ρ σ 2 .
As B→∞ the ensemble variance approaches what? ρ σ 2 \rho\sigma^2 ρ σ 2 — the floor set by inter-model correlation.
What fraction of data is out-of-bag per model, and why? ~37%, since
( 1 − 1 / n ) n → e − 1 (1-1/n)^n\to e^{-1} ( 1 − 1/ n ) n → e − 1 .
What is OOB error and why is it useful? Predict each point using only trees that didn't train on it — free validation without a held-out set.
Why bag unstable learners like deep trees? They change a lot across resamples → low correlation ρ → bigger variance reduction.
What single quantity must you lower to beat the ρ σ 2 \rho\sigma^2 ρ σ 2 The pairwise correlation ρ (motivates Random Forests).
Can increasing B (number of trees) cause overfitting? No — larger B just converges to the averaging limit; it never overfits by itself.
Decision Trees — the canonical high-variance base learner bagging fixes.Random Forests — bagging plus feature subsampling to reduce ρ \rho ρ Bias-Variance Tradeoff — bagging attacks the variance term.Bootstrap (statistics) — the resampling engine behind bagging.Boosting — contrast: reduces bias sequentially, can overfit.Out-of-Bag Error — the free validation estimate.Ensemble Methods — the umbrella family.
rho sigma2 plus 1 minus rho over B times sigma2
Kills 1 minus rho over B term
Intuition Hinglish mein samjhoBagging ka core idea bahut simple hai: agar tumhare paas ek model hai jo sahi average deta hai par bahut wobble karta hai (high variance), to us jaisa model bahut baar train karo aur sab ke predictions ka average le lo. Averaging se random errors cancel ho jaate hain, aur signal bacha rehta hai. Problem yeh hai ki data to ek hi hai — to hum bootstrap karte hain: same dataset se n points replacement ke saath uthate hain, taaki har baar thoda alag dataset mile. Isse har tree thoda alag banta hai.
Maths se do cheezein clear hoti hain. Pehli: E [ f ˉ ] = μ \mathbb{E}[\bar f]=\mu E [ f ˉ ] = μ bias nahi badalta — sirf variance kam karta hai. Isliye bagging deep, unstable trees pe lagao (jo low-bias high-variance hote hain), stable models jaise linear regression pe nahi. Doosri: variance ρ σ 2 + 1 − ρ B σ 2 \rho\sigma^2 + \frac{1-\rho}{B}\sigma^2 ρ σ 2 + B 1 − ρ σ 2 B B B floor ρ σ 2 \rho\sigma^2 ρ σ 2 ρ \rho ρ Random Forest ka idea aata hai (feature randomness daal ke ρ \rho ρ
Ek bonus: kyunki har bootstrap sample me lagbhag 37% points chhoot jaate hain (( 1 − 1 / n ) n → e − 1 (1-1/n)^n \to e^{-1} ( 1 − 1/ n ) n → e − 1 nahi hota, bas averaging limit tak pahunchte ho. Boosting se ulta — wahan zyada rounds overfit kar sakte hain.
