# How would one formally prove that the OOB error in random forest is unbiased?

I have read this statement many times but have never come across a proof. I would like to try to produce one myself but I'm not even sure on what notation to use. Can anyone help me with this?

• OOB is not void of bias. The only – often: most important – component of the bias that is removed by OOB is the “optimism” that an in-sample fit suffers from. E.g. OOB is pessimistically biased in that it is based on the averaged predictions of only $\approx 36.8 \%$ of trees in the forest. EDIT: as pointed out in the answer by @cbeleites below. – Jim May 30 '18 at 13:51

I do not know if this is the final answer, but those things can't fit a comment.

The statement that OOB errors are unbiased is often used, but I never saw a demonstration. After many searchings, I finally gave after reading carefully the well-known page of Breiman for RF Section: The out-of-bag (oob) error estimate. In case you did not noticed (as I missed for some time), the last proposition is the important one: This has proven to be unbiased in many tests. So, no sign of formal derivation.

More than that, it seems to be proved that for the case when you have more variables than instances this estimator is biased. See here.

For in-the-bag error there is a formal derivation. The in-the-bag error is the bootstrap error and there is plenty of literature starting with "An Introduction to the Bootsrap, by Efron and Tibshirani". However the cleanest demonstration I saw is here.

If you want to start to find a proof, I think a good starting point is the comparison of this estimate with N-fold cross validation. In ESTL is stated that there is an identity in the limit, as the number of samples goes to infinity.

• I had a quick glance at the Mitchell paper, and so far I don't particularly like it (I think the $n \ll p$ is in a way a coincidence: even random forests are no magic bullet against too few cases. At some point also their performance breaks down and I guess this is the underlying cause of the reported observations). However, the observations of a pessimistic bias are not astonishing to me, see my answer. Actually I think that the thougts I outline in my answer may offer a conceptually rather simple explanation of what is going on there. – cbeleites unhappy with SX Jul 12 '14 at 13:20

Why do you expect the oob error to be unbiased?

• There's (at least) 1 training case less available for the trees used in the surrogate forest compared to the "original" forest. I'd expect this to lead to a small pessimistic bias roughly comparable to leave-one-out cross-validation.

• There are roughly $\frac{1}{e} \approx \frac{1}{3}$ of the number of trees of the "original" forest in the surrogate forest that is actually evaluated with the left-out case. Thus, I'd expect higher variance in the prediction, which will cause further pessimistic bias.

Both thoughts are closely related to the learning curve of the classifier and application/data in question: the first to the average performance as function of training sample size and the second to the variance around this average curve.

All in all, I'd expect you'll at most be able to show formally that oob is an unbiased estimator of the performance of random forests containing $\frac{1}{e} \approx \frac{1}{3}$ of the number of trees of the "original" forest, and being trained on $n - 1$ cases of the original training data.

Note also that Breiman uses "unbiased" for out-of-bootstrap the same way as he uses it for cross validation, where we also have a (small) pessimistic bias. Coming from an experimental field, I'm OK with saying that both are practically unbiased as the bias is usually much less of a problem than the variance (you're probably not using random forests if you have the luxury of having plenty of cases).

• I didn't expect it to be. It is mentioned by people on many places so I just accepted it. Now that I have been thinking about it is why I wanted to prove it. I like you're answer let me play around with your info a bit to see what I can conclude. – JEquihua Jul 15 '14 at 16:39
• @JEquihua: I'd certainly be interested in the result. – cbeleites unhappy with SX Jul 16 '14 at 9:18
• The oob forest is about 1/3 of the original one, not 2/3 (so more reason for the oob error to be pessimistic!). The probability of picking a given tree T for the oob forest of a given observation (x,y) is the probability of (x,y) not being in T, that is ((N-1)/N)^N = (1 + (-1)/N)^N -> exp(-1) =~ 1/3. So the expected size of the oob forest for (x, y) is about B/3, if B is the size of the original forest. – memeplex May 28 '18 at 18:21
• @memeplex: of course - thanks for spotting. Fixed it. – cbeleites unhappy with SX May 28 '18 at 18:30