When we assess the quality of a Random Forest, for example using AUC, is it more appropriate to compute these quantities over the Out of Bag Samples or over the hold out set of cross validation?
I hear that computing it over the OOB Samples gives a more pessimistic assessment, but I don't see why.
Note: While I feel that my answer is probably correct, I also feel doubtful due to the fact that I made all this up by thinking about this problem only after reading this question for about 30-60 minutes. So you better be sceptical and scrutinize this and not get fooled by my possibly overly confident writing style (me using big words and fancy Greek symbols doesn't mean I am right).
This is just a summary. All details are mentioned in sections $\S1$ and $\S2$ below.
Let's assume the case of classification (can be extended to regression too, but omit for brevity). Essentially, our goal is to estimate the error of a forest of trees. Both out-of-bag error and k-fold cross-validation try to tell us the probability that:
Which is identical to the probability that:
And both are identical. The only difference is that k-fold cross-validation and OOBE assume different size of learning samples. For example:
Therefore in my view the only reason why OOBE is a pessimistic estimation of forest's error is only because it usually trains by a smaller number of samples than usually done with k-fold cross-validation (where 10 folds is common).
Due to that, I also think that 2-fold cross-validation is going to be more pessimistic estimation of forest's error than OOBE, and 3-fold cross-validation to be approximately equally pessimistic to OOBE.
Each tree in RF is grown by a list of $n$ samples that are randomly drawn from the learning set $\mathcal{X}$ with replacement. This way, the $n$ many samples can have duplicates, and if $n = |\mathcal{X}|$ then it can be found that approximately one 3rd of the samples in $\mathcal{X}$ are likely to end up not being in the list of $n$ samples that are used to grow a given tree (these are the out-of-bag samples of this specific tree. This process is independently repeated for each tree, so each tree has a different set of out-of-bag samples.
Now, let's re-describe bagging a bit differently with the hope of finding an equal description that is hopefully simpler to deal with.
I do this by stating that the tree $t$ is trained by the bagged samples in the set $\mathcal{X}_t \subseteq \mathcal{X}$. However, this is not exactly true as the set $\mathcal{X}_t$ does not have duplicated samples (this is how sets work), while -on the other hand- the $n$ list of samples can have duplicates.
Therefore, we can say that a tree $t$ is grown by analysing samples $\mathcal{X}_t$ plus a number of randomly chosen duplicates drawn from $\mathcal{X}_t$, namely $\mathcal{X}_{t,1}, \mathcal{X}_{t,2}, \ldots, \mathcal{X}_{t,r} \subseteq \mathcal{X}_t$, such that: \begin{equation} |\mathcal{X}_t| + \sum_{i=1}^r|\mathcal{X}_{t,i}| = n \end{equation}
It is trivial to see that from this collection of sets $\mathcal{C} = \{\mathcal{X}_t, \mathcal{X}_{t,1}, \ldots, \mathcal{X}_{t,r}\}$, we can define a list of $n$-many samples that contain duplicates by simply appending the elements in each set $\mathcal{C}_i \in \mathcal{C}$ to an array $a$. This way, for any $1 \le p \le n$, there exists at least one value of $i$ such that $a[p] \in \mathcal{C}_i$.
We can also see that the list of $n$ samples in the array $a$ is a generalization of bagging as I defined in Section 1. It is trivial to see that for some specific definition of $\mathcal{X}_t$ that I have defined in this section ($\S2$), list of samples in array $a$ can be exactly identical to the list of samples as defined in Section 1.
Instead of growing tree $t$ by samples in array $a$, we will grow them by the duplication-free list of instances that are found in $\mathcal{X}_t$ only.
I believe that, if $n$ is large enough, a tree $t$ that is grown by analysing samples in $\mathcal{X}_t$ is identical to another tree $t'$ that is grown from the samples in array $a$.
My reason is that, the probability of duplicating samples in $\mathcal{X}_t$ is equally likely across other samples in the same set. This means that, when we measure the information gain (IG) of some split, the IG will remain identical as the entropies will remain identical too.
And the reason I believe entropies won't change systematically for a given split is because the empirically measured probability of a sample having a specific label in some sub-set (after applying a decision split) won't change either.
And the reason the probabilities shouldn't change in my view is that that all samples in $\mathcal{X}_t$ are equally likely to be duplicated into $d$ copies.
Let $\mathcal{O}_t$ be the out-of-bag samples of tree $t$. I.e. $\mathcal{O}_t = \mathcal{X} \setminus \mathcal{X}_t$. Then the error of a single tree $t$ is: \begin{equation} \frac{\text{total $\mathbf{x}$ in $\mathcal{O}_t$ misclassified by $t$}}{|\mathcal{O}_t|} \end{equation} And the total error of the forest with $n_t$ many trees is: \begin{equation} \frac{\sum_{t=1}^{n_t} \text{total $\mathbf{x}$ in $\mathcal{O}_t$ misclassified by $t$}}{\sum_{t=1}^{n_t}|\mathcal{O}_t|} \end{equation} which can be thought as the empirically measured probability that the majority vote of all trees in a forest is a correct vote.
First we partition the learning set $\mathcal{X}$ into $n_k$ many equally-sized partitions namely $\mathcal{K} = \{\mathcal{K}_1, \mathcal{K}_2, \ldots, \mathcal{K}_{n_k}\}$. I.e. $\mathcal{K}_1 \cup \mathcal{K}_2 \cup \ldots \cup \mathcal{K}_{n_k} = \mathcal{X}$, and for any $\mathcal{K}_i, \mathcal{K}_j \in \mathcal{K}$, $\mathcal{K}_i \cap \mathcal{K}_j = \emptyset$ (this is what portioning implies).
Let $\mathcal{K}_t$ be the testing fold, and $\mathcal{K} \setminus \{\mathcal{K}_t\}$ be the set of learning folds.
Let $f$ be a forest of some trees that is built by using $\mathcal{K} \setminus \{\mathcal{K}_t\}$ as the learning set.
Then, k-fold cross-validation of forest $f$ is: \begin{equation} \frac{\sum_{t=1}^{n_k} \text{total $\mathbf{x}$ in $\mathcal{K}_t$ misclassified by $f$}}{\sum_{t=1}^{n_k} |\mathcal{K}_t|} \end{equation}
Which is also probability that forest $f$ classifies any input sample correctly.
The motivation :
Therefore in my view the only reason why OOBE is a pessimistic estimation of forest's error is only because it usually trains by a smaller number of samples than usually done with k-fold cross-validation (where 10 folds is common).
does not seem correct.
It is not true that OOBE error estimate being pessimistic is due to it being trained on a smaller number of samples, actually the contrary applies. In fact, each single random forest's tree is trained on a bootstrapped sample of the training set, so meanwhile it is true that on average every single tree sees about 66% of the training set, but overall the random forest ensemble sees more than that (depending on the number of trees fitted) because the out-of-bag samples of individual trees may not overlap. Hence, supposing we fit a random forest composed of $B$ trees to the entire training set composed of $n$ samples (as in the OOBE case) we have that:
on average each sample $z_i$ appears in the training set of $\frac{2}{3}B$ and in the out-of-bag samples of the remaining $\frac{1}{3}B$
the probability that $z_j$ does not appear in neither the training set of $m$ selected trees is $p_m = (\frac{1}{3})^m$
From the two points above it follows that the OOBE on sample $z_i$ is on average computed considering a subset of $\frac{1}{3}B$ trees that collectively are trained on $n_{OOB}(B) = n-1-np_{\frac{B}{3}} = n(1-p_{\frac{B}{3}})-1$ data samples on average.
When we estimate the error with k-fold cv instead we are doing the following (let's take $k=10$): we fit $B$ trees using $0.9n$ data samples, but again each tree use a bootstrapped version of the training set, so collectively the ensemble sees $n_{10-Fold}(B) = 0.9n(1-p_B)$ data samples on average. Then, considering that $p_{\frac{B}{3}}<0.1$ implies that $n_{OOB} > n_{10-fold}$ we conclude that the ensemble collective training set is larger in the OOB case whenever $B>6$, which is almost always in practice.
Given what we found above, what can we say of the OOB vs k-fold CV estimate for random forests? Is the OOB pessimistic ?
Since the OOBE is evaluated on ensembles that have collectively seen more data it should actually be a less pessimistically biased estimate of the test error with respect to k-fold CV. However, since OOBE ensembles are composed of less trees and are trained on overlapping training sets, the variance of the estimate can be larger.
Actually, it can even be showed that for $\lim_{B\to\infty} $ the OOBE converges to the LOO-CV error estimate (leave one out cross validation)[1] which is unbiased but with higher variance with respect to k-fold CV with $k<n$.
So neither estimator is by default better than the other, even though OOBE has a clear computational advantage since you can "fit and test" your forest at the same time.
[1] Hastie, T., Tibshirani, R., Friedman, J. (2001). The Elements of Statistical Learning.
