Estimating the variance of a bootstrap aggregator performance? 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. 
 A: 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.
