I've been using the $K$-fold cross-validation a few times now to evaluate performance of some learning algorithms, but I've always been puzzled as to how I should choose the value of $K$.

I've often seen and used a value of $K = 10$, but this seems totally arbitrary to me, and I now just use $10$ by habit instead of thinking it over. To me it seems that you're getting a better granularity as you improve the value of $K$, so ideally you should make your $K$ very large, but there is also a risk to be biased.

I'd like to know what the value of $K$ should depend on, and how I should be thinking about this when I evaluate my algorithm. Does it change something if I use the stratified version of the cross-validation or not?

up vote 62 down vote accepted

The choice of $k = 10$ is somewhat arbitrary. Here's how I decide $k$:

  • first of all, in order to lower the variance of the CV result, you can and should repeat/iterate the CV with new random splits.
    This makes the argument of high $k$ => more computation time largely irrelevant, as you anyways want to calculate many models. I tend to think mainly of the total number of models calculated (in analogy to bootstrapping). So I may decide for 100 x 10-fold CV or 200 x 5-fold CV.

  • @ogrisel already explained that usually large $k$ mean less (pessimistic) bias. (Some exceptions are known particularly for $k = n$, i.e. leave-one-out).

  • If possible, I use a $k$ that is a divisor of the sample size, or the size of the groups in the sample that should be stratified.

  • Too large $k$ mean that only a low number of sample combinations is possible, thus limiting the number of iterations that are different.

    • For leave-one-out: $\binom{n}{1} = n = k$ different model/test sample combinations are possible. Iterations don't make sense at all.
    • E.g. $n = 20$ and $k = 10$: $\binom{n=20}{2} = 190 = 19 ⋅ k$ different model/test sample combinations exist. You may consider going through all possible combinations here as 19 iterations of $k$-fold CV or a total of 190 models is not very much.
  • These thoughts have more weight with small sample sizes. With more samples available $k$ doesn't matter very much. The possible number of combinations soon becomes large enough so the (say) 100 iterations of 10-fold CV do not run a great risk of being duplicates. Also, more training samples usually means that you are at a flatter part of the learning curve, so the difference between the surrogate models and the "real" model trained on all $n$ samples becomes negligible.

  • 4
    (+1) for the elaboration, but (-1) for the repetition counts of the CV. It is true, that the risk of creating exact duplicats (looking at the ids of the observations) is small (given enough data etc.), but the risk of creating pattern/ data structure duplicates is very high. I would not repeat a CV more than 10 times, no matter what k is ... just to avoid underestimation of the variance. – steffen May 4 '12 at 11:31
  • 3
    @steffen, isn't that what ogrisel already pointed out: that the (surrogate) models are not really independent? I completely agree that this is the case. Actually, I try to take this into account by interpreting the results in terms of stability of the (surrogate) models wrt. exchanging "a few" samples (which I didn't want to elaborate here - but see e.g. stats.stackexchange.com/a/26548/4598). And I do not calculate standard error but rather report e.g. median and $5^{th}$ to $95^{th}$ percentile of the observed errors over the iterations. I'll post a separate question about that. – cbeleites May 4 '12 at 12:35
  • 2
    I see. I agree that the approach is valid to estimate the stability of the surrogate. What I had back in mind was the follow-up-statistical test to decide whether one model outperforms another one. Repeating a cv way too often increases the chance of an alpha error unpredictably. So I was confusing the inner with the outer validation (as dikran has put it here). – steffen May 4 '12 at 15:45
  • 2
    @cbeleites: I agree with you. Variance due to limited sample size usually dominates over model uncertainty. – jpcgandre Sep 12 '14 at 10:34
  • 2
    @jpcgandre: At least for classification errors such as sensitivity, specificity etc., uncertainty due to total number of tested cases can be calculated. While it is true that this is only part of the total variance, at least in the situations I encounter in my work, this uncertainty is often so large that even a rough guesstimate is enough to make clear that conclusions are severely limited. And this limitation stays, it won't go away by using 50x 8-folds or 80x 5-folds instead of 40x 10-fold cross validation. – cbeleites Sep 14 '14 at 14:22

Larger K means less bias towards overestimating the true expected error (as training folds will be closer to the total dataset) but higher variance and higher running time (as you are getting closer to the limit case: Leave-One-Out CV).

If the slope of the learning curve is flat enough at training_size = 90% of total dataset, then the bias can be ignored and K=10 is reasonable.

Also higher K give you more samples to estimate a more accurate confidence interval on you estimate (using either parametric standard error assuming normality of the distribution of the CV test errors or non parametric bootstrap CI that just make the i.i.d assumption which is actually not very true as CV folds are not independent from one another).

Edit: underestimating => overestimating the true expected error

Edit: the part of this reply about higher variances for large K or LOOCV is probably wrong (not always true). More details with simulations in this answer: Bias and variance in leave-one-out vs K-fold cross validation (thanks Xavier Bourret Sicotte for this work).

  • 1
    can you explain a bit more about the higher variance with large $k$? As a first approximation I'd have said that the total variance of CV result (= some kind of error calculated from all $n$ samples tested by any of the $k$ surrogate models) = variance due to testing $n$ samples only + variance due to differences between the $k$ models (instability). What am I missing? – cbeleites May 4 '12 at 5:29
  • 5
    By variance I mean variance of the estimated expected test error obtained by taking the median or mean of the CV fold errors w.r.t. the "true distribution", not across CV folds. When k is big your are closer to LOO-CV which is very dependent on the particular training set you have at hand: if the number of samples is small it can be not so representative of the true distribution hence the variance. When k is big, k-fold CV can simulate such arbitrary hard samples of the training set. – ogrisel May 4 '12 at 7:10
  • 8
    As an addition: Kohavi studies the bias-variance-tradeoff in validation in chapter 3 of his Phd thesis. I highly recommend it. – steffen May 4 '12 at 15:49
  • 3
    +1, btw "larger K means higher variance", as I understand it, with large $K$, all the $K$ training sets will have large data in common, so the trained $K$ models will be somewhat correlated, resulting in $K$ correlated test errors, so the mean of the test error will have higher variance, right? – avocado May 24 '14 at 10:41
  • Yes I think this is a correct intuition. – ogrisel Sep 20 '16 at 18:51

I don't know how K affects accuracy and generalization, and this may depend on the learning algorithm, but it definitely affects the computational complexity almost linearly (asymptotically, linearly) for training algorithms with algorithmic complexity linear in the number of training instances. The computational time for training increases K-1 times if the training time is linear in the number of training instances. So for small training sets I'd consider the accuracy and generalization aspects, especially given that we need to get the most out of a limited number of training instances.

However, for large training sets and learning algorithms with high asymptotical comutational complexity growth in the number of training instances (at least linear), I just select K=2 so that there is no increase in computational time for a training algorithm with asymptotic complexity linear in the number of training instances.

Solution:

K = N/N*0.30
  • N = Size of data set
  • K = Fold

Comment: We can also choose 20% instead of 30%, depending on size you want to choose as your test set.

Example:

If data set size: N=1500; K=1500/1500*0.30 = 3.33; We can choose K value as 3 or 4

Note:

Large K value in leave one out cross-validation would result in over-fitting. Small K value in leave one out cross-validation would result in under-fitting.

Approach might be naive, but would be still better than choosing k=10 for data set of different sizes.

  • 2
    (-1) $\frac{N}{N \cdot 0.3} = \frac{1}{0.3} \approx 3.33 = const.$ so you are suggesting always to use k = 3 or 4 regardless of sample size - this is IMHO not substantially different from using k = 10 equally regardless of sample size. – cbeleites May 28 '17 at 10:44
  • K=N/N*0.3=10/3 which is a constant. So it is not logical to use that value for every condition. – Kamal Thapa Jul 20 '17 at 6:55

protected by kjetil b halvorsen Aug 23 '17 at 9:57

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.