Performance-Estimation Properties of Cross-Validation-Based Protocols with Simultaneous Hyper-Parameter Optimization

Ioannis Tsamardinos, Amin Rakhshani, Vincenzo Lagani

TL;DR

This paper investigates how different cross-validation (CV) protocols estimate the performance of machine learning models when hyper-parameter optimization is involved. They find that standard CV overestimates performance, especially with small datasets, while Nested CV and a proposed Tibshirani-Tibshirani (TT) method offer more conservative estimates. The TT method is highlighted as a computationally efficient and effective alternative.

What Problem Does This Paper Address?

In machine learning, building a predictive model often involves two critical, intertwined tasks: selecting the best learning algorithm and its associated hyper-parameters (model selection), and then accurately estimating the performance of the final chosen model. Combining these tasks is tricky because the process of trying many hyper-parameter combinations and picking the best one can lead to an overly optimistic performance estimate – essentially, the model might appear better than it truly is because it was "lucky" in the specific data it was evaluated on. This is particularly problematic in fields with limited data, where such optimistic estimates can lead to poor real-world performance. The paper aims to rigorously compare different protocols for handling this challenge, focusing on their bias and variance in performance estimation.

Methods

The paper compares three main cross-validation protocols for performance estimation when hyper-parameter optimization is included:

  • CVM (Cross-Validation with Model Selection): This is the standard approach where K-fold CV is used to select the best hyper-parameters, and the performance is estimated based on this selection. The paper confirms this method is optimistic.
  • TT (Tibshirani and Tibshirani Method): This method attempts to estimate and correct the bias introduced by model selection by analyzing the performance differences across folds. It's designed to be computationally efficient, requiring no additional model training beyond what CVM does.
  • NCV (Nested Cross-Validation): This protocol treats the entire model selection process (including hyper-parameter tuning) as part of the learning function. It uses an outer CV loop to estimate the performance of the inner CV-based model selection process. This is generally considered a more robust but computationally expensive method.

The study also examines the effect of stratification, a technique that ensures each fold in the CV process has a similar class distribution to the original dataset, which is particularly important for small or imbalanced datasets.

Datasets

The experiments were conducted on five real-world datasets from diverse scientific fields:

  • SPECT: Binary classification of cardiac SPECT images.
  • Biodeg: Predicting biodegradability of molecules.
  • Gamma: Classifying gamma particles from atmospheric Cherenkov telescope data.
  • CD4vsCD8: Discriminating immune system cells based on protein phosphorylation levels.
  • Bank: Predicting customer response to bank marketing campaigns.

These datasets were used to create sub-datasets of varying sample sizes (from 20 to 1500) to evaluate the protocols' performance under different data regimes.

Key Insights and Ideas

  • The "Lucky Model" Problem: Standard CV with model selection (CVM) is indeed optimistic, especially with small sample sizes. This means it tends to overestimate a model's true performance.
  • Bias Correction is Crucial: Methods that attempt to correct for this optimistic bias are essential for reliable performance estimation.
  • Computational Trade-offs: While Nested CV (NCV) is theoretically sound, its computational cost can be prohibitive. The Tibshirani-Tibshirani (TT) method offers a compelling alternative by providing similar bias correction with significantly less computational overhead.
  • Stratification Matters: Stratification of folds in CV is beneficial, as it reduces the variance of performance estimation, leading to more stable results, especially in scenarios with small or imbalanced data.

Key Results

  • CVM Overestimation: CVM consistently overestimated performance, particularly for sample sizes of 100 or less. For instance, the average bias could be over 5 AUC points for small sample sizes.
  • TT and NCV Conservatism: TT and NCV showed much less bias, often slightly underestimating performance for larger sample sizes, making them more conservative and reliable.
  • Variance: CVM had the smallest variance in bias, but this was at the cost of significant overestimation. TT and NCV exhibited similar, acceptable variances.
  • Efficiency: The TT method was found to be computationally efficient, requiring no additional model training compared to NCV.
  • Stratification Benefit: Stratified versions of the protocols generally showed smaller bias and variance compared to their non-stratified counterparts.

Limitations and Future Work

The authors acknowledge that their experiments have a limited scope:

  • Dataset Variety: The study used a specific set of datasets, and future work could explore a wider range of data types and problem complexities.
  • Analysis Steps: The focus was on hyper-parameter optimization. Future research could incorporate other data analysis steps like variable selection within the protocols.
  • Hyper-parameter Optimization Strategies: The paper used a fixed set of hyper-parameter combinations. More dynamic or adaptive optimization strategies could be investigated.
  • Number of Folds (K): The study used K=10 for CVM, TT, and NCV, and K=9 for the inner loop of NCV. Exploring the impact of different K values is a potential avenue.
  • Performance Metrics: While AUC was used, other metrics could be explored.

The authors suggest that while TT appears to be a strong candidate, more research is needed to fully understand its behavior across all scenarios and to explore alternative approaches like model averaging. They also highlight the concerning issue of large variance in estimation for small sample sizes and advocate for methods that balance bias and variance.

Summary updated

Abstract

In a typical supervised data analysis task, one needs to perform the following two tasks: (a) select the best combination of learning methods (e.g., for variable selection and classifier) and tune their hyper-parameters (e.g., K in K-NN), also called model selection, and (b) provide an estimate of the performance of the final, reported model. Combining the two tasks is not trivial because when one selects the set of hyper-parameters that seem to provide the best estimated performance, this estimation is optimistic (biased / overfitted) due to performing multiple statistical comparisons. In this paper, we confirm that the simple Cross-Validation with model selection is indeed optimistic (overestimates) in small sample scenarios. In comparison the Nested Cross Validation and the method by Tibshirani and Tibshirani provide conservative estimations, with the later protocol being more computationally efficient. The role of stratification of samples is examined and it is shown that stratification is beneficial.
BibTeX
@article{tsamardinos2015performance,
  author = {Ioannis Tsamardinos and Amin Rakhshani and Vincenzo Lagani},
  title = {{Performance-Estimation Properties of Cross-Validation-Based Protocols with Simultaneous Hyper-Parameter Optimization}},
  journal = {Int. J. Artif. Intell. Tools},
  year = {2015},
  doi = {10.1142/s0218213015400230},
}
Figure