Bootstrap Assessment of Classification Error

Why Bootstrap Assessment Needs Care

A classifier's error is not a fixed property of its fitted rule alone: it depends on the population that will supply future cases, and the fitted rule depends on the training sample. Resampling the observed data can reveal how sensitive an assessment is to changes in that sample. But the way each resampled data set is used matters. Evaluating predictions on observations that helped fit the classifier is not the same as evaluating on observations left out of that fit.

The bootstrap is especially useful when a separate test set is small or unavailable. Its assessment is still an approximation based on the observed sample, not a substitute for information about an unknown population. The central distinction in this tutorial is between out-of-bag (OOB) evaluation, which evaluates a bootstrap-fitted classifier on cases omitted from that bootstrap sample, and apparent error on the resampled training data, which reuses cases that contributed to fitting.

Definition: Let $D_n=((X_1,Y_1),\ldots,(X_n,Y_n))$ be an independent sample from a population distribution $P$, with predictors $X_i$ and class labels $Y_i$. The empirical distribution $P_n$ assigns probability $1/n$ to each observed pair. A bootstrap sample $D_n^*$ consists of $n$ independent draws from $P_n$, with multiplicities retained. For a fitted classifier $h$, its population misclassification risk is $R_P(h)=P\{h(X)\ne Y\}$.

A classifier-building procedure maps a training data set to a rule $h$. Any data-dependent steps that are part of the intended procedure—such as preprocessing, feature selection, or tuning—must be repeated using only the training portion in each assessment replicate. Otherwise, information from the case being evaluated may have leaked into the fitted rule.

Out-of-Bag Evaluation

For one bootstrap sample, an original observation is out of bag if it was not selected in any of the $n$ bootstrap draws. Fit the classifier to the bootstrap sample, then evaluate it only on original observations that are out of bag. Repeating this process gives each original observation opportunities to be evaluated by classifiers fitted without it.

Definition: For bootstrap replicate $b$, let $I_{bi}=1$ if observation $i$ is absent from the replicate's training sample and $I_{bi}=0$ otherwise. Let $h_b$ be the classifier fitted on that sample. The pooled OOB error across $B$ replicates is $$ \widehat R_{\mathrm{OOB},B} = \frac{\displaystyle\sum_{b=1}^{B}\sum_{i=1}^{n} I_{bi}\,\mathbf{1}\{h_b(X_i)\ne Y_i\}} {\displaystyle\sum_{b=1}^{B}\sum_{i=1}^{n} I_{bi}}, $$ provided the denominator is positive.

This ratio pools all eligible prediction errors. It is not generally the same as first computing an error rate within each replicate and then averaging those rates: the replicate-specific rates have different denominators, and averaging ratios need not equal taking a ratio of totals.

Theorem: Fix the observed data set and suppose the learning procedure is deterministic, or any algorithmic randomness is independently included in each replicate. Let $q_n=(1-1/n)^n$, and define $e_i=E_*[\mathbf{1}\{h^*(X_i)\ne Y_i\}\mid i\text{ is OOB},D_n]$, where $E_*$ averages over bootstrap resampling and any algorithmic randomness. For independent bootstrap replicates, as $B\to\infty$, $$ \widehat R_{\mathrm{OOB},B}\xrightarrow{a.s.}\frac{1}{n}\sum_{i=1}^{n}e_i. $$

Proof. For each $i$, a single bootstrap draw avoids observation $i$ with probability $1-1/n$. Since the $n$ draws are independent, $P_*(I_{bi}=1\mid D_n)=q_n$. Conditional on $i$ being omitted, the expected error indicator is $e_i$; therefore $$ E_*[I_{bi}\mathbf{1}\{h_b(X_i)\ne Y_i\}\mid D_n]=q_n e_i. $$ Across replicates, the vectors of indicators are independent and identically distributed, and their components are bounded. The strong law of large numbers applied to the denominator divided by $B$ gives $$ \frac{1}{B}\sum_{b=1}^{B}\sum_{i=1}^{n}I_{bi}\xrightarrow{a.s.}nq_n. $$ Applied to the numerator divided by $B$, it gives convergence to $q_n\sum_{i=1}^{n}e_i$. Since $nq_n>0$ for $n>1$, the denominator limit is positive. Taking the ratio yields the stated limit. $\square$

The theorem identifies what repeated OOB assessment averages, conditional on the observed data: each observation's expected error when evaluated by bootstrap-fitted rules that omitted it. It does not say that this quantity equals the population risk of the rule trained on all $n$ original cases. The bootstrap training samples contain fewer than $n$ distinct cases on average, and their composition differs from the full data set.

How Often Is a Case Out of Bag?

The omission probability also explains why OOB evaluation can work and why its training sets are not equivalent to the original full sample. Let $U$ be the number of distinct original observations appearing in a bootstrap sample. For each original case, the probability of appearing at least once is $1-q_n$. Summing these inclusion indicators gives the expected number of unique cases.

Result: In a size-$n$ bootstrap sample, the probability that a specified observation is omitted is $q_n=(1-1/n)^n$, and the expected number of distinct observations included is $E_*[U]=n(1-q_n)$.

Derivation. For a specified observation, each draw misses it with probability $1-1/n$. All $n$ draws miss it with probability $(1-1/n)^n$. Now write $U=\sum_{i=1}^n J_i$, where $J_i=1$ if case $i$ appears at least once. Since $E_*[J_i]=1-q_n$, linearity of expectation gives $E_*[U]=\sum_i E_*[J_i]=n(1-q_n)$. No independence among the $J_i$'s is needed for this expectation calculation. $\square$

Worked Example: Omission Probability for Four Cases

A data set has $n=4$ observations, and each bootstrap sample contains four draws with replacement. Find the probability that a particular case is OOB and the expected number of distinct cases in a bootstrap sample.

For any one draw, the probability of not selecting that case is $3/4$. It is omitted in all four draws with probability $$ q_4=\left(\frac{3}{4}\right)^4=\frac{81}{256}\approx 0.3164. $$

The expected number of distinct cases is therefore $$ E_*[U]=4\left(1-\frac{81}{256}\right) =4\left(\frac{175}{256}\right) =\frac{700}{256} =\frac{175}{64} \approx 2.7344. $$

Thus each case is eligible for OOB evaluation in about 31.6% of replicates, while a bootstrap training sample contains about 2.73 distinct cases on average. These are expectations across many resamples; they do not claim that any individual replicate has a fractional number of cases.

Bootstrap Training Error Is Not OOB Error

A different calculation predicts the bootstrap-fitted classifier on the very draws used to train it. This is a resampled version of apparent error. Duplicated observations count with their multiplicities when that error is calculated. Because the classifier has already seen those training draws, their prediction errors do not constitute independent test evidence. In a flexible model, this error can be much smaller than error on new cases.

Worked Example: Multiplicities and a Majority-Class Rule

There are six original observations. Cases 1, 2, and 3 have class A; cases 4, 5, and 6 have class B. A classifier predicts the most frequent class in its training data, resolving a tie in favor of A. Consider the bootstrap sample of indices $(1,1,2,4,4,5)$.

Count the training draws, not just distinct indices. The sample contains three A draws, from indices $1,1,2$, and three B draws, from indices $4,4,5$. It has two distinct sampled A indices and two distinct sampled B indices. Since the draw counts are tied, the fitted rule predicts A.

Resampled training error. Among the six bootstrap draws, the three B draws are misclassified by this rule and the three A draws are correct. Its error on the resampled training draws is $3/6=1/2$.

OOB error for this replicate. The omitted original indices are 3 and 6. The fitted rule predicts A for both. Case 3, whose class is A, is correct; case 6, whose class is B, is wrong. The OOB error is $1/2$. This equality is specific to this sample and rule; it does not make the two error calculations interchangeable.

Worked Example: A Memorizing Classifier

Suppose there are four cases with distinct predictor values $x_1,\ldots,x_4$ and labels A, A, B, B, respectively. Consider a classifier that memorizes the label at every predictor value represented in its training data and predicts A at an unseen value. Take a bootstrap sample with indices $(1,1,2,3)$.

All four training draws are predicted correctly: the classifier has observed each predictor value represented in the sample and stored its corresponding label. Its resampled training error is therefore $0/4=0$.

Case 4 is the only omitted original observation. Its predictor value $x_4$ was not in the training sample, so the classifier predicts the default class A. Since its true class is B, it is wrong. The replicate's OOB error is $1/1=1$.

This example does not claim that every OOB error is large or every apparent error is zero. It demonstrates why the two procedures answer different questions: the in-sample calculation evaluates on training draws, whereas OOB evaluation tests predictions on cases left out of that fit.

Interpreting Variability Across Resamples

A set of bootstrap replicates can show how much an OOB assessment changes as the training data are perturbed. For replicate $b$, one may record its OOB error when it has at least one omitted case. The distribution of these replicate-level values describes resampling variation in that particular procedure, conditional on the observed data. It is not automatically a standard error for population risk: OOB sets differ in size, replicate errors are dependent through shared original cases, and the fitted classifiers overlap in their training data.

Also distinguish this variation from Monte Carlo error. Increasing $B$ reduces the random fluctuation caused by using a finite number of bootstrap draws to approximate the conditional bootstrap calculation. It does not create more independent observations from the population, and it does not remove the approximation between the empirical distribution and the unknown $P$.

If the goal is to study the sampling variability of a reported assessment statistic, a further bootstrap approach is to resample the original data and rerun the entire assessment procedure in each outer replicate. The statistic then has a distribution across outer resamples. This is computationally more demanding and still relies on the empirical distribution as a stand-in for the population. When the data set is small, the classifier is unstable, or some classes are rare, the resulting distribution can be especially sensitive to which cases happened to be observed.

Specify the target.
Decide whether the goal is an OOB estimate for the observed data or a bootstrap approximation to the sampling variability of a complete assessment procedure.

Resample cases with replacement.
Draw $n$ labeled observations from the empirical distribution and retain all multiplicities in fitting.

Refit without leakage.
Repeat every training-dependent step using only that replicate's training cases.

Evaluate only eligible cases.
For OOB error, score original cases omitted from the replicate and record the number of eligible cases as well as the number misclassified.

Summarize with the target in view.
Report the pooled OOB error or the chosen variability summary, and explain that it is conditional on the observed data and the specified learning procedure.

Common Pitfalls and Practical Meaning

Counting distinct cases instead of draws. A bootstrap sample of size $n$ always has $n$ draws, even when some indices repeat. For training error, those repeated draws contribute repeatedly.
Calling resampled training error a test error. If a case contributed to fitting, scoring it does not make it an independent test case. Use OOB cases for OOB evaluation.
Confusing more replicates with more data. A large $B$ stabilizes the resampling calculation; it does not increase the original sample size or guarantee accurate population-risk estimation.
Ignoring the training-size difference. Bootstrap samples omit cases and repeat others. OOB performance pertains to classifiers trained on those resamples, not automatically to a classifier fitted once on all $n$ cases.
Leaking tuning or preprocessing information. Any decision based on labels or predictors must be confined to the training portion of each replicate if the assessment is meant to represent new-case prediction.

Bootstrap assessment matters because prediction performance can vary with the particular training cases, especially when the classifier or its tuning choices are unstable. OOB evaluation makes that variation usable without reserving a fixed test set, while the resampling distribution can expose sensitivity to the observed data. The interpretation must remain tied to the procedure actually run: who was trained on, who was evaluated, and what source of variability is being summarized.

Check Your Understanding

Use the definitions and calculations above to answer these questions.

For a bootstrap sample of size $n$, derive the probability that a specified observation is omitted.
Why does the pooled OOB error not generally equal the simple average of replicate-specific OOB error rates?
A bootstrap sample contains three A draws and three B draws but only two distinct sampled indices from each class. Under the tie rule used above, which class is predicted, and why?
Explain why a memorizing classifier can have zero resampled training error and positive OOB error.
What does increasing the number of bootstrap replicates reduce, and what important source of uncertainty does it not remove?