183
$\begingroup$

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?

Improve this question
$\endgroup$
1

4 Answers 4

Reset to default
100
$\begingroup$

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.

Improve this answer
$\endgroup$
15
  • 8
    $\begingroup$ (+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. $\endgroup$
    – steffen
    Commented May 4, 2012 at 11:31
  • 3
    $\begingroup$ @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. $\endgroup$
    – cbeleites
    Commented May 4, 2012 at 12:35
  • 2
    $\begingroup$ 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). $\endgroup$
    – steffen
    Commented May 4, 2012 at 15:45
  • 3
    $\begingroup$ @cbeleites: I agree with you. Variance due to limited sample size usually dominates over model uncertainty. $\endgroup$
    – jpcgandre
    Commented Sep 12, 2014 at 10:34
  • 2
    $\begingroup$ @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. $\endgroup$
    – cbeleites
    Commented Sep 14, 2014 at 14:22
46
$\begingroup$

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

Improve this answer
$\endgroup$
11
  • 1
    $\begingroup$ 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? $\endgroup$
    – cbeleites
    Commented May 4, 2012 at 5:29
  • 7
    $\begingroup$ 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. $\endgroup$
    – ogrisel
    Commented May 4, 2012 at 7:10
  • 8
    $\begingroup$ As an addition: Kohavi studies the bias-variance-tradeoff in validation in chapter 3 of his Phd thesis. I highly recommend it. $\endgroup$
    – steffen
    Commented May 4, 2012 at 15:49
  • 3
    $\begingroup$ +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? $\endgroup$
    – avocado
    Commented May 24, 2014 at 10:41
  • 1
    $\begingroup$ @digits This is incorrect. If k equals the number of examples in the dataset, k-fold CV becomes leave-one-out CV, so the training datasets in each fold will be nearly identical to the full dataset (but less one sample). $\endgroup$
    – rinspy
    Commented Aug 22, 2017 at 14:43
0
$\begingroup$

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.

Improve this answer
$\endgroup$
-7
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 6
    $\begingroup$ (-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. $\endgroup$
    – cbeleites
    Commented May 28, 2017 at 10:44
  • $\begingroup$ K=N/N*0.3=10/3 which is a constant. So it is not logical to use that value for every condition. $\endgroup$
    – Kamal Thapa
    Commented Jul 20, 2017 at 6:55
  • 2
    $\begingroup$ This is, quite literally, one of the dumbest answers I have ever seen on this forum $\endgroup$
    – bob
    Commented Apr 28, 2022 at 5:10

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