Foundations — Bagging and bootstrap aggregating

Before you can read the parent note comfortably, you need to earn every symbol it throws at you. This page starts from a smart 12-year-old with zero notation and builds each piece, one on top of the last. Nothing here contradicts the parent — it is the scaffolding underneath it.

Prerequisite vault stops on the way: Bootstrap (statistics), Decision Trees, Bias-Variance Tradeoff, and the destination is the parent Bagging topic (and later Random Forests, Ensemble Methods).

0. What is a "prediction" and why call it a random thing?

Imagine you want to guess a house's price from its size. A model is a rule that eats an input and spits out a number. We write the input as $x$ (the house's size) and the model's guess as $\hat{f}(x)$ — read aloud: "f-hat of x".

Why does the parent treat $\hat{f}(x)$ as random? Because if you had collected a slightly different dataset (a different sample of houses), you'd have fit a slightly different rule and gotten a slightly different guess for the very same house. The guess wobbles depending on which data you happened to see. A number that changes with luck-of-the-draw is exactly what we mean by a random variable.

Look at the red dot in the figure: same house $x$, but three different datasets gave three different predictions. That spread is the randomness we're about to name and measure.

1. The dataset $D$ and its size $n$ — where the randomness lives

Why does the topic need $n$? Because the whole magic number of bagging — that $\approx 37\%$ of points get left out — is really a statement about how big your dataset is, in the limit of large $n$.

2. Sampling "with replacement" — the heart of bootstrap

Here is the one physical action bagging is built on.

In the figure, card $3$ was drawn twice (duplicate) and card $2$ was never drawn (a gap — this becomes an out-of-bag point). This single "replace the card" step is what the bootstrap means, and it's why some points go missing.

3. Building many models: the count $B$ and the average

Bagging fits many models, one per resample. We need a name for "how many."

Now that $B$ and $\sum$ are defined, we can safely use them below.

4. The centre and spread of one model: $\mu (x)$ and ${\sigma }^2(x)$

Every prediction ${\hat{f}}_b(x)$ is a random variable (it depends on the lucky draw $D_b$). Two numbers summarise its cloud — and both are for a fixed input $x$, so we keep the $x$ visible.

The figure shows two clouds with the same centre $\mu (x)$ but different widths — small ${\sigma }^2(x)$ (tight) vs large ${\sigma }^2(x)$ (loose). Bagging's whole promise is: keep $\mu (x)$ fixed, shrink the width.

5. How two models relate: covariance $\mathrm{Cov}$ and correlation $\rho$

To predict what happens when we average models, one model's spread isn't enough — we must know whether two models err together.

6. Putting it together — deriving the variance of the average

We want the spread of the bagged prediction $\bar{f}(x)=\frac{1}{B}{\sum }_{b=1}^B{\hat{f}}_b(x)$. Two rules do the whole job.

Rule A — expectation is linear (the centre is unchanged).

Rule B — variance of a sum (the spread does shrink). Here is why covariance had to enter.

Now plug in $a_b=\frac{1}{B}$, $\mathrm{Var}({\hat{f}}_b)={\sigma }^2$, and (from §5) $\mathrm{Cov}({\hat{f}}_i,{\hat{f}}_j)=\rho {\sigma }^2$. There are $B$ diagonal terms and $B(B-1)$ off-diagonal pairs:

$\mathrm{Var}(\bar{f})=\frac{1}{B^2}[\underset{\text{diagonal}}{\underbrace{B{\sigma }^2}}+\underset{\text{off-diagonal}}{\underbrace{B(B-1)\rho {\sigma }^2}}].$

Divide through by $B^2$ and simplify:

$\boxed{\mathrm{Var}(\bar{f})=\rho {\sigma }^2+\frac{1-\rho }{B}{\sigma }^2}$

Read it with your new vocabulary: the shared-wobble part $\rho {\sigma }^2$ comes straight from the covariance cross-terms and never shrinks; the personal-wobble part $\frac{1-\rho }{B}{\sigma }^2$ comes from the diagonal and melts as $B$ grows. If that sentence makes sense, you're ready for the parent page.

7. The exponential $e$ and the number $0.368$

The parent claims $(1-\frac{1}{n}{)}^n\to e^{-1}\approx 0.368$. Where does $e$ come from?

Why $e$ and not just "compute the number"? Because $n$ changes from problem to problem, but the answer barely moves once $n$ is a few hundred — it locks onto the constant $e^{-1}$. That stability is why the parent can quote a single "37%" for any large dataset.

Prerequisite map

Equipment checklist

Test yourself — each line is a question ::: answer reveal.