When performing cross-validation or bootstrap re sampling to estimate the performance of some machine learning algorithm, one commonly records the mean and variance of the errors obtained in of all the trials. This is commonly used in model selection, such as choosing the simplest (or quickest to run) model whose mean is within 1 sigma of the best mean (or some other rule of thumb).

Typically I have seen it stated that when using bootstrap aggregators (such as random forest) the out of bag error should be an unbiased estimate of the generalisation error, and therefore we don't need to bother doing cross-validation to estimate the error, we get that for free. In my experience this is usually true, however I don't see how I can get an estimate of the variance of that estimate, comparable to that which you get from CV or bootstrap resampling.

Is there a reasonable way to estimate this variance? We can't simply take the variance of the individual ensemble members (e.g. the trees in the case of random forest) since they will all have a much worse error than the ensemble (that being the point of bagging!). Is there some other reasonable approach?

Please note that statistical/machine learning is not my main field and I tend to get a bit muddled with the terminology at times. Please correct any misuse or confusing terminology.


I am not sure variance is the right thing to be looking for. A complex procedure like regression using a variable selection method or generating a random forest will change with slight changes in the data. So what I think is good in those situations is to bootstrap the entire procedure. That means getting bootstrap samples and for each bootstrap sample go through the entire procedure. This can be very computer-intensive but also very enlightening. Often you see surprising differences in the algorithms choice from one bootstrap sample to the next. But for example in variable selection you may see certain important variables being selected consistently more often than the others. So the bootstrap provides the variability or sensitvity of the procedure to small changes in the data. But important patterns that you wouldn't see otherwise may emerge. It is another way to do sensitivity analysis.

In the case of bagging procedures in random forests it may be interesting to look at what treeare used in the ensemble each time. You can also compute classification error rates each time and see how that varies from one bootstrap sample to the next. I think you can even estimate a variance for the classification error due to the perturbations in the data.

The idea in stepwise logistic regression of bootstrapping the selection procedure was first given by Gail Gong in her dissertation at Stanford in the early 1980s. I discuss some of this in my bootstrap books.

  • $\begingroup$ There's an important point that this answer misses. I am interested in evaluating the bagging procedure without doing re sampling (either by bootstrap or CV or whatever else). I know there are all sorts of useful things one can learn by resampling, but this question was directed at the case where we want to make a short cut in the case of bagging procedures (and indeed whether or not there is any good shortcut). Was that not clear enough in the question (e.g. the entire second paragraph)? This is a good answer with useful advice, but seems to answer a different question. Have I misunderstood? $\endgroup$ Jul 18 '12 at 0:24
  • $\begingroup$ I would say the exact objective as you now state it was not clear. I don't know what variance you are looking for or how you would get at it without some sort of sensitivity analysis with the procedure. I really do think that sensitivity analysis or bootstrap are the right ways to evaluate a procedure and they are too often overlooked. It may be that you don't like my answer because it is not telling you what you want to hear. But I think it is an important and possibly the only way to evaluate complex procedures. $\endgroup$ Jul 18 '12 at 0:29
  • $\begingroup$ The first paragraph indicated that I am doing re sampling via CV or bootstrap already. The second paragraph indicated I want to avoid this in the case of bagging procedures. The third paragraph asks whether I can get similar kinds of information that the resampling gives for non-bagging methods without resampling. Your answer gives a clear description of the benefits of bootstrap, but the first sentence of the question indicated I was already doing this. I don't want to argumentative, but can you indicate what you thought the question was asking that lead to your answer? $\endgroup$ Jul 18 '12 at 0:41
  • $\begingroup$ I did point out that my terminology may not be completely accurate, so please indicate where it is unclear and what lead you astray. I'd like to elicit some relevant answers so please help me to improve the question. $\endgroup$ Jul 18 '12 at 0:43
  • $\begingroup$ As I reread it it seems that you are asking for a way to estimate variance without cross-validation or bootstrap. The problem I have with your remarks though is that you seem to be assuming that there is a "relevant" answer out there. I am saying that there probably isn't and that if you are interested in variability due to the procedure then you have to see how the procedure varies as the data gets slightly perturbed. This could be done using simulated sensitivity analysis or by bootstrapping. $\endgroup$ Jul 18 '12 at 1:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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