Bootstrapping the out-of-sample predictions for efficient and accurate cross-validation

Abstract

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 (Varma and Simon in BMC Bioinform 7(1):91, 2006) and a method by Tibshirani and Tibshirani (Ann Appl Stat 822-829, 2009), 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 statistical criterion we stop training of models on new folds of inferior (with high probability) configurations. We name the method Bootstrap Bias Corrected with Dropping CV (BBCD-CV) that is both efficient and provides accurate performance estimates.

Keywords: Bias correction; Cross-validation; Hyper-parameter optimization; Performance estimation.

Fig. 1

Average (over 500 repeats) estimated bias of accuracy estimation of the CVT, TT, NCV, BBC-CV and BBCD-CV. The average true classification accuracy of all configurations is 60%. CVT over-estimates performance in all settings. TT’s behaviour varies for sample size $N<500$ and is conservative for $N\ge 500$. NCV provides almost unbiased estimates of performance, while BBC-CV is more conservative with a difference in the bias of 0.013 points of accuracy on average. BBCD-CV is on par with NCV

Fig. 2

Average estimated bias (over 20 sub-datasets for each original dataset) of the CVT, TT, NCV, BBC-CV and BBCD-CV estimates of performance. CVT is optimistically biased for sample size $N\le 100$. TT’s bias varies with sample size and dataset, and it is mainly over-conservative for $N\ge 80$. NCV and BBC-CV, both have low bias though results vary with dataset. BBCD-CV has, on average, greater bias than BBC-CV for $N\le 100$ and identical for $N=500$

Fig. 3

Relative average true performance of the models returned by the BBCD-CV and CVT. For $N\le 100$ the loss in performance varies greatly with dataset, however, for $N=500$ there is negligible to no loss in performance. If N if fairly large, BBCD-CV will accelerate the CVT procedure without sacrificing the quality of the resulting model or the accuracy of its performance estimate

Fig. 4

The speed-up of BBCD-CV over CVT is shown for sample size $N=500$. It is computed as the ratio of models trained by CVT over BBCD-CV. Typically, BBCD-CV achieves a speed-up of 2-5, up to 10 for the gisette dataset. Overall, using BBCD-CV results in a significant speed boost, without sacrificing model quality or performance estimation

Fig. 5

Relative average true performance of BBC-CV¹⁰ to BBC-CV (left), and of BBC-CV¹⁰ to NCV (right). Multiple repeats increase the performance of the returned models, maintaining the accuracy of the performance estimation. If computational time is not a limitation, it is preferable to use BBC-CV¹⁰ over NCV

Fig. 6

Coverage of the $\{50\%,55\%,\cdots ,95\%,99\%\}$ CIs returned by BBC-CV, BBCD-CV, and BBC-CV¹⁰, defined as the ratio of the estimated CIs that contain the corresponding true performances of the produced models. The CIs are mainly conservative and become more accurate with increasing sample size and multiple repeats

Fig. 7

Average width (over all 20 sub-datasets) of CIs with increasing number of repeats (BBC-CV^X, $X=1...10$), for each dataset. CIs shrink with increasing sample size and number of repeats