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.
2 Answers
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-67Statisticians 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-6For 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
-
$\begingroup$ Thanks for the many references. Are conclusions regarding cross validation and bootstrap for classification generalizable to PCR, PLSR model evaluation? $\endgroup$ Jan 12, 2014 at 15:08
-
1$\begingroup$ @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. $\endgroup$ Jan 12, 2014 at 15:46
-
$\begingroup$ 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. $\endgroup$– alfaJan 13, 2014 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.
-
1$\begingroup$ Is this based on some research, or from your practical experience, or from a machine learning professor in a training course? $\endgroup$ Jan 12, 2014 at 11:25
-
$\begingroup$ 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. $\endgroup$– iliasflJan 12, 2014 at 11:37
-
$\begingroup$ 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). $\endgroup$ Jan 12, 2014 at 12:07
-
1$\begingroup$ 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... $\endgroup$– iliasflJan 12, 2014 at 12:31
-
$\begingroup$ @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. $\endgroup$ Jan 12, 2014 at 13:06