Sachin Kr. Rajput

Posted on Aug 3 Edited on Aug 5

Out-of-Bag Error: The Free Exam You Didn't Know You Were Already Taking

#python #datascience #beginners #machinelearning

The One-Line Summary: Because each tree in a Random Forest trains on a bootstrap sample, exactly $(1-1/n)^n \to 1/e \approx 36.8\%$ of rows are invisible to any given tree, so you can score every row using only the trees that never saw it — a validation estimate that costs one fit instead of five, on an exam nobody had to set a single question aside for.

The Parable of the School That Never Set an Exam

The village of Predicta, having fixed its jury by blindfolding every judge, turned to its school — and hit a problem the jury never had. How do you find out whether the teaching worked?

Schoolmaster Alder kept a thousand question cards in a wooden bin. Real problems from real harvests: how to split a disputed field, what a wet season costs in grain. Students learned by working through them. At term's end, Alder needed a number to put in front of the village council.

The Sealed Cupboard

For years Alder did the obvious thing. Before term began he counted out two hundred cards, put them in a cupboard, and locked it. Nobody studied those. At term's end he unlocked it and made the students answer them cold.

Honest. Also expensive, in a way it took him a decade to notice.

THE SEALED CUPBOARD:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Bin: 1000 cards.
  800 -> teaching
  200 -> locked away, untouched, all term

Cost 1: students never learn from 200 real
        problems. They finish the term WORSE
        than they had to be.

Cost 2: the exam is only 200 questions. Draw an
        unlucky 200 and the school looks awful.
        Alder ran it twice, different cards:
          cupboard A -> 71 of 200 correct
          cupboard B -> 84 of 200 correct
        Same students, same teaching. 13 points.

A clerk proposed the fix: seal a DIFFERENT 200
five times, teach the whole term five times,
average the five numbers.

It worked. It cost five terms.

This is the price of an HONEST HOLD-OUT.

Alder accepted that price the way you accept weather. One term for a shaky number, or five for a steady one. Pick.

Nim Notices the Ledger

The person who broke this open was not a teacher. It was Nim, fourteen, whose entire job was the bin.

Here is how a student got their practice stack. Nim reached in, pulled a card, copied it onto a slate, and dropped the original back in the bin. Then again. A thousand times. A thousand slates from a bin that never got smaller — which means some cards got copied three times, and some never got copied at all.

Nim kept a ledger of every draw, because otherwise he lost count. Nobody had ever asked to read it.

NIM'S LEDGER  (Tova's stack, shrunk to 10 cards)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Draws, in order:  1  3  3  6  7  9  1 10  7  3

  card  1  ■■       card  6  ■
  card  2  -        card  7  ■■
  card  3  ■■■      card  8  -
  card  4  -        card  9  ■
  card  5  -        card 10  ■

10 draws produced only 6 distinct cards.
Tova has NEVER SEEN cards 2, 4, 5, 8.

For Tova — and Tova alone — those four are a
sealed cupboard. Nobody locked it.
It locked itself.

Nim brought the ledger to Alder and asked the question that ended the sealed cupboard forever.

"Why are we locking cards away, when every student already has hundreds they have never once seen — and a different set for each one?"

Alder did not follow at first. Nim explained it card by card.

GRADING CARD 47, THE FREE WAY
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Twelve students. Nim reads his ledger:

  Tova   drew it 2x    -> DISQUALIFIED, she studied it
  Bram   never drew it -> eligible  ✓
  Ilse   drew it 1x    -> DISQUALIFIED
  Ozan   never drew it -> eligible  ✓
  ... (of 12, four never drew card 47)

Ask ONLY those four. They are answering a
question they were never taught.

  Bram ✓   Ozan ✓   Vell ✗   Hedda ✓
  -> 3 of 4. Card 47 counts as CORRECT.

Repeat for all 1000 cards. Each is graded by a
different quarter of the class.

Cards sealed away:      0
Terms of teaching used: 1

Alder ran it that autumn and got 84 correct in every hundred. Then, out of pure suspicion, he ran the old five-cupboard ritual too — five full terms of work — and got 84 as well.

He had been paying five terms for a number sitting in a fourteen-year-old's notebook the whole time.

Why the Cupboard Locks Itself

What unsettled Alder was that the fraction never moved. Every student, every term, roughly the same share of the bin went unseen.

THE ARITHMETIC OF THE MISSING THIRD
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

One draw from a bin of n cards.
Chance it is NOT card 47:        1 - 1/n

The card goes back in, so the next draw has the
same chance. And the next. n draws in total:

  P(card 47 never drawn) = (1 - 1/n)^n

Watch that as the bin grows:

     n = 10    ->  0.349
     n = 100   ->  0.366
     n = 1000  ->  0.3677
     n -> huge ->  0.3679

It does not drift. It CONVERGES.
The limit is 1/e = 0.367879...

  IN  a student's stack:  ≈ 63.2% of the bin
  OUT of it:              ≈ 36.8%

Two things the village lived off for years:

  1. Every student arrives with a free exam
     attached, about 368 cards long.
  2. Every free exam is DIFFERENT, so pooling
     them covers the whole bin.

Predicta called it Nim's Third.
Machine learning calls it OUT-OF-BAG ERROR.

Bootstrap sampling was never just a way to make trees different. It was quietly generating a held-out set for every tree, and throwing it away.

What Is Out-of-Bag Error?

Every tree in a Random Forest trains on a bootstrap sample: $n$ rows drawn from your $n$ training rows with replacement. Some rows land in it twice. Some never land at all.

The rows a tree never saw are that tree's out-of-bag (OOB) rows, and for those rows the tree is an honest grader — asked about data it was not fit on. Out-of-bag error flips that from tree-wise to row-wise: for each row, collect the trees that excluded it, average only those, compare against the truth.

Parable	Random Forest
Card in the bin	Training row
Student	Tree
Nim's ledger	Bootstrap indices per tree
Cards never drawn	That tree's OOB rows
Polling only the ignorant	OOB prediction for a row
The school's honest score	`oob_score_`
Five cupboards, five terms	5-fold CV

The Math

Fix a row $i$ and a tree $b$ . Each bootstrap draw picks row $i$ with probability $1/n$ , so it misses row $i$ with probability $1 - 1/n$ . Draws are independent, and there are $n$ :

P(\text{row } i \notin \text{bag } b) = \left(1 - \frac{1}{n}\right)^{n}

Take logs and expand $\ln(1-x) = -x - \tfrac{x^2}{2} - \tfrac{x^3}{3} - \cdots$ with $x = 1/n$ :

n \ln!\left(1 - \frac{1}{n}\right) = -1 - \frac{1}{2n} - \frac{1}{3n^2} - \cdots \;\longrightarrow\; -1

So it converges to $e^{-1} \approx 0.3679$ — and from below: small $n$ leaves out slightly less. Two corollaries you'll use constantly:

With $B$ trees, the number grading row $i$ is $\text{Binomial}(B, 1/e)$ — mean $0.368B$ .
The probability row $i$ is graded by no tree is $(1 - 1/e)^B = 0.632^B$ .

That second one is where OOB goes wrong. We'll come back to it.

The Algorithm

Fit the forest normally, recording the bootstrap indices each tree used.
For each row $i$ , find $S_i = {b : i \notin \text{bag}_b}$ .
If $S_i$ is empty, skip the row — and be nervous.
Otherwise average the trees in $S_i$ : soft-vote probabilities for classification, mean for regression.
Score those pooled predictions against $y$ .

Note step 4. OOB uses roughly $0.368B$ trees per row, not $B$ . You are estimating a smaller forest than the one you shipped.

First, Let's Verify the 36.8%

No theory. Just draw cards and count.

# Empirically verifying the 36.8% -- no theory, just counting.
import numpy as np

rng = np.random.default_rng(42)
TRIALS = 2000

print(f"{'n':>7} {'measured':>10} {'(1-1/n)^n':>11} {'1/e':>8} {'diff':>8}")
print("-" * 48)
for n in [5, 10, 25, 100, 500, 2000, 10000]:
    left_out = []
    for _ in range(TRIALS):
        draw = rng.integers(0, n, n)          # bootstrap: n draws WITH replacement
        seen = np.zeros(n, dtype=bool)
        seen[draw] = True
        left_out.append(1.0 - seen.mean())    # fraction of rows never drawn
    measured = float(np.mean(left_out))
    theory = (1 - 1 / n) ** n
    print(f"{n:>7} {measured:>10.4f} {theory:>11.4f} "
          f"{1/np.e:>8.4f} {abs(measured - 1/np.e):>8.4f}")

print(f"\n1/e = {1/np.e:.6f}  ->  {100/np.e:.2f}% of rows sit out every tree.")

      n   measured   (1-1/n)^n      1/e     diff
------------------------------------------------
      5     0.3288      0.3277   0.3679   0.0391
     10     0.3488      0.3487   0.3679   0.0191
     25     0.3602      0.3604   0.3679   0.0077
    100     0.3663      0.3660   0.3679   0.0016
    500     0.3675      0.3675   0.3679   0.0004
   2000     0.3680      0.3678   0.3679   0.0001
  10000     0.3679      0.3679   0.3679   0.0000

1/e = 0.367879  ->  36.79% of rows sit out every tree.

measured tracks (1-1/n)^n to four decimals at every size, and both walk up to $1/e$ from below. By $n=25$ you're within 0.008 of the limit. For any dataset you actually care about, "36.8% of rows are out-of-bag" is exact enough to plan with.

Out-of-Bag Error in Scikit-Learn

One keyword argument. That is the whole API.

import time
import numpy as np
from sklearn.datasets import make_classification
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import cross_val_score, train_test_split

X, y = make_classification(n_samples=2000, n_features=20, n_informative=5,
                           n_redundant=5, random_state=42)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=42)

def fresh():
    return RandomForestClassifier(n_estimators=200, oob_score=True,
                                  random_state=42, n_jobs=-1)

# --- Route 1: OOB. One fit. The score falls out of it for free.
t0 = time.perf_counter()
rf = fresh().fit(X_tr, y_tr)
oob_time = time.perf_counter() - t0
oob = rf.oob_score_

# --- Route 2: 5-fold cross-validation. Five fits.
t0 = time.perf_counter()
cv = cross_val_score(fresh(), X_tr, y_tr, cv=5, scoring="accuracy")
cv_time = time.perf_counter() - t0

# --- Route 3: the held-out test set we are not allowed to peek at.
test = rf.score(X_te, y_te)

print(f"OOB score          : {oob:.4f}   ({oob_time:.2f}s, 1 fit)")
print(f"5-fold CV mean     : {cv.mean():.4f}   ({cv_time:.2f}s, 5 fits)"
      f"  +/- {cv.std():.4f}")
print(f"Held-out test score: {test:.4f}   (the ground truth)")
print(f"\nfolds: {np.round(cv, 4)}")
print(f"OOB is off by      : {abs(oob - test):.4f}")
print(f"5-fold is off by   : {abs(cv.mean() - test):.4f}")
print(f"Time saved         : {cv_time / oob_time:.1f}x")

OOB score          : 0.9021   (0.28s, 1 fit)
5-fold CV mean     : 0.9036   (1.44s, 5 fits)  +/- 0.0132
Held-out test score: 0.8983   (the ground truth)

folds: [0.9143 0.8893 0.9143 0.9143 0.8857]
OOB is off by      : 0.0038
5-fold is off by   : 0.0052
Time saved         : 5.1x

Sit with those three numbers. 0.9021, 0.9036, 0.8983. The spread across all three is under half a point — smaller than the spread between individual CV folds (0.8857 to 0.9143). And on this run OOB was the closer of the two to the held-out truth.

One fit versus five — 5.1x on this run. Exactly the multiple you'd predict: cross-validation's cost model is trivial, $k$ folds means $k$ forests.

The Three Attributes You Need

Attribute	What it holds
`oob_score=True`	Turns the machinery on. Requires `bootstrap=True`.
`oob_score_`	Accuracy for classifiers, $R^2$ for regressors. Higher is better.
`oob_decision_function_`	Pooled OOB probabilities, `(n, n_classes)`. `oob_prediction_` on regressors.

oob_decision_function_ is the one people ignore and shouldn't. oob_score_ collapses everything into one accuracy number, often the wrong one. The decision function hands you raw per-row probabilities, so you can compute ROC-AUC, log loss, balanced accuracy or a calibration curve — from a single fit, with no leakage. Since sklearn 1.3 you can skip that step and pass a callable straight to oob_score, e.g. oob_score=roc_auc_score.

Three traps:

ExtraTreesClassifier defaults to bootstrap=False. oob_score=True alone raises; set both. (More tomorrow.)
max_samples changes the fraction. Drawing $f \cdot n$ samples makes the OOB fraction $e^{-f}$ , not $e^{-1}$ . max_samples=0.5 leaves out 60.7% of rows.
OOB only covers what happens inside fit. Scale or impute beforehand and OOB will launder that leakage. Cross-validation inside a Pipeline will not.

The Trees That Grade You Are Fewer Than You Think

Each row is scored by only ~36.8% of your trees. With 200 that is ~74 graders: plenty. With 10 it is ~4, and some rows get none at all.

import warnings
import numpy as np
from sklearn.datasets import make_classification
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import train_test_split

X, y = make_classification(n_samples=2000, n_features=20, n_informative=5,
                           n_redundant=5, random_state=42)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=42)

print(f"{'trees':>6} {'oob_score_':>11} {'test':>8} {'oob-test':>9} "
      f"{'rows w/o OOB':>13} {'warned':>7}")
print("-" * 60)
for B in [5, 10, 25, 50, 100, 200]:
    with warnings.catch_warnings(record=True) as caught:
        warnings.simplefilter("always")
        rf = RandomForestClassifier(n_estimators=B, oob_score=True,
                                    random_state=42, n_jobs=-1).fit(X_tr, y_tr)
        warned = any("OOB" in str(w.message) for w in caught)
    df = rf.oob_decision_function_
    orphans = int(np.isnan(df).any(axis=1).sum() + (df.sum(axis=1) == 0).sum())
    test = rf.score(X_te, y_te)
    print(f"{B:>6} {rf.oob_score_:>11.4f} {test:>8.4f} "
          f"{rf.oob_score_ - test:>+9.4f} {orphans:>13} {str(warned):>7}")

print(f"\nP(a row is OOB for no tree at all) = 0.632^B")
for B in [5, 10, 25, 50]:
    print(f"  B={B:<4} -> {0.632**B:.2e}  ~= {0.632**B * 1400:.1f} of 1400 rows")

 trees  oob_score_     test  oob-test  rows w/o OOB  warned
------------------------------------------------------------
     5      0.7829   0.8750   -0.0921           154    True
    10      0.8479   0.8983   -0.0505            16    True
    25      0.8893   0.9000   -0.0107             0   False
    50      0.8964   0.9000   -0.0036             0   False
   100      0.9000   0.8983   +0.0017             0   False
   200      0.9021   0.8983   +0.0038             0   False

P(a row is OOB for no tree at all) = 0.632^B
  B=5    -> 1.01e-01  ~= 141.2 of 1400 rows
  B=10   -> 1.02e-02  ~= 14.2 of 1400 rows
  B=25   -> 1.04e-05  ~= 0.0 of 1400 rows
  B=50   -> 1.09e-10  ~= 0.0 of 1400 rows

At five trees, OOB reports 0.7829 for a forest whose real accuracy is 0.8750. Nine points pessimistic — and it says so, in a UserWarning everybody scrolls past. 154 of 1,400 rows had no eligible grader at all, where theory predicted 141.

READING THE TREE-COUNT TABLE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Each row is graded by ~0.368 x B trees.

  B=5    ->  ~2 graders  measuring a 2-TREE
                         forest. Useless.
  B=25   ->  ~9 graders  bias mostly gone
  B=200  ->  ~74 graders OOB ≈ test  ✓

The bias has a DIRECTION: always pessimistic.
A 74-tree vote is worse than a 200-tree vote,
so OOB understates your real forest.

RULES OF THUMB:
  ✗ B < 25    OOB is noise. Ignore it.
  ✓ B >= 100  OOB is trustworthy.
  ✓ B >= 250  bias below measurement noise.

"Some inputs do not have OOB scores" is not a
bug. It is too few trees. Add trees.

The direction of that bias is the useful part: too few trees makes your model look worse than it is, never better. A conservative lie is survivable. Next, the lies that go the other way.

When Out-of-Bag Error Lies

OOB rests on one assumption: a row that is out-of-bag is genuinely unseen. Break it and the number turns actively harmful — it stays confident while becoming wrong.

import numpy as np
from sklearn.datasets import make_classification
from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import balanced_accuracy_score, roc_auc_score
from sklearn.model_selection import GroupKFold, cross_val_score

rng = np.random.default_rng(42)

# ---- LIE #1: rows that are not independent (400 patients, 5 visits each)
Xb, yb = make_classification(n_samples=400, n_features=20, n_informative=5,
                             n_redundant=5, random_state=42)
groups = np.repeat(np.arange(400), 5)
X = np.repeat(Xb, 5, axis=0) + rng.normal(0, 0.01, (2000, 20))  # near-twins
y = np.repeat(yb, 5)

rf = RandomForestClassifier(n_estimators=200, oob_score=True,
                            random_state=42, n_jobs=-1).fit(X, y)
grouped = cross_val_score(
    RandomForestClassifier(n_estimators=200, random_state=42, n_jobs=-1),
    X, y, cv=GroupKFold(n_splits=5), groups=groups).mean()

print("LIE #1 -- grouped rows (5 near-duplicate visits per patient)")
print(f"  oob_score_          : {rf.oob_score_:.4f}   <- looks fantastic")
print(f"  GroupKFold accuracy : {grouped:.4f}   <- the honest number")
print(f"  OOB overstates by   : {rf.oob_score_ - grouped:+.4f}")

# ---- LIE #2: heavy class imbalance
Xi, yi = make_classification(n_samples=2000, n_features=20, n_informative=5,
                             n_redundant=5, weights=[0.97, 0.03],
                             flip_y=0.01, random_state=42)
rfi = RandomForestClassifier(n_estimators=200, oob_score=True,
                             random_state=42, n_jobs=-1).fit(Xi, yi)
proba = rfi.oob_decision_function_
oob_pred = rfi.classes_[proba.argmax(axis=1)]

print(f"\nLIE #2 -- imbalance ({np.bincount(yi)[1]} positives of {len(yi)})")
print(f"  oob_score_ (accuracy)   : {rfi.oob_score_:.4f}   <- 'great model!'")
print(f"  always-predict-majority : {(yi == 0).mean():.4f}   <- the dumb baseline")
print(f"  OOB balanced accuracy   : {balanced_accuracy_score(yi, oob_pred):.4f}")
print(f"  OOB recall on positives : {(oob_pred[yi == 1] == 1).mean():.4f}")
print(f"  OOB ROC-AUC             : {roc_auc_score(yi, proba[:, 1]):.4f}")

LIE #1 -- grouped rows (5 near-duplicate visits per patient)
  oob_score_          : 1.0000   <- looks fantastic
  GroupKFold accuracy : 0.8620   <- the honest number
  OOB overstates by   : +0.1380

LIE #2 -- imbalance (72 positives of 2000)
  oob_score_ (accuracy)   : 0.9710   <- 'great model!'
  always-predict-majority : 0.9640   <- the dumb baseline
  OOB balanced accuracy   : 0.5972
  OOB recall on positives : 0.1944
  OOB ROC-AUC             : 0.8440

Lie #1 is a perfect 1.0000. Every row correct — and the reason has nothing to do with the model being good. When patient 219's third visit is out-of-bag for a tree, that patient's other four visits are almost certainly in-bag. The tree memorised a near-identical row. OOB thinks it is testing on unseen data; it is testing on a photocopy. Hold out whole patients with GroupKFold and the truth is 0.8620 — fourteen points lower. Time series is the same disease with a clock: yesterday and today are near-twins, so bootstrapping smears the future into the past. Use TimeSeriesSplit.

Lie #2 is quieter and therefore worse. oob_score_ says 0.9710. But predicting "negative" for all 2,000 rows scores 0.9640 — the model beat a constant by 0.7 points. Its recall on the class you built the thing to find is 0.1944: it misses four of every five positives. The AUC of 0.8440 says the ranking has real signal; the default 0.5 threshold throws it away. oob_score_, being plain accuracy, hid all of that behind one flattering number.

THE THREE WAYS OOB LIES
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

1. TOO FEW TREES         direction: pessimistic
   Rows get 0-4 graders. Noisy, understated.
   Fix: n_estimators >= 100, and read the
        "Some inputs do not have OOB" warning.

2. NON-INDEPENDENT ROWS  direction: OPTIMISTIC
   Panels, repeat customers, multi-visit
   patients, time series, duplicate rows.
   An OOB row's twin is in-bag -> leakage.
   Measured: 1.0000 vs 0.8620 real.
   Fix: GroupKFold / TimeSeriesSplit. OOB
        CANNOT be repaired here — bootstrap
        has no idea groups exist.

3. CLASS IMBALANCE       direction: meaningless
   oob_score_ is plain ACCURACY. At 97:3 the
   trivial model already scores 0.9640.
   Measured: 0.9710 accuracy, but recall on
   positives = 0.1944.
   Fix: score oob_decision_function_ yourself,
        or pass a callable to oob_score.

The honest summary:
  OOB assumes rows are INDEPENDENT and that you
  have ENOUGH TREES. It never checks either.

Out-of-Bag Error from Scratch

Nim's insight was that the ledger was the whole trick. So let's write the ledger: bootstrap by hand, remember who saw what, score each row using only the trees blind to it.

import numpy as np
from sklearn.datasets import make_classification
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier


def oob_score_from_scratch(X, y, n_estimators=200, seed=42):
    """The whole trick: keep the ledger of who saw what."""
    rng = np.random.default_rng(seed)
    n, classes = len(X), np.unique(y)
    votes = np.zeros((n, len(classes)))   # summed probs from EXCLUDING trees
    n_graders = np.zeros(n, dtype=int)    # how many trees never saw each row

    for _ in range(n_estimators):
        in_bag_idx = rng.integers(0, n, n)          # bootstrap, WITH replacement
        seen = np.zeros(n, dtype=bool)
        seen[in_bag_idx] = True
        oob = ~seen                                 # <-- the 36.8%

        tree = DecisionTreeClassifier(
            max_features="sqrt", random_state=int(rng.integers(1 << 31))
        ).fit(X[in_bag_idx], y[in_bag_idx])

        # credit only the rows this tree was blind to
        cols = np.searchsorted(classes, tree.classes_)
        votes[np.ix_(oob, cols)] += tree.predict_proba(X[oob])
        n_graders[oob] += 1

    scored = n_graders > 0                          # rows with >=1 honest grader
    pred = classes[votes[scored].argmax(axis=1)]
    return (pred == y[scored]).mean(), scored.sum(), n_graders.mean()


X, y = make_classification(n_samples=2000, n_features=20, n_informative=5,
                           n_redundant=5, random_state=42)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=42)

mine, scored, avg = oob_score_from_scratch(X_tr, y_tr, 200, seed=42)
theirs = RandomForestClassifier(n_estimators=200, oob_score=True,
                                random_state=42, n_jobs=-1).fit(X_tr, y_tr)

print(f"my OOB score        : {mine:.4f}")
print(f"sklearn oob_score_  : {theirs.oob_score_:.4f}")
print(f"difference          : {abs(mine - theirs.oob_score_):.4f}")
print(f"rows scored         : {scored} of {len(X_tr)}")
print(f"avg graders per row : {avg:.1f} of 200  ({avg / 200:.1%})")

my OOB score        : 0.9029
sklearn oob_score_  : 0.9021
difference          : 0.0007
rows scored         : 1400 of 1400
avg graders per row : 73.8 of 200  (36.9%)

Seven ten-thousandths apart — different random draws, same estimator. There is no hidden machinery in oob_score_; it is ~seen and a running tally.

And look at the last line, the article closing its own loop: 73.8 graders out of 200 — 36.9%. Not because I asked for it. Because $1/e$ is what falls out of drawing $n$ times from $n$ with replacement, whether you notice or not.

Three details that matter more than they look:

seen[in_bag_idx] = True handles duplicate indices for free — assigning True twice is still True. That's why the ledger is a boolean mask, not a counter.
votes accumulates probabilities, not hard labels. Soft voting is what sklearn uses for oob_decision_function_; hard voting gives a different number.
np.searchsorted(classes, tree.classes_) exists because a bootstrap sample can miss a rare class entirely, leaving that tree's predict_proba with fewer columns than the forest has classes. On balanced data it never fires. On a 99:1 problem it will, and silently corrupts your columns.

When Should You Use OOB?

Situation	Use OOB?	Why
Quick check while iterating	Yes	Free, one fit, instant feedback
Small data you can't split	Yes	Every row trains and validates
Slow fit, tight compute	Yes	5-fold is 5x cost, same answer
Coarse `max_features` sweeps	Carefully	Fine for ranking only
Grouped / time-series data	No	Broken. Use `GroupKFold`
Imbalanced target	Decision function	`oob_score_` is accuracy
Tuning a whole pipeline	No	Upstream leakage hides
The number in the report	No	Use a test set touched once

OOB is your development loop, cross-validation is your decision procedure, the test set is your evidence. Three jobs, and OOB is very good at the first.

The Knobs That Affect OOB

Parameter	Effect on OOB	Guidance
`oob_score`	Turns it on; `True` or a callable (≥ 1.3)	Callable when accuracy is wrong
`bootstrap`	Must be `True`	`False` means no OOB at all
`n_estimators`	Drives the bias (~`0.368 * B` graders)	≥ 100 to trust, ≥ 250 to forget
`max_samples`	OOB fraction becomes $e^{-f}$	`0.5` leaves out 60.7%
`class_weight`	`'balanced_subsample'` reweights per bag	Changes predictions, not the metric
`warm_start`	Adding trees recomputes OOB	Watch OOB stabilise cheaply

max_samples is the trap. A genuinely useful lever — smaller bootstraps mean faster fits, more diverse trees and more OOB rows per tree — but the 36.8% rule of thumb stops applying the moment you touch it.

Quick Reference Card

OUT-OF-BAG ERROR: CHEAT SHEET
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

WHAT IT IS:
  Bootstrap leaves ~36.8% of rows out of each tree.
  Score every row using ONLY the trees that missed it.
  A validation set that assembles itself, for free.

THE ONE FORMULA:
  P(row not in bag) = (1 - 1/n)^n  ->  1/e = 0.3679

  in-bag  ≈ 63.2%      graders per row ≈ 0.368 x B
  out     ≈ 36.8%      P(no grader)    = 0.632^B

COST:
  OOB = 1 fit        k-fold = k fits
  measured: 0.9021 OOB, 0.9036 5-fold,
            0.8983 test.  ~5x faster.

TRUST IT WHEN:
  ✓ n_estimators >= 100 (>= 250 ideally)
  ✓ Rows are genuinely independent
  ✓ Classes balanced, or you score
    oob_decision_function_ yourself
  ✓ No preprocessing outside the forest

IT LIES WHEN:
  ✗ Few trees      -> pessimistic  (0.78 vs 0.88)
  ✗ Grouped rows   -> OPTIMISTIC   (1.00 vs 0.86)
  ✗ Time series    -> OPTIMISTIC, badly
  ✗ Imbalance      -> meaningless  (0.97 = baseline)
  ✗ bootstrap=False-> does not exist

SKLEARN:
  RandomForestClassifier(
      n_estimators=300, oob_score=True,
      bootstrap=True, n_jobs=-1)
  -> .oob_score_              (acc / R^2)
  -> .oob_decision_function_  (n, n_classes)
  -> .oob_prediction_         (regressors)

Key Takeaways

Bootstrap leaves out $(1-1/n)^n \to 1/e \approx 36.8\%$ of rows per tree — a limit, not an approximation. Measured 0.3679 at $n=10{,}000$ .
A row's OOB prediction uses only the trees that never saw it. Row-wise, not tree-wise. That flip is the entire algorithm.
OOB costs one fit; $k$ -fold costs $k$ . Measured ~5x, for estimates 0.0015 apart — and OOB was closer to the truth.
Each row is graded by only ~ $0.368B$ trees, so OOB estimates a smaller forest than you shipped and runs pessimistic. At $B=5$ : 0.7829 for a 0.8750 model.
n_estimators >= 100, or don't quote the number. $P(\text{no grader}) = 0.632^B$ — 10% of rows at 5 trees, one in a hundred thousand at 25.
Non-independent rows break OOB silently and optimistically. Five visits per patient pushed oob_score_ to a perfect 1.0000 against a real 0.8620. Bootstrap has no concept of a group.
oob_score_ is plain accuracy — at 97:3 it scored 0.9710 while recall on positives was 0.1944. Use oob_decision_function_.
OOB is a development loop, not evidence. Iterate on OOB, decide with cross-validation, report the test set.

The One-Sentence Summary

Out-of-bag error works because Nim was right: the moment you draw $n$ cards from a bin of $n$ with replacement, mathematics quietly locks away $1/e$ of the bin — a different 36.8% for every tree — so the honest exam you were about to pay for by sealing data away and refitting five times has already been written and graded, and all you have to do is read the ledger of who saw what.

What's Next?

Now that you can validate a forest for free, you're ready for:

Extra Trees — tomorrow. A third source of randomness: stop searching for the best split and pick thresholds at random. Faster and often better — and its bootstrap=False default means OOB is off until you say otherwise.
AdaBoost — the first great alternative to averaging. Build trees in sequence and make each obsess over what the last got wrong.
Gradient Boosting — the same idea reframed as gradient descent in function space, each tree fitting the residuals of everything before it.
The Boosting series — where our whole variance-reduction story flips into a bias-reduction story, and every bagging intuition has to be re-earned.

Follow me for the next article in the Random Forests Deep Dive series!

Let's Connect!

If Nim's ledger made out-of-bag error click, drop a heart!

Questions? Ask in the comments — I read and respond to every one.

Have you ever shipped a model on an OOB score? I have, twice — and once it was panel data with repeat customers. A beautiful 0.97 that fell apart in week one. Group your folds. 📚

What I keep coming back to is that Nim wasn't smarter than the schoolmaster. He just happened to be holding the ledger, and he was curious enough to read it. Most of the free information in an engineering organisation works like this: already generated, already written down by whoever does the unglamorous part of the job, and thrown away because nobody senior enough to act on it has ever looked.

Share this with the next person who runs 5-fold CV on a 500-tree forest and waits. Tell them to check the ledger first.

DEV Community