Out-of-bag error estimation

A "free" validation set that falls out of bagging for free — no separate hold-out required.

The Setup: Why does OOB even exist?

WHAT is OOB error?

WHY does it work? For any single training point $x_i$, the set of trees that excluded it forms a sub-ensemble that treated $x_i$ as unseen data. Aggregating predictions over those trees gives an honest, out-of-sample prediction for $x_i$.

Deriving the magic number: ~37% are out-of-bag

Let's derive the probability a specific point is NOT chosen in one bootstrap sample.

Probability point $i$ is not picked in one draw: $P(\text{miss in 1 draw}) = 1 - \frac{1}{n}$

Why this step? Each draw picks exactly one of $n$ points uniformly; "not $i$" covers the other $n-1$, so probability $= \frac{n-1}{n} = 1-\frac1n$.

Probability point $i$ is never picked across all $n$ independent draws: $P(\text{OOB for } i) = \left(1 - \frac{1}{n}\right)^{n}$

Why this step? Draws are independent, so multiply the per-draw miss probability $n$ times.

Now take the limit as $n \to \infty$: $\lim_{n\to\infty}\left(1 - \frac{1}{n}\right)^{n} = e^{-1} \approx 0.368$

Why this step? This is the classic definition $\lim_{n\to\infty}(1+\frac{x}{n})^n = e^x$ with $x=-1$.

HOW to actually compute OOB error (the algorithm)

1. For each training point $x_i$, find the set $S_i = \{b : x_i \notin \text{bootstrap}(b)\}$ — the trees for which $x_i$ is OOB.
2. Aggregate the predictions of only those trees:
   • Classification: $\hat{y}_i = \text{majority vote}\{T_b(x_i) : b \in S_i\}$
   • Regression: $\hat{y}_i = \frac{1}{|S_i|}\sum_{b \in S_i} T_b(x_i)$
3. Compute the OOB error over all points:

$\text{OOB error} = \frac{1}{n}\sum_{i=1}^{n} L\big(y_i,\; \hat{y}_i\big)$

where $L$ is your loss (0/1 loss for classification, squared error for regression).

Why only trees in $S_i$? Using a tree that trained on $x_i$ would leak the label — the tree could memorize $x_i$, making the estimate optimistically biased. Restricting to $S_i$ keeps it honest.

Worked Example 1 — Which points are OOB?

• In-bag = unique picked = $\{1,2,4\}$. Why? These indices appear at least once, so the tree trained on them.
• OOB for tree $b$ = $\{3,5\}$. Why? Indices 3 and 5 never appear → the tree never saw them → they test this tree.

Check the fraction: OOB fraction $= 2/5 = 0.40$, close to the theoretical $0.368$ (small $n$ noise).

Worked Example 2 — Computing OOB prediction for one point

$T_2(x_7)=1,\quad T_5(x_7)=0,\quad T_9(x_7)=1,\quad T_{11}(x_7)=1$

• Majority vote $= 1$ (three 1's vs one 0). Why? We aggregate only the 4 trees that didn't train on $x_7$ — honest sub-ensemble.
• OOB prediction $\hat{y}_7 = 1 = y_7$ → contributes $0$ to 0/1 loss.

We ignore all other trees (say $T_1, T_3, \dots$) for $x_7$ because they did train on it.

Worked Example 3 — Full OOB error

$\text{OOB MSE} = \frac{4+1+9}{3} = \frac{14}{3} \approx 4.67$

Why divide by $n=3$? Average over all training points, each getting a prediction from its own set of OOB trees.

Common Mistakes (Steel-manned)

Flashcards

Connections

• Bootstrap Aggregating (Bagging) — OOB is a byproduct of sampling with replacement.
• Random Forests — standard consumer of OOB error for model evaluation.
• Cross-Validation — alternative generalization estimate; OOB approximates it cheaply.
• Bias-Variance Tradeoff — bagging reduces variance; OOB measures the resulting test error.
• Bootstrap Sampling — the with-replacement draw that creates the 63/37 split.
• Decision Trees — the base learners being aggregated.

Concept Map

Hinglish (regional understanding)