Exercises — Bagging and bootstrap aggregating

Bagging = Bootstrap Aggregating.

• Bootstrap — build many training sets by ==sampling $n$ points with replacement== from the original $n$-point dataset. This manufactures diversity from one dataset.
• Aggregating — combine the $B$ trained models into one output: average for regression, majority vote for classification.

Variance only. From Step 1 of the parent derivation, expectation is linear, so $\mathbb{E}[\bar{f}(x)]=\frac{1}{B}{\sum }_b\mathbb{E}[{\hat{f}}_b(x)]=\frac{1}{B}\cdot B\mu =\mu .$ The ensemble mean equals a single model's mean $\mu$, so bias is untouched. All the benefit lives in the variance term.

• $\frac{1-\rho }{B}{\sigma }^2$ — the $B$-dependent term; it $\to 0$ as $B\to \infty$ (adding trees).
• $\rho {\sigma }^2$ — the floor; it has no $B$ in it, so more trees can never remove it. To lower the floor you must lower $\rho$.

Plug in $\rho =0$: $\mathrm{Var}(\bar{f})=0\cdot 9+\frac{1-0}{9}\cdot 9=0+1=\boxed{1}.$ The variance dropped by a factor of exactly $B=9$ ($9\to 1$). This is the best case — no correlation floor to stop it.

$\mathrm{Var}(\bar{f})=0.4\cdot 9+\frac{1-0.4}{9}\cdot 9=3.6+0.6=\boxed{4.2}.$ The floor is $\rho {\sigma }^2=0.4\cdot 9=3.6$. Even with infinite trees you stop at $3.6$, not $0$. Correlation caps the win.

$P(\text{absent})={\left(1-\frac{1}{5}\right)}^5=(0.8{)}^5=\mathrm{0.32768.}$ The limiting value is $e^{-1}\approx 0.3679$. Even at the tiny size $n=5$ we are already close to $37\%$; the convergence is fast.

Ensemble is correct if $2$ or $3$ are right — a binomial with $n=3$, $p=0.8$: $P=\left(\genfrac{}{}{0ex}{}{3}{2}\right)(0.8{)}^2(0.2{)}^1+\left(\genfrac{}{}{0ex}{}{3}{3}\right)(0.8{)}^3=3(0.64)(0.2)+0.512=0.384+0.512=\boxed{0.896}.$ Accuracy rose $0.80\to 0.896$ — the classic majority-vote lift, valid only because the votes were independent.

Floor $=\rho {\sigma }^2=0.5\cdot 4=2$. We need $\frac{1-\rho }{B}{\sigma }^2\le 0.10\cdot 2=\mathrm{0.2.}$ Left side $=\frac{0.5}{B}\cdot 4=\frac{2}{B}$. So $\frac{2}{B}\le 0.2\Rightarrow B\ge 10.$ Minimum $B=10$. Notice the requirement depends only on $\rho$ and the tolerance, not on ${\sigma }^2$ (it cancels).

$\mathrm{Var}=2+\frac{2}{B}$ (from the term $\frac{1-\rho }{B}{\sigma }^2=\frac{0.5}{B}\cdot 4=\frac{2}{B}$).

Look at the curve: the drop from $B=1\to 5$ is huge ($4\to 2.4$), from $5\to 20$ modest, and past $20$ almost flat. Message: returns diminish fast — pick $B$ where the curve flattens (where OOB error plateaus), not arbitrarily large.

If the three votes are identical, the majority is whatever the single classifier said. The ensemble accuracy collapses back to $p=\boxed{0.80}$ — no gain at all. Lesson: the entire majority-vote benefit came from independence (diversity). Correlation $\rho \to 1$ makes the ensemble a copy of one model — exactly the $\rho {\sigma }^2\to {\sigma }^2$ floor in the variance formula. This is the analysis-level twin of L2.4.

Team A: $\mathrm{Var}=0.6\cdot 1+\frac{1-0.6}{1000}\cdot 1=0.6+0.0004=\mathrm{0.6004.}$ Team B: $\mathrm{Var}=0.2\cdot 1+\frac{1-0.2}{50}\cdot 1=0.2+0.016=\mathrm{0.216.}$ Team B wins by $0.6004-0.216=0.3844$ — nearly 3× lower variance with $20\times$ fewer trees. Synthesis: lowering the floor $\rho {\sigma }^2$ dominates piling on trees. This is precisely why Random Forests add feature subsampling on top of bagging — to attack $\rho$, not $B$.

A given point is OOB for a fraction $\approx e^{-1}=0.368$ of trees. So $\text{OOB trees for }{x}_i\approx 0.368\times 100\approx \boxed{37\text{ trees}}.$ Because those $\approx 37$ trees never trained on $x_i$, their prediction on it is like a test prediction. Averaging them and repeating for every point gives the Out-of-Bag Error — a validation estimate that needs no held-out set. See also Bootstrap (statistics).

$\mathrm{Var}(\bar{f})=0.97\cdot 2+\frac{1-0.97}{200}\cdot 2=1.94+0.0003=\mathrm{1.9403.}$ Best case ($B\to \infty$) $=\rho {\sigma }^2=0.97\cdot 2=1.94$. A single model had ${\sigma }^2=2$, so bagging cut variance from $2$ to only $1.94$ — a 3 % reduction for $200\times$ the compute. Comment: stable learners barely change across resamples ($\rho \approx 1$), so bagging is nearly useless here. This is the quantitative form of the parent's "don't bag stable models" mistake.

The single-model variance is ${\sigma }^2$ (set $B=1$: $\rho {\sigma }^2+(1-\rho ){\sigma }^2={\sigma }^2$ ✓). The floor is $\rho {\sigma }^2$. Halfway between them is $V_{\text{half}}=\frac{{\sigma }^2+\rho {\sigma }^2}{2}=\frac{(1+\rho )}{2}{\sigma }^2.$ Set the ensemble equal to this and solve for $B$: $\rho {\sigma }^2+\frac{1-\rho }{B}{\sigma }^2=\frac{1+\rho }{2}{\sigma }^2.$ Divide by ${\sigma }^2$ and subtract $\rho$: $\frac{1-\rho }{B}=\frac{1+\rho }{2}-\rho =\frac{1-\rho }{2}.$ Therefore $\frac{1}{B}=\frac{1}{2}$, i.e. $\boxed{B=2}$. Insight: independent of $\rho$, the very first extra tree ($B=1\to 2$) already carries you halfway from a single model to the floor. Bagging's biggest single gain is the second tree; everything after is cleanup.

Ensemble correct $⟺$ at least $m+1$ of the $2m+1$ are correct: $P_{\text{ens}}={\sum }_{k=m+1}^{2m+1}\left(\genfrac{}{}{0ex}{}{2m+1}{k}\right)p^k(1-p{)}^{2m+1-k}.$ For $2m+1=5$ ($m=2$), $p=0.7$, need $k\ge 3$: $P=\left(\genfrac{}{}{0ex}{}{5}{3}\right)(0.7{)}^3(0.3{)}^2+\left(\genfrac{}{}{0ex}{}{5}{4}\right)(0.7{)}^4(0.3{)}^1+\left(\genfrac{}{}{0ex}{}{5}{5}\right)(0.7{)}^5$ $=10(0.343)(0.09)+5(0.2401)(0.3)+(0.16807)$ $=0.3087+0.36015+0.16807=\boxed{0.83692}.$ This matches the parent's $\approx 0.837$. As $2m+1\to \infty$ with $p>0.5$, the sum $\to 1$ (Condorcet's Jury Theorem) — but again only for independent votes.

As $B\to \infty$ the correlated ensemble reaches variance $\rho {\sigma }^2$. An independent ensemble of $B_{\text{eff}}$ models has variance $\frac{{\sigma }^2}{B_{\text{eff}}}$ (set $\rho =0$ in the formula). Match them: $\rho {\sigma }^2=\frac{{\sigma }^2}{B_{\text{eff}}}⟹\boxed{B_{\text{eff}}=\frac{1}{\rho }}.$ For $\rho =0.25$: $B_{\text{eff}}=4$. So an infinite forest with pairwise correlation $0.25$ behaves like just 4 independent trees. Correlation is a hard ceiling on how much diversity you actually own — the deep reason Random Forests fight to lower $\rho$.

• L2.1 $\to 1$; L2.2 $\to 4.2$ (floor $3.6$); L2.3 $\to 0.32768$; L2.4 $\to 0.896$.
• L3.1 $\to B\ge 10$; L3.2 table $4,2.4,2.1,2$; L3.3 $\to 0.80$.
• L4.1 Team B $0.216$ vs A $0.6004$; L4.2 $\approx 37$ trees; L4.3 $1.9403$ (floor $1.94$).
• L5.1 $B=2$; L5.2 $0.83692$; L5.3 $B_{\text{eff}}=1/\rho$, $=4$ at $\rho =0.25$.