How to evaluate/select cross validation method?

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.

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:

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.

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.

• 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.

• Thanks for the many references. Are conclusions regarding cross validation and bootstrap for classification generalizable to PCR, PLSR model evaluation? – hatmatrix Jan 12 '14 at 15:08
• @crippledlambda: yes. They apply to all kinds of predictive models. Regression (calibration in chemistry/physics terminology) however is better behaved than classification: It is easier there to get stable models, and also the validation results tend to have less variance uncertainty. – cbeleites unhappy with SX Jan 12 '14 at 15:46
• Could you discuss the time complexity of cross-validation and bootstrapping and propose how to select an appropriate $k$ in k-fold CV? Otherwise it is good answer. – alfa Jan 13 '14 at 10:41

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.

• Is this based on some research, or from your practical experience, or from a machine learning professor in a training course? – probabilityislogic Jan 12 '14 at 11:25
• Do you refer to the 3 cases? I am sure you can find some discussion on any good book of machine learning. Check for example "Pattern Recognition" by S.Theodoridis. About the last point, a quick google search about "training, validation, test" can give you some pointers. Research results in the past which missed the validation set "suffered" a lot from overestimated performances, but the 3 split rule is quite common place now. – iliasfl Jan 12 '14 at 11:37
• Particularly in small sample size situations, leave-one-out is not recommended: it does not allow to estimate model stability, variance caused by model instability cannot be reduced by iterations, and in some situations can have a large (as opposed to minimal) pessimistic bias. Thus, particularly in small sample size itations, out-of-bootstrap or iterated $k$-fold/leave-$n$-out are more appropriate. In those situations, it is also often better to avoid hyperparameter optimization, so no inner split/ nesting of the validation is needed. However, we don't know the sample size (yet). – cbeleites unhappy with SX Jan 12 '14 at 12:07
• Agree in most part: in small sample sizes any approach will have issues, and there are trade-offs no matter which one you choose. Rarely you can avoid hyperparameter optimization, unless you assume that some kind of default parameters will work for the problem. Sample size per se, is not enough to decide best method, it depends on the problem that is how data behave, but also their dimensionality. Otherwise there would be tables like from 1 to 10 samples use method x, for 11 to 101 go for method y... – iliasfl Jan 12 '14 at 12:31
• @iliasfl: Well, we don't even know whether the application is classifiation or regression, whether there is a small sample size problem, what the dimensionality of the data is, nor anything about the application. However, for my data (I'm spectroscopist and chemometrician), I usually can include external knowledge like number of expected latent variables. And some methdods are either less sensitive about the exact parameter choice than others, and some allow to translate external knowledge into hyperparameters while others don't. Anyways, we're getting off-topic for this question. – cbeleites unhappy with SX Jan 12 '14 at 13:06