Compendium of cross-validation techniques

Question

I'm wondering if anybody knows of a compendium of cross-validation techniques with a discussion of the differences between them and a guide on when to use each of them. Wikipedia has a list of the most common techniques, but I'm curious if there are other techniques, and if there are any taxonomies for them.

For example, I just run into a library that allows me to choose one of the following strategies:

• Hold out
• Bootstrap
• K Cross-validation
• Leave one out
• Stratified Cross Validation
• Balanced Stratified Cross Validation
• Stratified Hold out
• Stratified Bootstrap

and I am trying to understand what stratified and balanced mean in bootstrapping, hold out or CV.

We can also turn this post into a community wiki if people want ,and collect a discussion of techniques or taxonomies here.

Answer 1

You can add to that list:

• Repeated-cross validation
• Leave-group-out cross-validation
• Out-of-bag (for random forests and other bagged models)
• The 632+ bootstrap

I don't really have a lot of advice as far as how to use these techniques or when to use them. You can use the caret package in R to compare CV, Boot, Boot632, leave-one-out, leave-group-out, and out-of-bag cross-validation.

In general, I usually use the boostrap because it is less computationally intensive than repeated k-fold CV, or leave-one-out CV. Boot632 is my algorithm of choice because it doesn't require much more computation than the bootstrap, and has show to be better than cross-validation or the basic bootstap in certain situations.

I almost always use out-of-bag error estimates for random forests, rather than cross-validation. Out-of-bag errors are generally unbiased, and random forests take long enough to compute as it is.

Answer 2

K-fold cross-validation (CV) randomly breaks your data up into K partitions, and you in turn hold out one of those K parts as a test case, and lump the other K-1 parts together as your training data. Leave One Out (LOO) is the special case where you take your N data items and do N-fold CV. In some sense, Hold Out is another special case, where you only choose one of your K folds as test and do not rotate through all K folds.

As far as I know, 10-fold CV is pretty much the de rigueur, since it uses your data efficiently and also helps to avoid unlucky partition choices. Hold Out does not make efficient use of your data, and LOO is not as robust (or something like that), but 10-ish-fold is just right.

If you know that your data contains more than one category, and one or more categories are much smaller than the rest, some of your K random partitions might not even contain any of the small categories at all, which would be bad. To make sure each partition is reasonably representative, you use stratification: break your data up into the categories and then create random partitions by choosing randomly and proportionally from each category.

All of these variations on K-fold CV choose from your data without replacement. The bootstrap chooses data with replacement, so the same datum can be included multiple times and some data might not be included at all. (Each "partition" will also have N items, unlike K-fold, in which each partition will have N/K items.)

(I'll have to admit that I don't know exactly how the bootstrap would be used in CV, though. The principle of testing and CV is to make sure you don't test on data that you trained on, so you get a more realistic idea of how your technique + coefficients might work in the real world.)

EDIT: Replaced "Hold Out is not efficient" with "Hold Out does not make efficient use of your data" to help clarify, per the comments.

Answer 3

I found one of the references linked to in the Wikipedia article quite useful

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.529&rep=rep1&type=pdf

"A study of cross-validation and bootstrap for accuracy estimation and model selection", Ron Kohavi, IJCAI95

It contains an empirical comparison for a subset of CV techniques. The tl;dr version is basically "use 10-fold CV".

Answer 4

...and a guide on when to use each of them...

Unfortunately that problem is harder than it gets credit for. There are at least 2 main uses of cross-validation: selecting a model, and evaluating model performance.

Roughly speaking, if you use a CV variant which splits the data using a high train-to-test ratio, this can be better for evaluation. Using a larger training set will more accurately mimic the performance of the model fit on the full dataset.

But a high train-to-test ratio can be worse for selection. Imagine there really is a "best" model that you "ought" to choose, but your dataset is quite large. Then, too-large models which overfit slightly will have almost the same CV performance as the "best" model (because you'll successfully estimate their spurious parameters to be negligible). Randomness in the data and the CV/splitting procedure will often cause you to choose an overfitting model instead of the truly "best" model.

See Shao (1993), "Linear Model Selection by Cross-Validation" for older asymptotic theory in the linear regression case. Yang (2007), "Consistency of Cross Validation for Comparing Regression Procedures" and Yang (2006), "Comparing Learning Methods for Classification" give asymptotic theory for more general regression and classification problems. But rigorous finite-sample advice is hard to come by.