Bagged Predictions and Out-of-Bag Assessment
Bagging fits many versions of a learning method to bootstrap samples and combines their predictions. For regression trees, the combination is an average. The same bootstrap samples also provide a built-in assessment: a tree can predict an observation that was not used to fit that tree. These predictions are called out-of-bag (OOB) predictions.
Care is needed because an ordinary bagged prediction and an OOB prediction use different sets of trees. An ordinary prediction averages all fitted trees. An OOB prediction for a particular case averages only trees whose bootstrap samples excluded that case. The OOB mean squared error is then calculated across cases, after forming one OOB prediction for each case.
The word “appears” refers to the number of times an observation is drawn, not merely whether it occurs at least once in a list of distinct cases. A bootstrap sample has \(n\) draws, so some observations are repeated and others are omitted. Repeated observations affect the fitted tree, while an omitted observation can be used to assess that tree’s prediction.
The first expression uses every tree. The second uses only trees that did not train on observation \(i\). If every observation has at least one OOB prediction, the OOB mean squared error is
If some cases have no OOB trees, their OOB predictions are undefined. The MSE can then be averaged over the \(n_{\mathrm{eval}}\) cases with at least one OOB prediction, with that denominator stated explicitly. An undefined prediction must not be replaced by zero.
Why Bootstrap Samples Produce OOB Cases
For any fixed observation \(i\), one draw from the training data misses it with probability \(1-1/n\). Because the \(n\) draws are made independently with replacement, the probability that all draws miss it is
Thus, for \(B\) independently generated bootstrap samples, the expected number of trees that exclude a particular case is \(Bq_n\). The probability that the case is excluded from every tree is \((1-q_n)^B\). As \(n\) grows, \(q_n\) approaches \(e^{-1}\), about \(0.368\). This is a probability for a particular case and tree; it does not mean every case is OOB for exactly that fraction of a finite forest.
Averaging can also reduce prediction variability. For an illustrative calculation, suppose each tree’s prediction at a fixed \(x\) has variance \(\sigma^2\), and every pair of tree predictions has correlation \(\rho\). Then the variance of their mean is
The first equality adds the \(B\) individual variances and the \(B(B-1)\) ordered pairwise covariance terms. When tree predictions are positively correlated, increasing \(B\) reduces the second term but does not eliminate the component associated with \(\rho\). This identity explains why averaging helps under its stated equal-variance and equal-correlation assumptions; it is not a formula for calculating OOB MSE.
Tracking Bootstrap Samples and Predictions
Worked Example: From Bootstrap Draws to an OOB MSE
A hypothetical claims-screening study has four observations with responses \(y=(10,12,16,20)\). Five regression trees are fitted, each to a bootstrap sample of four draws. The samples, identified by observation number, are \(T_1:(1,1,2,4)\), \(T_2:(2,3,3,4)\), \(T_3:(1,2,4,4)\), \(T_4:(1,1,3,4)\), and \(T_5:(1,2,3,3)\). The trees’ predictions at the four observed predictor vectors are shown below.
| Tree | Prediction for case 1 | Prediction for case 2 | Prediction for case 3 | Prediction for case 4 |
|---|---|---|---|---|
| \(T_1\) | 11 | 13 | 15 | 21 |
| \(T_2\) | 9 | 12 | 17 | 19 |
| \(T_3\) | 10 | 14 | 16 | 20 |
| \(T_4\) | 12 | 11 | 18 | 22 |
| \(T_5\) | 8 | 13 | 15 | 18 |
Step 1: Find each tree’s OOB case. \(T_1\) contains cases 1, 2, and 4, so case 3 is OOB. \(T_2\) contains cases 2, 3, and 4, so case 1 is OOB. \(T_3\) contains cases 1, 2, and 4, so case 3 is OOB. \(T_4\) contains cases 1, 3, and 4, so case 2 is OOB. \(T_5\) contains cases 1, 2, and 3, so case 4 is OOB. Repeated draws, such as the two draws of case 1 in \(T_1\), do not create additional distinct cases.
Step 2: Average only eligible trees for each case. Case 1 is OOB only for \(T_2\), giving \(\hat f_{\mathrm{OOB}}(x_1)=9\). Case 2 is OOB only for \(T_4\), giving \(\hat f_{\mathrm{OOB}}(x_2)=11\). Case 3 is OOB for \(T_1\) and \(T_3\), giving \((15+16)/2=15.5\). Case 4 is OOB only for \(T_5\), giving \(\hat f_{\mathrm{OOB}}(x_4)=18\).
Step 3: Calculate squared errors and average them across cases. The four errors are \(10-9=1\), \(12-11=1\), \(16-15.5=0.5\), and \(20-18=2\). Their squares are \(1\), \(1\), \(0.25\), and \(4\). Therefore, the OOB MSE is \((1+1+0.25+4)/4=1.5625\).
Step 4: Compare with ordinary bagged predictions. Averaging all five trees gives predictions \(50/5=10\), \(63/5=12.6\), \(81/5=16.2\), and \(100/5=20\). Their squared errors against these same training responses are \(0\), \(0.36\), \(0.04\), and \(0\), for a training-set MSE of \(0.4/4=0.1\). This is not the OOB MSE: the ordinary bagged predictions include trees that used the corresponding case to fit. The much smaller training error here is not evidence that generalization error is \(0.1\).
Method and trap avoided. The method is to identify OOB membership tree by tree, average eligible predictions by case, and then average case-level squared errors. A common mistake is to average all five predictions for each case and call the result OOB; that reuses in-bag information and gives a different quantity.
OOB Averaging Must Happen Before Squaring
Worked Example: Different OOB Counts Across Cases
A second hypothetical study has five observed responses, \(y=(8,11,13,17,21)\). The OOB tree predictions available for each case are listed below. The number of predictions differs across cases, as can happen when some observations are excluded from more bootstrap samples than others.
| Case | Observed response | OOB tree predictions | OOB average | Squared error of OOB average |
|---|---|---|---|---|
| 1 | 8 | 9, 7 | 8 | 0 |
| 2 | 11 | 10, 12, 11 | 11 | 0 |
| 3 | 13 | 14 | 14 | 1 |
| 4 | 17 | 15, 18 | 16.5 | 0.25 |
| 5 | 21 | 19, 20 | 19.5 | 2.25 |
For case 1, the average is \((9+7)/2=8\), so its squared error is \((8-8)^2=0\). For case 2, the average is \((10+12+11)/3=11\), giving squared error \(0\). Case 3 has average \(14\), so \((13-14)^2=1\). Case 4 has average \((15+18)/2=16.5\), so \((17-16.5)^2=0.25\). Case 5 has average \((19+20)/2=19.5\), so \((21-19.5)^2=2.25\). The OOB MSE is therefore \((0+0+1+0.25+2.25)/5=0.7\).
A tempting but incorrect alternative is to calculate squared error for every individual OOB tree prediction and divide by the total number of such predictions. The per-case totals of those squared errors are \(2,2,1,5,5\), summing to \(15\); there are \(2+3+1+2+2=10\) OOB predictions. That calculation gives \(15/10=1.5\), not \(0.7\). It answers a different question because it squares before averaging tree predictions and gives cases with more OOB trees more weight.
Method and trap avoided. For the usual OOB MSE, average predictions within each case first, calculate one squared error for each case, and then give each evaluated case equal weight. The number of eligible trees determines the precision of a case’s OOB average, not its weight in this standard MSE formula.
Interpreting the OOB Estimate
OOB assessment is useful because it does not require setting aside a separate validation sample: each tree supplies predictions for cases excluded from that tree’s fit. However, the OOB predictions for one case are averages over a subset of the ensemble, and different cases can have different subset sizes. With too few trees, some cases may have no OOB prediction or an average based on very few trees.
An OOB estimate is not identical in every respect to error on a wholly new sample. Each OOB tree was trained on a bootstrap sample drawn from the available training data while excluding the case being predicted. In particular, the OOB tree did not use that case but may have fewer distinct training cases than a tree in the full fitted ensemble. OOB MSE is therefore a useful internal estimate of predictive error, not a guarantee of the exact error on future observations.
For each tree, note which observation numbers appear at least once. An observation is OOB only if it appears zero times.
Use only trees that excluded that case; average their predictions. Mark the prediction undefined if no eligible tree exists.
Subtract each available OOB prediction from its observed response, then square the difference.
Use the number of cases with defined OOB predictions as the denominator, and state that denominator if it is less than \(n\).
This sequence prevents two especially consequential errors: allowing in-bag predictions into the OOB average, and treating each tree-level prediction as a separate case when calculating the usual OOB MSE. Both change the target quantity being computed.
Check Your Understanding
Work through each calculation in order; the answers provide a check on both the arithmetic and the quantity being estimated.
- A training set has \(n=8\) observations and \(B=12\) bootstrap trees, with eight draws per tree. What is the expected number of trees for which a particular observation is OOB? Give the answer to four decimal places. (Answer: \(12(7/8)^8=4.1233\) trees.)
- A case has observed response \(9\) and OOB tree predictions \(8,10,13\). Calculate its OOB prediction and its squared error. (Answer: OOB prediction \(31/3=10.3333\); squared error \(16/9=1.7778\).)
- Three cases have observed responses \(4,7,9\) and OOB predictions \(5,5,12\), respectively. Calculate the OOB MSE. (Answer: \((1+4+9)/3=14/3=4.6667\).)
- For \(n=3\) and \(B=5\), what is the probability that a specified case is OOB for at least one tree? (Answer: \(1-[1-(2/3)^3]^5=1-(19/27)^5\approx0.8274\).)
- Three cases have responses \(5,8,10\), with OOB prediction sets \((4,7)\), \((7)\), and \((9,10,11)\). Calculate the standard case-level OOB MSE, averaging predictions within each case first. (Answer: \(\big[(5-5.5)^2+(8-7)^2+(10-10)^2\big]/3=1.25/3=0.4167\).)