Stability of Random Forests and Coverage of Random-Forest Prediction Intervals
This work addresses the need for trustworthy uncertainty quantification in machine learning predictions, particularly for practitioners using random forests, though it is incremental as it builds on existing stability and coverage analysis.
The authors tackled the problem of ensuring reliable prediction intervals from random forests by establishing stability under mild conditions and proving non-asymptotic bounds for coverage probability, showing that random forests can provide justified interval prediction at minimal extra cost.
We establish stability of random forests under the mild condition that the squared response ($Y^2$) does not have a heavy tail. In particular, our analysis holds for the practical version of random forests that is implemented in popular packages like \texttt{randomForest} in \texttt{R}. Empirical results show that stability may persist even beyond our assumption and hold for heavy-tailed $Y^2$. Using the stability property, we prove a non-asymptotic lower bound for the coverage probability of prediction intervals constructed from the out-of-bag error of random forests. With another mild condition that is typically satisfied when $Y$ is continuous, we also establish a complementary upper bound, which can be similarly established for the jackknife prediction interval constructed from an arbitrary stable algorithm. We also discuss the asymptotic coverage probability under assumptions weaker than those considered in previous literature. Our work implies that random forests, with its stability property, is an effective machine learning method that can provide not only satisfactory point prediction but also justified interval prediction at almost no extra computational cost.