How to evaluate/select cross validation method?

Question

How can I decide which cross validation method is appropriate for my problem and data type? For instance, choosing among leave-one-out, or K-fold (and which K is appropriate?). Most of my searches end up on selection of model rather than selection of cross validation method.

Answer 1

There have been a bunch of similar questions, please browse through the threads on [cross-validation], e.g. Cross-validation or bootstrapping to evaluate classification performance?

Here's the gist:

• You need to worry only if you are in a small sample size situation. For estimating proportions (like accuracy), I'd say anything that leads to a denominator of the proportion < 100 - 300 independent cases (depending on the precision you need) is small. For the model itself, it also depends on how difficult the problem is, but a sample size that will give a decent estimate of the performace often allows to train a decent model as well.

• Choosing among iterated/repeated $k$-fold cross validation, out-of-bootstrap and iterated/repeated set validation from my personal experience is largely a matter of taste in practice.

• The important thing is to calculate enough surrogate models, so you can have a good estimate of model instability. How many you need will depend on your data and the model (complexity).

• Leave-one-out, however, I can not recommend as it neither allows to measure model stability, nor to reduce the variance uncertainty on the validation result caused by model instability. In addition, there are situations where it is subject to a large pessimistic bias (as opposed to the minimal pessimistic bias that is expected).

• The PhD thesis of Ron Kohavi, "Wrappers for Performance Enhancement and Oblivious Decision Graphs" contains an excellent discussion.

• Also have a look at the work of Dougherty and Braga-Neto, e.g.
  Dougherty, E. R. et al.: Performance of Error Estimators for Classification Current Bioinformatics, 2010, 5, 53-67

• Statisticians like the bootstrap (resampling with replacement) as from a theory point of view it has nicer properties than cross validation (resampling without replacement). That may mean that you'd need to do more iterations with cross validation (more precisely: calculate more surrogate models) than with the bootstrap.

• There is useful information, however, that is easier to be gotten from iterated cross validation, e.g. model stability expressed as stability of the predictions.
  Beleites, C. & Salzer, R.: Assessing and improving the stability of chemometric models in small sample size situations, Anal Bioanal Chem, 390, 1261-1271 (2008). DOI: 10.1007/s00216-007-1818-6

• For my type of data (spectroscopic data, wide matrices), we found similar overall performance for out-of-bootstrap and iterated $k$-fold cross validation with equal numbers of surrogate models. .632-bootstrap was overoptimistic, as the models easily overfit.
  Beleites, C.; Baumgartner, R.; Bowman, C.; Somorjai, R.; Steiner, G.; Salzer, R. & Sowa, M. G. Variance reduction in estimating classification error using sparse datasets, Chemom Intell Lab Syst, 79, 91 - 100 (2005).

• Kim, J.-H. Estimating classification error rate: Repeated cross-validation, repeated hold-out and bootstrap , Computational Statistics & Data Analysis , 53, 3735 - 3745 (2009). DOI: 10.1016/j.csda.2009.04.009 report similar findings.

---

update: The papers deal with classifier validation. Validation of regression models tends to be easier in that in my experience it is easier there to get stable models (= less variance due to model instability), and also the variance due to the finite test sample size tends to be less problematic.

---

I forgot to link
Esbensen, K. H. & Geladi, P.: Principles of Proper Validation: use and abuse of re-sampling for validation, J Chemom, 24, 168-187 (2010). DOI: 10.1002/cem.1310
which discusses important limits of resampling validation, namely, that it cannot be used to measure error caused by (instrumental) drift.

---

update: @alfa asks about

• time-complexity: time complexity is linear with the number of surrogate models. As the bootstrap is said to be somewhat more efficient (i.e. fewer iterations needed than for cross validation), so it may have a slight edge here. I don't think this matters in practice (at least for my data, as the variance uncertainty due to having few test cases only is the limiting factor for my applications).

For linear models, leave-one-out estimators can be calculated using the "hat matrix". This means that the LOO estimator can be computed without refitting $n$ surrogate models from the fit of all data points. Approximations to this are knows for some more models. BUT a) this is possible only if each row in the data set is an independent case, and b) the problems that you cannot iterate/repeat and thus cannot check model stability and reduce the impact of the associated variance is not solved by that approach.

• choice of $k$: Choice of K in K-fold cross-validation

Answer 2

If you have few samples one of the approaches you can do is leave-one-out. Definitely, you would need to combine it with some sort of resampling technique like bootstrap or jackknife, in order to have a sense of the stability of the results.

If you have enough data then you can go for K-fold. The K depends on the stability of the results. If results are stable across the K-folds you are fine. The problems begin when you don't have enough data for training each of the K-folds, or there is too much noise etc.

If you have a LOT of samples you can simply split on training set by some proportion (e.g. 70/30%). Then it is a matter of choosing wisely the way to split (e.g. randomly with respect to timestamps if that's the case, etc). In practice it may be hard to train e.g. 5 times when each training can take some days.

That said, in all cases, if you want to do a proper evaluation you should make three splits, i.e. training/validation/test.