Out-of-Bag Error Estimation

Why Out-of-Bag Error Is Useful

Bagging fits models to bootstrap samples and combines their predictions. Each bootstrap sample is drawn with replacement from the observed data, so some observations appear more than once and others are omitted. An observation omitted from a particular sample can be evaluated using the model fitted to that sample: that prediction is out of bag for the observation.

This gives bagging a built-in way to assess prediction error without setting aside a separate portion of the observed data. The key is to compare each response only with predictions from models whose bootstrap samples excluded that observation. Including predictions from models that trained on the observation would make the evaluation partly in-sample and could understate predictive error.

Definition: Suppose the observed data are $(x_i,y_i)$, for $i=1,\ldots,n$, and $B$ bootstrap samples are drawn, each containing $n$ draws with replacement from the $n$ observed cases. Let $\hat f^{(b)}$ be the model fitted to bootstrap sample $b$. The out-of-bag set for observation $i$ is $$ \mathcal{O}_i=\{b:\text{observation }i\text{ does not appear in bootstrap sample }b\}, $$ and its out-of-bag count is $m_i=|\mathcal{O}_i|$. An out-of-bag prediction for observation $i$ uses only the fitted models indexed by $\mathcal{O}_i$.

For regression, the usual out-of-bag prediction is the average of the eligible model predictions. For classification, it is usually the class receiving the most eligible votes, with a specified rule for ties. One may instead average predicted class probabilities and classify from those averages, provided the method is chosen consistently.

\hat y_i^{\mathrm{OOB}}=\frac{1}{m_i}\sum_{b\in\mathcal{O}_i}\hat f^{(b)}(x_i),\qquad m_i>0.

With squared-error loss, the out-of-bag mean squared error is the average of the squared differences between each observed response and its out-of-bag prediction. With classification error, each observation contributes one if its out-of-bag class prediction is wrong and zero otherwise. These are examples of a general procedure: compute the chosen loss for each observation using only its eligible out-of-bag prediction, then average the losses.

How Often Is an Observation Out of Bag?

Assume that each bootstrap sample consists of $n$ independent draws from the $n$ observed cases, with each case equally likely on each draw. For a particular observation, the probability of not being selected on one draw is $1-1/n$. The draws are independent within the sample, so the probability that it is omitted from all $n$ draws is

q_n=\left(1-\frac{1}{n}\right)^n.

The probability of appearing at least once is $1-q_n$. As $n$ increases, $q_n$ approaches $e^{-1}$, about 0.368, while the expected fraction of distinct observations included in one bootstrap sample approaches $1-e^{-1}$, about 0.632. These are probability limits and approximations, not exact proportions for every individual sample.

Justification: The event that observation $i$ is out of bag requires that every draw miss it. Each draw misses it with probability $1-1/n$; multiplying this probability across the $n$ independent draws gives $q_n=(1-1/n)^n$. Across $B$ independent bootstrap samples, $m_i$ is therefore binomial with parameters $B$ and $q_n$, so $E[m_i]=Bq_n$ and $P(m_i=0)=(1-q_n)^B$.

Thus, an observation is expected to receive out-of-bag predictions from about $0.368B$ fitted models when $n$ is reasonably large. This expectation does not guarantee that every observation receives that many predictions. In particular, a finite number of bootstrap samples can leave some observations with very few eligible models or none at all. An observation with $m_i=0$ has no out-of-bag prediction; it must not be assigned a prediction from an in-sample model and then treated as an out-of-bag result.

Calculating Out-of-Bag Error

The following examples use small bootstrap collections so that inclusion can be checked directly. In practice, the bootstrap samples and fitted predictions are generated by an algorithm, but the accounting is the same.

Worked Example: Regression Error From Bootstrap Inclusion Counts

A hypothetical regression problem has five observed cases with responses $y=(2,1,5,5,4)$. Four bootstrap samples, each of size five, have the following case indices:

Sample 1: $(1,1,2,4,5)$; sample 2: $(2,2,3,4,4)$; sample 3: $(1,3,3,5,5)$; sample 4: $(1,2,2,3,5)$. The fitted models make the following predictions for cases that are out of bag: sample 2 predicts 3 for case 1; sample 3 predicts 2 for case 2 and 6 for case 4; sample 1 predicts 4 for case 3; sample 4 predicts 4 for case 4; and sample 2 predicts 3 for case 5. Find each out-of-bag prediction and the overall mean squared error.

Method. First identify the omissions in each sample. Sample 1 omits case 3; sample 2 omits cases 1 and 5; sample 3 omits cases 2 and 4; sample 4 omits case 4. Therefore, cases 1, 2, 3, and 5 each have one eligible model, while case 4 has two.

Average predictions only across the eligible models. The resulting out-of-bag predictions are $3$ for case 1, $2$ for case 2, $4$ for case 3, $(6+4)/2=5$ for case 4, and $3$ for case 5.

The squared errors, in case order, are $(3-2)^2=1$, $(2-1)^2=1$, $(4-5)^2=1$, $(5-5)^2=0$, and $(3-4)^2=1$. Their sum is $1+1+1+0+1=4$, so the out-of-bag mean squared error is $4/5=0.8$.

Check. The four nonzero squared errors and one zero squared error sum to 4; dividing by all five observed cases gives 0.8. A common mistake is to average the two predictions for case 4 with predictions from other cases, rather than first averaging that case’s eligible model predictions and then calculating its loss.

Worked Example: Classification Votes and a Tie Rule

A hypothetical classifier has four cases. Their true classes are $A,B,A,B$, respectively. Four bootstrap samples are $(1,1,2,3)$, $(2,2,4,4)$, $(1,3,3,4)$, and $(1,2,2,4)$. For out-of-bag cases only, the fitted models predict: sample 1 predicts $B$ for case 4; sample 2 predicts $A$ for cases 1 and 3; sample 3 predicts $A$ for case 2; and sample 4 predicts $A$ for case 3. Use a fixed tie rule that selects $A$ if votes are tied. Calculate the out-of-bag classification error.

Method. Sample 1 omits case 4. Sample 2 omits cases 1 and 3. Sample 3 omits case 2. Sample 4 omits case 3. Thus, case 1 receives one eligible vote for $A$, case 2 receives one for $A$, case 3 receives votes $A$ and $A$, and case 4 receives one for $B$.

The resulting out-of-bag predictions are $A,A,A,B$. Comparing them with the true classes $A,B,A,B$, cases 1, 3, and 4 are classified correctly, while case 2 is misclassified. The error rate is $1/4=0.25$.

Check. Exactly one of the four out-of-bag predictions is incorrect. The stated tie rule is not needed for these votes, but specifying it makes the procedure unambiguous in cases where class votes are tied. A common error is to count a prediction from a sample containing the case; here, for example, case 1 is eligible only for sample 2.

Relationship to Evaluation on New Data

Predictive error is the expected loss on a new observation, evaluated using a model trained on observed data. In out-of-bag evaluation, each observed case plays the role of an evaluation case only for bootstrap-fitted models that did not include it. That exclusion is why the procedure is more informative about prediction on unseen cases than error measured on the same cases used to fit every model.

For a bagged predictor, the out-of-bag estimate combines losses across the observed cases. It is often useful because it uses the available data for both fitting and internal evaluation. Its resemblance to test-set evaluation does not make it identical to evaluation on a fresh, independent sample. Each out-of-bag model is trained on a bootstrap sample drawn from the original data, and that sample typically contains fewer than $n$ distinct cases. The amount of data and the dependence structure of the fitted models can therefore affect the estimate.

Worked Example: Diagnosing an Out-of-Bag Tuning Result

A hypothetical analyst compares 20 choices of tree settings for a bagged classifier on 200 observed cases. The lowest out-of-bag error among the 20 choices is 0.10, and that choice is selected. After selection, the analyst evaluates the chosen model on a separate, untouched set of 50 cases and observes 8 errors. Explain what the two error rates say and identify the main limitation.

Method. The selected out-of-bag error is $0.10$, or 10 errors per 100 cases on the out-of-bag scale. The separate evaluation error is $8/50=0.16$, or 16 errors per 100 cases. The observed difference is $0.16-0.10=0.06$, which is 6 percentage points.

The fresh evaluation result provides a check on the selected procedure using cases that were not used for fitting or choosing among those 20 settings. The difference does not prove that out-of-bag evaluation must understate error by 0.06 in other problems; both estimates vary, and the evaluation set here has only 50 cases.

The limitation is that the same out-of-bag results were used to select the best of 20 settings. Even if each setting’s out-of-bag error is a noisy estimate, choosing the smallest observed value tends to favor a setting whose error benefited from favorable noise. The selected value can therefore be optimistic as an estimate of the performance of the selected procedure. A common mistake is to treat the minimum among many tuned out-of-bag errors as if it came from a single prespecified model.

Assumptions, Limitations, and Exam Traps

The standard inclusion calculation assumes that each bootstrap replicate draws $n$ cases independently with replacement from the same $n$ observed cases. The usual interpretation of out-of-bag error also relies on the observed cases being suitable representatives of the prediction setting. If cases have dependence or structure, a bootstrap that treats all rows as interchangeable may not produce a meaningful evaluation. For example, observations from the same subject or adjacent times may be related; excluding one row while retaining closely related rows can make evaluation unrealistically easy.

Out-of-bag error is most directly suited to evaluating a bagged ensemble. It is not a universal substitute for a fresh evaluation whenever the analyst has repeatedly inspected the same data. Extensive tuning, repeated feature or model choices, or other decisions influenced by out-of-bag results can make the final reported error optimistic. The more choices are made using those results, the less independent the final assessment is from the selection process.

Do not use in-bag predictions. For case $i$, a model belongs in the prediction average only when $i\notin$ its bootstrap sample.
Do not confuse a count with a prediction. The out-of-bag count $m_i$ tells how many eligible models are available; the prediction is computed from those models’ outputs.
Check zero or small counts. If $m_i=0$, no out-of-bag prediction exists. If $m_i$ is small, that case’s prediction may be relatively variable.
Keep the loss definition consistent. For regression, specify the loss, such as squared error. For classification, specify how votes or probabilities become a predicted class, including tie handling if relevant.
Account for tuning. An error value used to choose among many alternatives is not an untouched final assessment of the selected alternative.

Key takeaway: Out-of-bag prediction for a case uses only bootstrap-fitted models whose samples omitted that case. Average the eligible predictions, calculate the chosen loss case by case, and average those losses. This provides a practical internal assessment for bagging, but extensive selection based on the same results can make the reported error optimistic.

Check Your Understanding

For each problem, determine the out-of-bag quantity requested. Use only models whose bootstrap samples omit the case being evaluated.

A bootstrap sample of size 8 is drawn from 8 cases. What is the probability that a specified case is omitted from the whole sample, and how many out-of-bag replicates are expected for that case among 500 independent replicates? (Answer: omission probability $ (7/8)^8\approx0.3436$; expected count $500(7/8)^8\approx171.8$.)
Three regression cases have responses $2,4,5$. Their out-of-bag predictions are respectively $3$, the average of $2$ and $4$, and $4$. Find the out-of-bag mean squared error. (Answer: $1$.)
A binary case has true class $B$, and its eligible out-of-bag models vote $A,B,B,A,B$. What is its out-of-bag class prediction and its zero-one loss? (Answer: class $B$; loss $0$.)
For four cases, the numbers of eligible models are $2,0,3,1$. How many cases have defined out-of-bag predictions, and what must be done with the case having no eligible models? (Answer: 3 cases; no out-of-bag prediction is defined for the case with count 0.)
An analyst compares 30 model settings using the same out-of-bag results and reports the lowest error as the final performance estimate. What is the principal concern, and what kind of evaluation would provide a less selection-contaminated check? (Answer: selecting the minimum can make the reported error optimistic; evaluate the selected procedure on genuinely untouched data.)

What You'll Learn