Quantifying Uncertainty in Random Forests via Confidence Intervals and Hypothesis Tests

This paper develops tools for performing formal statistical inference for predictions generated by a broad class of methods developed under the algorithmic framework of data analysis. In particular, we focus on ensemble methods - combinations of many individual, frequently tree-based, prediction functions - which have played an important role. We present a variant of bagging and random forests, both initially introduced by Breiman [1996, 2001b], in which base learners are built on randomly chosen subsamples of the training data and the final prediction is taken as the average over the individual outputs. We demonstrate that this fits into the statistical framework of U-statistics, which were shown to have minimum variance by Halmos [1946] and later demonstrated to be asymptotically normal by Hoeffding [1948]. This allows us to demonstrate that under weak regularity conditions, predictions generated by these subsample ensemble methods are asymptotically normal. We also provide a method to consistently estimate the variance in the limiting distribution without increasing the computational cost so that we may produce confidence intervals and formally test feature significance in practice. Though not the focus of this paper, it is worth noting that this 1 subbagging procedure - suggested by Andonova et al. [2002] for use in model selection - was shown by Zaman and Hirose [2009] to outperform traditional bagging in many situations.