Bootstrapping the Out-of-sample Predictions for Efficient and Accurate Cross-Validation
This addresses a fundamental problem in machine learning for researchers and practitioners who rely on cross-validation for unbiased model evaluation and selection, offering incremental improvements in efficiency and accuracy.
The paper tackles the optimistic bias in cross-validated performance estimates for model selection by introducing BBC-CV, a bootstrap method that corrects this bias without additional model training, achieving smaller variance and bias than alternatives. It also proposes BCED-CV, which uses bootstrapping to speed up cross-validation by early dropping of inferior configurations, making the process both efficient and accurate.
Cross-Validation (CV), and out-of-sample performance-estimation protocols in general, are often employed both for (a) selecting the optimal combination of algorithms and values of hyper-parameters (called a configuration) for producing the final predictive model, and (b) estimating the predictive performance of the final model. However, the cross-validated performance of the best configuration is optimistically biased. We present an efficient bootstrap method that corrects for the bias, called Bootstrap Bias Corrected CV (BBC-CV). BBC-CV's main idea is to bootstrap the whole process of selecting the best-performing configuration on the out-of-sample predictions of each configuration, without additional training of models. In comparison to the alternatives, namely the nested cross-validation and a method by Tibshirani and Tibshirani, BBC-CV is computationally more efficient, has smaller variance and bias, and is applicable to any metric of performance (accuracy, AUC, concordance index, mean squared error). Subsequently, we employ again the idea of bootstrapping the out-of-sample predictions to speed up the CV process. Specifically, using a bootstrap-based hypothesis test we stop training of models on new folds of statistically-significantly inferior configurations. We name the method Bootstrap Corrected with Early Dropping CV (BCED-CV) that is both efficient and provides accurate performance estimates.