Foundations — Out-of-bag error estimation

This page assumes you have seen nothing. Every letter, ratio, and squiggle in the parent note gets built here, one brick at a time, so that when you read the main OOB topic note every symbol is already an old friend.

0. What is a "dataset" and what does $n$ mean?

The picture: think of $n$ numbered cards laid in a row. Card $i$ carries a question ($x_i$) on the front and its correct answer ($y_i$) on the back.

Why the topic needs it: OOB error is measured per example, so we must be able to point at "example number $i$" precisely. The subscript $i$ is that pointing finger.

1. Drawing "with replacement" — the heart of everything

The word bootstrap means: build a new sample of size $n$ by picking cards one at a time, and each time putting the card back before the next pick. Putting it back = "with replacement".

The picture: a jar of $n$ balls. You reach in, read a ball's number, drop it back, shake, and reach again — $n$ times total. Your new list may read $\{2,2,4,1,4\}$ for $n=5$: ball 3 and ball 5 were never scooped.

Why the topic needs it: "with replacement" is the single mechanism that manufactures a free test set. No replacement → every card is picked exactly once → nothing is ever left out → no OOB. See Bootstrap Sampling.

2. Probability — reading $P(\cdot )$

The picture: a pie sliced into $n$ equal wedges. One wedge = your card. Its slice of the whole pie is $\frac{1}{n}$ of the area.

Why the topic needs it: the famous "37% is out-of-bag" number is a probability. To earn it you must first be comfortable that "not this one card" $=1-\frac{1}{n}$.

3. Independent events → multiply

The picture: flip a coin twice. Chance of two heads $=\frac{1}{2}\times \frac{1}{2}=\frac{1}{4}$. Each independent flip multiplies in a fresh factor.

Here the raised exponent $n$ is not magic notation — it literally means "multiply the same factor $(1-\frac{1}{n})$ by itself $n$ times, once per draw".

Why the topic needs it: a whole bootstrap sample is $n$ draws. To leave card $i$ out we need it missed every single time — that "every time" is what turns the exponent into $n$.

4. The number $e$ and the limit — why 37%?

The picture: plot $(1-\frac{1}{n}{)}^n$ against $n$. As $n$ climbs, the dots flatten onto a horizontal line at about $0.368$. They never wander off — they converge.

So ≈ 36.8% of cards fall out-of-bag per tree, and the rest, ≈ 63.2%, stay in-bag.

Why the topic needs it: this single ratio (37 out / 63 in) is the reason OOB is a usable test set. If only 1% were left out, each point would rarely be OOB and the estimate would be starved.

5. Sets and the symbols $\in$, $\notin$, $\{\cdots \}$, $|\cdot |$

The picture: a fenced pen ($S$) with a few numbered sheep inside. $\in$ = "this sheep is inside the fence"; $\notin$ = "this sheep is outside"; $|S|$ = "count the sheep inside".

In the parent note, $S_i=\{b:x_i\notin \text{bootstrap}(b)\}$ reads plainly as: "$S_i$ is the collection of tree-numbers $b$ such that example $i$ is not in tree $b$'s bootstrap sample" — i.e. the trees for which $i$ is OOB.

Why the topic needs it: OOB prediction for a point only uses that point's own $S_i$ — the exact trees that never trained on it. Sets are how we name "just those trees".

6. Indexing the trees: $B$, $b$, $T_b$

The picture: a shelf of $B$ trained trees, each a little machine. Feed $x_i$ into machine $b$ and out drops a guess $T_b(x_i)$.

Why the topic needs it: the forest (Random Forests, built by Bootstrap Aggregating (Bagging)) is a collection of trees. Every OOB formula is a sum or vote over some subset of these $B$ machines.

7. Aggregation, loss, and the summation sign $\sum$

The picture: $\sum$ is a conveyor belt: each example drops its loss onto the belt, and at the end you read the total — then divide by $n$ to get the average.

Why the topic needs it: the final OOB error is exactly this average loss: $\text{OOB error}=\frac{1}{n}{\sum }_{i=1}^{n}L(y_i,{\hat{y}}_i).$ Every symbol in that line — $\frac{1}{n}$, $\sum$, $L$, $y_i$, ${\hat{y}}_i$ — is now defined.

8. How it all snaps together

Read top-left to bottom-right: the with-replacement draw splits each tree's data into in-bag and out-of-bag; the probability chain explains why ~37% land out-of-bag; the set $S_i$ gathers each point's honest trees; aggregation + loss + $\sum$ turn those honest guesses into one number — the OOB error, a cheap stand-in for Cross-Validation that measures the test error of the forest.

Equipment checklist

Test yourself — cover the right side and answer aloud.