PaperlayerView exact revision on arXiv

Source-linked AI summary

Bootstrapping the Out-of-sample Predictions for Efficient and Accurate Cross-Validation

Ioannis Tsamardinos, Elissavet Greasidou, Michalis Tsagris, Giorgos Borboudakis

arXiv:1708.07180v2cs.LG

TL;DR

The paper addresses optimistic performance estimates caused by selecting the best configuration through cross-validation, especially when many configurations are tried. It bootstraps pooled out-of-sample predictions to correct this bias without additional model training, and uses bootstrap testing to drop inferior configurations early. Experiments report more accurate, often conservative estimates with substantially lower computational cost than alternatives.

  • Problem

    Selecting the best configuration from repeatedly reused cross-validation tuning sets can produce an optimistically biased estimate of final-model performance.

  • Method

    BBC-CV bootstraps pooled out-of-sample predictions to repeat configuration selection and estimate loss, while BCED-CV additionally drops inferior configurations using bootstrap-based hypothesis tests.

  • Results

    BBC-CV and BCED-CV provide more accurate, almost unbiased or conservative performance estimates with computational speed-ups of up to 10 over alternatives.

  • Takeaways & Limitations

    Bootstrapping out-of-sample predictions supports bias correction, confidence-interval estimation, and early elimination of inferior configurations across performance metrics.

  • Takeaways & Limitations

    BBC-CV with AUC requires scores from models across different folds to be comparable on the same scale.

Abstract

from arXiv · show

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.

1 Introduction

Cross-validation is used to select configurations and estimate final-model performance, but repeatedly evaluating configurations on tuning sets can make the selected configuration’s estimate optimistically biased. The paper introduces bootstrap-based methods that correct this bias and can reduce computation without retraining models.

  • Cross-Validation: Cross-validation partitions data into K non-overlapping folds, averaging each configuration’s performance across folds.Each fold serves as a tuning set while the remaining folds serve as training sets.
  • Bias in Configuration Selection: The selected configuration’s cross-validated performance can be optimistically biased because all configurations repeatedly use the same tuning sets.The optimism can be significant for small samples and many tried configurations.
  • Bias in Configuration Selection: For small samples (< 100), empirical AUC bias frequently ranges from 5% to 10%.The bias depends on the number of configurations, model-performance correlations, sample size, and the gap between the best and remaining configurations.
  • Alternative Estimation: A second untainted hold-out set can estimate the performance of the model trained with the configuration selected during tuning.This avoids reusing the tuning data for final performance estimation but requires additional held-out data.
  • BBC-CV: BBC-CV bootstraps pooled out-of-sample predictions from all configurations, repeatedly selects the minimum-loss configuration, and averages its out-of-sample loss without training additional models.The bootstrap has low computational overhead and is trivially parallelized.
  • BBC-CV: BBC-CV estimates bias more accurately than TT and similarly to nested cross-validation while requiring no new model training.The method is therefore as computationally efficient as TT and much faster than nested cross-validation.
  • BCED-CV: BCED-CV uses a bootstrap-based hypothesis test to drop statistically inferior configurations before training them on remaining folds.This combines early dropping with BBC-CV bias correction to reduce the number of trained models.

2 Preliminaries of Out-of-Sample Estimation

Out-of-sample estimation protocols use held-out predictions to evaluate learning methods and select configurations, but tuning across configurations creates bias whose direction can be uncertain. Nested CV and TT address this issue with different computational and statistical trade-offs.

  • Cross-Validation: K-fold CV partitions data into K non-overlapping folds, trains on K−1 folds, evaluates on the remaining fold, and averages performance across folds.It also returns a final model trained on all available data and can collect out-of-sample predictions for bias correction.
  • Cross-Validation: CV estimates the average loss of models trained on subsets of the data rather than the specific final model trained on all available data.The operational model is therefore trained on the full dataset, not selected from the fold-specific models.
  • Cross-Validation: CV is conservatively biased when full-data models improve with sample size, because each fold model trains on |D\i| = (K −1)/K · |D| < |D| samples.The magnitude depends on the learning curve and K, and conservatism is expected to be stronger with small or imbalanced samples.
  • Tuning and bias: When multiple configurations are cross-validated and the best is selected, the winner’s estimate is also optimistically biased because the tuning sets were repeatedly used for selection.The net bias combines this optimism with CV’s conservatism, and which trend dominates is unknown a priori.
  • Nested Cross-Validation: Nested CV reserves each fold for estimation while repeatedly tuning on the remaining folds, thereby generalizing the train–tune–estimate protocol.For C configurations, NCV requires exactly K^2 × C + K + 1 models.
  • Tibshirani–Tibshirani: The Tibshirani–Tibshirani method corrects CVT bias without additional model training, but its estimate can over-correct or fail to correct, especially with small folds and many configurations.Its correction requires relatively large folds for reliable bias estimation.

3 Related Work

Related work develops bias-correction methods based on repeated resampling, weighted error aggregation, or learning-curve modeling. These methods differ in stability and computational cost, particularly for small datasets.

  • Resampling-based methods: WMC and WMCS use repeated subsampling, train multiple models, and estimate error as a weighted mean across configurations and subsamples.The two variants differ in their weighting procedures.
  • Learning-curve methods: The IPL method estimates each classifier’s error by fitting an inverse power law to a learning curve built from repeated resampling at different sample sizes.It was compared with TT, NCV, and WMC/WMCS on simulated and real datasets.
  • Learning-curve methods: For small original datasets, IPL produces unstable estimates and has higher computational cost than TT and WMC/WMCS.These limitations constrain its efficiency and reliability in small-sample settings.

4 The Bootstrap Bias Corrected Cross-Validation (BBC-CV)

BBC-CV estimates the performance of a configuration selected through tuning by bootstrapping pooled out-of-sample predictions rather than retraining models. The procedure also supports confidence intervals and repeated cross-validation while retaining low computational overhead.

  • Motivation: BBC-CV replaces bootstrap retraining with resampling pooled out-of-sample predictions while tuning across configurations.A direct bootstrap of tuned models would require B × C model trainings, whereas BBC-CV applies configuration selection to prediction matrices.
  • Procedure: The method selects the best configuration on each bootstrap sample and estimates its loss using predictions not selected by that bootstrap.The procedure creates bootstrap matrices from prediction rows, applies the configuration selection strategy, and computes the selected configuration’s loss on out-of-bootstrap samples.
  • Procedure: BBC-CV differs from standard bootstrap by resampling the prediction matrix Π and applying configuration selection rather than the learning method.Because no new models are trained, performance estimation has minimal computational overhead.
  • Confidence intervals: The bootstrap distribution provides confidence intervals for the estimated loss, commonly using a 95% interval from ordered bootstrap estimates.The interval excludes α/2 probability mass from each tail; with α = 0.05 and B = 1000, the interval uses the 25th and 975th ordered estimates.
  • Repeated cross-validation: BBC-CV can be applied to repeated cross-validation by resampling instance indexes so predictions for the same instance across repeats remain together.Predictions from different repeats for the same instance are correlated, so all such predictions must be included in a bootstrap sample or excluded together.

5 Bootstrap Corrected with Early Dropping Cross-Validation (BCED-CV)

BCED-CV uses bootstrap-based hypothesis tests on pooled out-of-sample predictions to drop configurations that are statistically inferior during cross-validation. This can save computation while retaining an accurate performance estimate, but its early-dropping test is heuristic.

  • Early dropping: BCED-CV drops configurations whose bootstrapped performance is statistically inferior to the current best configuration.The test compares each remaining configuration with the current best and stops training the dropped configuration on subsequent folds.
  • Computational savings: Early dropping can substantially reduce computation by eliminating configurations after only a few folds instead of completing K-fold cross-validation.With a strict threshold, the dropped configurations have a low probability of ultimately being optimal, according to the paper.
  • Bootstrap test: A configuration is dropped when the estimated probability that its loss is worse than the current best exceeds the significance threshold α.The paper gives α = 0.99 as an example threshold.
  • Limitation: The procedure is a computational heuristic because it tests each configuration against the current best in isolation rather than modeling the joint selection event.A configuration may appear better than the current best in bootstrap samples while remaining dominated by another configuration.
  • Scope: BCED-CV combines bootstrap correction with early dropping to provide an almost unbiased estimate while supporting general performance measures and relatively small samples.The paper contrasts this bootstrap test with earlier statistical tests and emphasizes its applicability across learning tasks and performance measures.

6 Empirical Evaluation

Empirical evaluations on controlled and real binary-classification problems show that BBC-CV and BCED-CV substantially reduce CV bias while avoiding NCV’s computational cost. BCED-CV can accelerate configuration search with little performance loss at larger sample sizes, while repeated BBC-CV improves model selection and confidence-interval calibration.

  • Evaluation design: The evaluation varies sample size, candidate-configuration count, true performance, datasets, and performance metrics in controlled simulations and real classification problems.Simulations use accuracy, while real datasets are evaluated with AUC.
  • Bias estimation: CVT is optimistically biased, reaching 0.17 points of classification accuracy in simulations, whereas NCV is nearly unbiased but requires quadratically more model training as folds increase.On real datasets, CVT remains optimistically biased for N ≤100, while NCV and BBC-CV generally have low bias.
  • Bias estimation: BBC-CV has low, mainly conservative bias that approaches zero with larger samples; its average bias is 0.013 accuracy points above NCV, while BCED-CV is 0.005 points above NCV on average.BCED-CV’s worst-case excess bias is 0.018 accuracy points, compared with 0.034 for BBC-CV.
  • Relative performance: For N ≤100, BCED-CV’s returned-model performance loss varies substantially and reaches 9.05% in the worst case, but at N = 500 the loss is negligible to absent.At N = 500, losses are 0% on five datasets, 0.44% on gisette, 0.15% on jasmine, and 1.4% on madelon.
  • Multiple repeats and confidence intervals: Ten BBC-CV repeats generally return models at least as good as single-repeat BBC-CV and outperform NCV for N ≥40, while preserving estimation bias and improving confidence-interval calibration.Repeated methods also shrink confidence intervals; three to four repeats appear sufficient for most CI-estimation gains.

7 Conclusions

Bootstrapping pooled out-of-sample predictions addresses performance-estimation bias, confidence-interval estimation, and computational efficiency in configuration selection. BBC-CV and BCED-CV empirically improve accuracy and reduce computational cost, while confidence intervals are mainly conservative and improve with larger samples and repeated partitions.

  • Contributions: Bootstrapping pooled out-of-sample predictions addresses optimism correction, confidence-interval estimation, and dropping inferior configurations.BBC-CV tackles optimism correction and confidence intervals; BCED-CV additionally supports dropping configurations from further consideration.
  • Empirical findings: BBC-CV and BCED-CV outperform nested cross-validation and the TT method through more accurate estimates and/or lower computational cost, with speed-ups of up to 10.The reported estimates are almost unbiased and conservative, including for smaller sample sizes.
  • Confidence intervals: Bootstrapped confidence intervals are mainly conservative and improve with increasing sample size and multiple repeats.The paper reports that repeated application also improves confidence-interval calibration and reduces interval width.
  • Future work: A thorough evaluation on regression and survival analysis remains future work, although preliminary results indicate comparable efficiency and effectiveness.
  • Practical guidance: For small samples, the authors suggest BBC-CV instead of computationally expensive nested cross-validation, while BCED-CV is advocated for larger samples.BCED-CV may select a slightly sub-optimal configuration for small samples but reduces the number of trained models; repeated partitions improve interval widths and configuration selection.
Loading 1708.07180v2…