13
$\begingroup$

In Random Forest, each tree is grown in parallel on a unique boostrap sample of the data. Because each boostrap sample is expected to contain about 63% of unique observations, this leaves roughly 37% of observations out, that can be used for testing the tree.

Now, it seems that in Stochastic Gradient Boosting, there is also an $OOB_{error}$ estimate similar to the one in RF:

If bag.fraction is set to be greater than 0 (0.5 is recommended), gbm computes an out-of-bag estimate of the improvement in predictive performance. It evaluates the reduction in deviance on those observations not used in selecting the next regression tree.

Source: Ridgeway (2007), section 3.3 (page 8).

I have trouble understanding how it works/is valid. Say I am adding a tree in the sequence. I am growing this tree on a random subsample of the original data set. I could test this single tree on the observations that were not used to grow it. Agreed. BUT, since Boosting is sequential, I am rather using the entire sequence of trees built so far to provide a prediction for those left-out observations. And, there is a high chance that many of the preceding trees have already seen these observations. So the model is not really being tested at each round on unseen observations like with RF, right?

So, how come this is called "out-of-bag" error estimate? To me, it does not appear to be "out" of any bag since the observations have already been seen?

$\endgroup$
6
  • 1
    $\begingroup$ See the discussion here github.com/scikit-learn/scikit-learn/pull/1806. You are not alone in expressing concerns the way OOB estimates are calculated. $\endgroup$
    – mpiktas
    Sep 16, 2015 at 12:34
  • $\begingroup$ thanks for the link, but unfortunately all the thread contributors seem to be as lost as I am! $\endgroup$
    – Antoine
    Sep 16, 2015 at 12:54
  • 1
    $\begingroup$ Actually no. See github.com/scikit-learn/scikit-learn/pull/2188. In this commit the OOB score is changed to OOB improvement the way gbm does it. I do not know how this idea works precisely, but from what I gathered, the oob sample for the current tree is used to calculate OOB improvement. I did not managed to find the mathematical formulas, so it is necessary to dig into gbm code to see how precisely this improvement is calculated. $\endgroup$
    – mpiktas
    Sep 16, 2015 at 13:08
  • 1
    $\begingroup$ Nope, unfortunately. Some hints are given by the above links (in the comments), this thread, and this other thread. This is driving me completely crazy. Someday someone should shoot an email to Dr. Friedman/Hastie... Thanks for your attention though. $\endgroup$
    – Antoine
    Oct 19, 2015 at 17:54
  • 1
    $\begingroup$ I have the same problem as @Antoine: to me, it does not seem possible to do bagging in Gradient Boosting (no matter the implementation), since even if you train with a small subsample of data (using "subsample" parameter in sklearn), like 10%, in the i-th iteration, the ensemble will have seen the entire training dataset. Thus, in practice, it may provide good results, but because it will be overfitting. Well, at least that is how I see it! Comments welcome! EDIT: I mean, it CAN be done, but my point is whether it makes SENSE. $\endgroup$
    – iamgin
    Nov 29, 2016 at 10:54

3 Answers 3

3
$\begingroup$

Answering only partially (and adding a new question to your question).

The gbm implementation in R http://www.rdocumentation.org/packages/gbm/functions/gbm has two parameters to adjust some out-of-bagness.

a) train.fraction will define a proportion of the data that is used to train all trees and thus 1-train.fraction will be true OOB (out-of-bag) data.

b) bag.fraction will define the proportion of training data to be used in the creation of the next tree in the boost. Thus there may be some data that is never used for the creation of any tree and they can be truly used as OOB data.(but it is unlikely, see the question below)

Which brings me to the question. Your analysis of 37% of data as being OOB is true for only ONE tree. But the chance there will be any data that is not used in ANY tree is much smaller - $0.37^{ntrees}$ (it has to be in the OOB for all $ntree$ trees - my understanding is that each tree does its own bootstrap). So in RandomForests it should be very unlikely to be any OOB to test the forest. And yet the randomForest implementation in R (based on Breiman's original code) talks a lot about OOB (for example the result data err.rate and confusion see http://www.rdocumentation.org/packages/randomForest/functions/randomForest)

I dont know how to answer that (and I thank you (+1) for asking the question and making me realize I don't understand this aspect of randomForests). The possible solution is that there is only one bootstrap - and all trees are constructed from it - but as far as I know , it is not the case.

$\endgroup$
6
  • 1
    $\begingroup$ For RF/Bagging, there is no issue: at any given step in the ensemble-building process, any observation in the original data set can be fed to all the trees that were trained on boostrap samples devoid of this observation. Approximately one third (~37%) of the total number of trees will meet this condition. Further, by letting these tree vote and taking the most popular class, a prediction can be obtained for the observation. The number of times the prediction differs from the true label of the observation averaged over all classes, gives the out-of-bag error estimate $\endgroup$
    – Antoine
    Apr 25, 2015 at 21:48
  • 1
    $\begingroup$ also, it seems that what gives the OOB error estimate ability in Boosting does not come from the train.fraction parameter (which is just a feature of the gbm function but is not present in the original algorithm) but really from the fact that only a subsample of the data is used to train each tree in the sequence, leaving observations out (that can be used for testing). Which goes back to my original question. How can these observations be used for testing since they have probably been seen many times by many preceding trees in the sequence? $\endgroup$
    – Antoine
    Apr 25, 2015 at 21:57
  • $\begingroup$ forgot to mention that each tree in RF is indeed built from its very own, unique bootstrap sample of the original data $\endgroup$
    – Antoine
    Apr 25, 2015 at 22:06
  • $\begingroup$ @user2835597 thanks for your explanations regarding RF. Thus a OOB error of a RF is really evaluating only 1/3 of the trees in the forest (that does not look very useful to me). Well, learning something everyday. $\endgroup$ Apr 25, 2015 at 22:22
  • $\begingroup$ Anyway, the train.fraction parameter seems to be the answer to your question. The sklearn implementation also has a similar parameter, the subsample (see scikit-learn.org/stable/modules/generated/… $\endgroup$ Apr 25, 2015 at 22:31
0
$\begingroup$

I believe that the OOB stuff works differently on Random Forrests and Gradient Boosting.

On Random Forrests, you can train a tree on a portion of the data (train data) and thus any predictions on the OOB data are clean-room predictions. So, the implementation would keep two separate arrays in order to implement OOB predictions. Each of these two array has the same length as the data passed in to the fit() method. The first array (y_hat_oob) would keep a sum of the OOB y_hats for each OOB data point, and the second array (oob_count) would keep a count of how many predictions (trees) contributed to each OOB prediction (for each data point). So, let's say you have 10 data points (0..9) and your first bag uses points (0..4) for training and (5..9) for OOB. You fit() a tree on points (0..4) and use that tree to predict() on points (5..9). You add the predictions to the y_hat_oob array for points (5..9) and you add 1 to the oob_count array in points (5..9). Now, let's say your bag 2 uses points (5..9) for training and thus points (0..4) for oob. You do the same, store the oob predictions in the y_hat_oob array points (0..4) and increment the corresponding counts. Now you have two trees in your model, but since you use only 0.5 of your data for oob, then your oob contains predictions from only (number of trees) * (proportion of oob data) trees (2 * 0.5 = 1). To get the actual y_hat_oob at the end of training, you'd need to divide y_hat_oob by count_oob -- this does the same as averaging all the predictions from all the tree models. Ok, so that's Random Forrests, and this was the easy one.

For Gradient Boosting, I believe there is a problem. Because each tree depends on the predictions from prior trees, you can't take the same approach as with Random Forrests. What you CAN do is calculate the OOB "improvement" in "performance" due to the latest iteration/model. You'd calculate the error/performance on the iteration OOB data using the models of the prior iteration. Now, once the new iteration model is fit(), then you can recalculate the error/performance on the same OOB data and calculate the difference. That will give you and estimate of the OOB "improvement" in performance due to the latest iteration. At least this is how I understand things.

Hope that helps.

$\endgroup$
-2
$\begingroup$

I believe they do out of bag estimation on each step. Since results of all steps are added (with coefficients), OOB errors can be also added with same coefficients.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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