73

What is out of bag error in Random Forests? Is it the optimal parameter for finding the right number of trees in a Random Forest?

1
  • 9
    If this question is not implementation specific, you may want to post your question at stats.stackexchange.com
    – Sentry
    Sep 2, 2013 at 16:27

2 Answers 2

185

I will take an attempt to explain:

Suppose our training data set is represented by T and suppose data set has M features (or attributes or variables).

T = {(X1,y1), (X2,y2), ... (Xn, yn)}

and

Xi is input vector {xi1, xi2, ... xiM}

yi is the label (or output or class). 

summary of RF:

Random Forests algorithm is a classifier based on primarily two methods -

  • Bagging
  • Random subspace method.

Suppose we decide to have S number of trees in our forest then we first create S datasets of "same size as original" created from random resampling of data in T with-replacement (n times for each dataset). This will result in {T1, T2, ... TS} datasets. Each of these is called a bootstrap dataset. Due to "with-replacement" every dataset Ti can have duplicate data records and Ti can be missing several data records from original datasets. This is called Bootstrapping. (en.wikipedia.org/wiki/Bootstrapping_(statistics))

Bagging is the process of taking bootstraps & then aggregating the models learned on each bootstrap.

Now, RF creates S trees and uses m (=sqrt(M) or =floor(lnM+1)) random subfeatures out of M possible features to create any tree. This is called random subspace method.

So for each Ti bootstrap dataset you create a tree Ki. If you want to classify some input data D = {x1, x2, ..., xM} you let it pass through each tree and produce S outputs (one for each tree) which can be denoted by Y = {y1, y2, ..., ys}. Final prediction is a majority vote on this set.

Out-of-bag error:

After creating the classifiers (S trees), for each (Xi,yi) in the original training set i.e. T, select all Tk which does not include (Xi,yi). This subset, pay attention, is a set of boostrap datasets which does not contain a particular record from the original dataset. This set is called out-of-bag examples. There are n such subsets (one for each data record in original dataset T). OOB classifier is the aggregation of votes ONLY over Tk such that it does not contain (xi,yi).

Out-of-bag estimate for the generalization error is the error rate of the out-of-bag classifier on the training set (compare it with known yi's).

Why is it important?

The study of error estimates for bagged classifiers in Breiman [1996b], gives empirical evidence to show that the out-of-bag estimate is as accurate as using a test set of the same size as the training set. Therefore, using the out-of-bag error estimate removes the need for a set aside test set.1

(Thanks @Rudolf for corrections. His comments below.)

12
  • 4
    Thanks @bourneli, I agree that usefulness is better when the answers are concise but I focussed on putting the answer in context which is what took most space. Apr 9, 2015 at 10:09
  • 12
    Very nice explanation, but there is a small mistake - sampling with replacement, which you call "Bagging", is actually named "Bootstrapping". (en.wikipedia.org/wiki/Bootstrapping_(statistics)) Bagging is the process of taking bootstraps & then aggregating the models learned on each bootstrap. (en.wikipedia.org/wiki/Bootstrap_aggregating)) May 19, 2015 at 12:53
  • 8
    Hi Alex, Basically as explained above - we create an OOB classifier that takes one record at a time (denoted by (Xi,yi) from all the training records available (denoted by T) - find all bootstrap samples or datasets that had this record missing (say T3, T7, T8, T9) - we run the current record (Xi,yi) through our forest but count votes only from the trees corresponding to bootstrap samples that didn't had this record (i.e. K3, K7, K8, K9). Please let me know if it's still not clear. Sep 30, 2015 at 6:21
  • 1
    Now, RF creates S trees and uses m ... random subfeatures out of M possible features to create any tree. It's not to create the whole tree, but to create each node in the tree. As I understand it, each time it has to make a bifurcation node, it samples m features to use.
    – Juan
    Oct 13, 2015 at 17:17
  • 1
    Excellent explanation. Perhaps worth mentioning: depending on the structure of the data, OOB error estimates can differ from the error predicted when training using only a fraction of the entire data. This may affect one's decision for an appropriate number of trees. For example, if your data consists of 1000 data points from 100 separate experiments, the classifier's accuracy will be different if it's trained only on experiments 1-80 and validated on 81-100 versus the OOB approach where all the data points from all 100 experiments are essentially randomized.
    – Mathews24
    Apr 3, 2018 at 4:38
56

In Breiman's original implementation of the random forest algorithm, each tree is trained on about 2/3 of the total training data. As the forest is built, each tree can thus be tested (similar to leave one out cross validation) on the samples not used in building that tree. This is the out of bag error estimate - an internal error estimate of a random forest as it is being constructed.

0

Not the answer you're looking for? Browse other questions tagged or ask your own question.