How do I know which method of cross validation is best?

Question

I am trying to figure out which cross validation method is best for my situation.

The following data are just an example for working through the issue (in R), but my real X data (xmat) are correlated with each other and correlated to different degrees with the y variable (ymat). I provided R code, but my question is not about R but rather about the methods. Xmat includes X variables V1 to V100 while ymat includes a single y variable.

set.seed(1233)
xmat           <- matrix(sample(-1:1, 20000, replace = TRUE), ncol = 100)
colnames(xmat) <- paste("V", 1:100, sep ="")
rownames(xmat) <- paste("S", 1:200, sep ="")
  # the real y data are correlated with xmat
ymat           <- matrix(rnorm(200, 70,20), ncol = 1)
rownames(ymat) <- paste("S", 1:200, sep="")

I would like to build a model for predicting y based on all the variables in xmat. So it will be a linear regression model y ~ V1 + V2 + V3+ ... + V100. From a review, I can see the following three cross validation methods:

1. Split data in about half and use one for training and another half for testing (cross validation):

   prop       <- 0.5 # proportion of subset data
   set.seed(1234)
     # training data set 
   training.s <- sample (1:nrow(xmat), round(prop*nrow(xmat),0))
   xmat.train <- xmat[training.s,]
   ymat.train <- ymat[training.s,]
   
     # testing data set 
   testing.s <- setdiff(1:nrow(xmat), training)
   xmat.test <- xmat[testing.s,]
   ymat.test <- ymat[testing.s,]
   

2. K-fold cross validation - using 10 fold cross validation:

   mydata <- data.frame(ymat, xmat)
   fit    <- lm(ymat ~ ., data=mydata)
   library(DAAG)
   cv.lm(df=mydata, fit, m=10) # ten-fold cross validation 
   

3. Masking one value or few values at a time : In this method we randomly mask a value in dataset (y) by replacing it with NA and predict it. The process is repeated n times.

   n = 500 
   predicted.v <- rep(NA, n)
   real.v      <- rep(NA, n)
   
   for (i in 1:n){
     masked.id <- sample (1:nrow(xmat), 1)
     ymat1     <- ymat 
     real.v[i] <- ymat[masked.id,]
     ymat1[masked.id,] <- NA
     mydata            <- data.frame(ymat1, xmat)
     fit               <- lm(ymat1 ~ ., data=mydata)
     predicted.v[i]    <- fit$fitted.values[masked.id]
   }
   

How do I know which is best for any situation? Are there other methods? Bootstrap validation vs CV ? Worked examples would be appreciated.

Answer 1

Since the OP has placed a bounty on this question, it should attract some attention, and thus it is the right place to discuss some general ideas, even if it does not answer the OP directly.

First, names:

a) cross-validation is the general name for all estimation/measure techniques that use a test set different than the train set. Synonym: out-of-sample or extra-sample estimations. Antonym: in-sample estimation.

In-sample estimation are techniques that use some information on the training set to estimate the model quality (not necessarily error). This is very common if the model has a high bias – that is – it makes strong assumptions about the data. In linear models (a high bias model), as the in the example of the question, one uses R-squared, AIC, BIC, deviance, as a measure of model quality – all these are in-sample estimators. In SVM, for example, the ratio data in the support vector to the number of data is an in-sample estimation of error of the model.

There are many cross validation techniques:

b) hold-out is the the method #1 above. Split the set into a training and one test. There is a long history of discussion and practices on the relative sizes of the training and test set.

c) k-fold – method #2 above. Pretty standard.

d) Leave-one-out – method #3 above.

e) bootstrap: if your set has N data, randomly select N samples WITH REPLACEMENT from the set and use it as training. The data from the original set that has not been samples any time is used as the test set. There are different ways to compute the final estimation of the error of the model which uses both the error for the test set (out-of-sample) and the error for the train set (in-sample). See for example, the .632 bootstrap. I think there is also a .632+ formula – they are formulas that estimate the true error of the model using both out-of-sample and in-sample errors.

f) Orthogonal to the selection of the method above is the issue of repetition. Except for leave-one-out, all methods above can be repeated any number of times. In fact one can talk about REPEATED hold-out, or REPEATED k-fold. To be fair, almost always the bootstrap method is used in a repeated fashion.

---

The next question is, which method is "better". The problem is what "better" means.

1) The first answer is whether each of these methods is biased for the estimation of the model error (for an infinite amount of future data).

2) The second alternative is how fast or how well each of these methods converge to the true model error (if they are not biased). I believe this is still a topic of research. Let me point to these two papers (behind pay-wall) but the abstract gives us some understanding of what they are trying to accomplish. Also notice that it is very common to call k-fold as "cross-validation" by itself.

• Measuring the prediction error. A comparison of cross-validation, bootstrap and covariance penalty methods

• Estimating classification error rate: Repeated cross-validation, repeated hold-out and bootstrap

There are probably many other papers on these topics. Those are just some examples.

3) Another aspect of "better" is: given a particular measure of the model error using one of the techniques above, how certain can you be that the correct model error is close.

In general, in this case you want to take many measures of the error and calculate a confidence interval (or a credible interval if you follow a Bayesian approach). In this case, the issue is how much can you trust the variance of the set of error measures. Notice that except for the leave-one-out, all techniques above will give you many different measures (k measures for a k-fold, n measures for a n-repeated hold out) and thus you can measure the variance (or standard deviation) of this set and calculate a confidence interval for the measure of error.

Here things get somewhat complicated. From what I understand from the paper No unbiased estimator of the variance of k-fold cross-validation (not behind paywall), one cannot trust the variance you get from a k-fold – so one cannot construct a good confidence interval from k-folds. Also from what I understand from the paper Approximate Statistical Tests for Comparing Supervised Classification Learning Algorithms (not behind paywall), techniques that use repeated measures (repeated k-fold, repeated hold-out – not sure about bootstrap) will sub-estimate the true variance of the error measure (it is somewhat easy to see that – since you are sampling from a finite set if you repeat the measure a very large number of times, the same values will keep repeating, which keep the mean the same, but reduce the variance). Thus repeated measures techniques will be too optimistic on the confidence interval.

This last paper suggest doing a 5 repeated 2-fold – which he calls 5×2 CV – as a good balance of many measures (10) but not too much repetitions.

EDIT:

Of course there are great answers in Cross Validated to some of these questions (although sometimes they do not agree among themselves). Here are some:

Cross-validation or bootstrapping to evaluate classification performance?

Differences between cross validation and bootstrapping to estimate the prediction error

Cross-validation or bootstrapping to evaluate classification performance?

Understanding bootstrapping for validation and model selection

In general, the tag cross-validation is your friend here.

---

So what is the best solution? I don't know. I have been using 5×2 CV when I need to be very rigorous, when I need to be sure that one technique is better than another, especially in publications. And I use a hold out if I am not planning to make any measure of variance or standard deviation, or if I have time constraints – there is only one model learning in a hold-out.

Answer 2

Please refer to the wikipedia page for the method definitions (they do a far better job than I could do here).

After you have had a look at that page, the following may be of help to you. Let me focus on the part of the question where one wants to pick one of these methods for their modeling process. Since this is pretty frequent choice that one makes, and they could benefit from additional knowledge, here is my answer for two situations:

1. Any situation: Use k-fold cross validation with some suitable number of repeats (say 5 or 10).

   • Splitting the data into 1 half, training on the first half and validating on the other is one step in 2-fold cross validation anyway (the other step being repeating the same exercise with the two halfs interchanged). Hence, rule out 'splitting the data into half' strategy.

   • Many machine learning and data mining papers use k-fold cross validation (don't have citation), so use it unless you have to be very careful in this step.

   • Now, leave one out method and other methods like 'leave p out' and 'random split and repeat' (essentially bootstrap like process described above) are defintely good contenders.

   • If your data size is N, then N-fold cross validation is essentially the same as leave one out.

   • 'leave p out' and 'bootstrap' are a bit more different than k fold cross validation, but the difference is essentially in how folds are defined and the number of repetitions 'k' that happen.

   • As the wiki page says, both k-fold and 'leave p out' are decent estimators of the 'expected performance/fit' (although the bets are off with regards to the variance of these estimators).

2. Your situation: You only have a sample size of 200 compared to number of features (100). I think there is a very high chance that there are multiple linear models giving the same performance. I would suggest using k-fold cross validation with > 10 repeats. Pick a k value of 3 or 5.

   • Reason for k value: generic choice.

   • Reason for repeat value: A decently high value for repetition is probably critical here because the output of a single k-fold cross validation computation may be suceptible to fold splitting variability/randomness that we introduce.

Additional thoughts:

• Maybe I would also employ 'leave p out' and 'bootstrap like random split repeat' methods (in addition to k-fold cross validation) for the same performance/fit measure to check if my k-fold cross validation method's outputs look alright.

• Although you want to use all the 100 features, as someone suggested, pay attention to multicollinearity/correlation and maybe reduce the number of features.