# K-fold vs. Monte Carlo cross-validation

I am trying to learn various cross validation methods, primarily with intention to apply to supervised multivariate analysis techniques. Two I have come across are K-fold and Monte Carlo cross-validation techniques. I have read that K-fold is a variation on Monte Carlo but I'm not sure I fully understand what makes up the definition of Monte Carlo. Could someone please explain the distinction between these two methods?

-
So would I be correct to say that Monte Carlo is random sizes of the training and test sets while k-fold is a defined size of sets? I have seen the above page but didn't quite grasp what the difference was. – Liam Mar 6 '13 at 16:02
I'm familiar with different types of cross validation and out-of-bootstrap validation, but have not yet come across the term Monte Carlo cross validation (I may know it under some other name). Could you link or quote a description of how Monte Carlo cross validation works? – cbeleites Mar 15 '13 at 12:48
The simplest and open access description of Monte Carlo is on wiki. I just don't seem to see the distinction between k-fold and Monte Carlo methods. – Liam Mar 25 '13 at 15:51

## $k$-Fold Cross Validation

Suppose you have 100 data points. For $k$-fold cross validation, these 100 points are divided into $k$ equal sized and mutually-exclusive 'folds'. For $k$=10, you might assign points 1-10 to fold #1, 11-20 to fold #2, and so on, finishing by assigning points 91-100 to fold #10. Next, we select one fold to act as the test set, and use the remaining $k-1$ folds to form the training data. For the first run, you might use points 1-10 as the test set and 11-100 as the training set. The next run would then use points 11-20 as the test set and train on points 1-10 plus 21-100, and so forth, until each fold is used once as the test set.

## Monte-Carlo Cross Validation

Monte Carlo works somewhat differently. You randomly select (without replacement) some fraction of your data to form the training set, and then assign the rest of the points to the test set. This process is then repeated multiple times, generating (at random) new training and test partitions each time. For example, suppose you chose to use 10% of your data as test data. Then your test set on rep #1 might be points 64, 90, 63, 42, 65, 49, 10, 64, 96, and 48. On the next run, your test set might be 90, 60, 23, 67, 16, 78, 42, 17, 73, and 26. Since the partitions are done independently for each run, the same point can appear in the test set multiple times, which is the major difference between Monte Carlo and cross validation.

## Comparison

Each method has its own advantages and disadvantages. Under cross validation, each point gets tested exactly once, which seems fair. However, cross-validation only explores a few of the possible ways that your data could have been partitioned. Monte Carlo lets you explore somewhat more possible partitions, though you're unlikely to get all of them--there are $\binom{100}{50} \approx 10^{28}$ possible ways to 50/50 split a 100 data point set(!).

If you're attempting to do inference (i.e., statistically compare two algorithms), averaging the results of a $k$-fold cross validation run gets you a (nearly) unbiased estimate of the algorithm's performance, but with high variance (as you'd expect from having only 5 or 10 data points). Since you can, in principle, run it for as long as you want/can afford, Monte Carlo cross validation can give you a less variable, but more biased estimate.

Some approaches fuse the two, as in the 5x2 cross validation (see Dietterich (1998) for the idea, though I think there have been some further improvements since then), or by correcting for the bias (e.g., Nadeau and Bengio, 2003).

-
Someone asked, via the suggested edits queue, whether Monte Carlo is performed with or without replacement. For each Monte Carlo run, the training and test set are drawn without replacement (i.e., each point is assigned, exactly once, to either the train or test set). However, the runs are done independently, so a given example can show up in the same set multiple times; this is the major difference between Monte Carlo and k-fold cross validation! – Matt Krause Dec 3 '14 at 18:37

Let's assume $N$ is the size of the dataset, $k$ is the number of the $k$-fold subsets , $n_t$ is the size of the training set and $n_v$ is the size of the validation set. Therefore, $N = k \times n_v$ for $k$-fold cross-validation and $N = n_t + n_v$ for Monte Carlo cross-validation.

$k$-fold cross-validation (kFCV) divides the $N$ data points into $k$ mutually exclusive subsets of equal size. The process then leaves out one of the $k$ subsets as a validation set and trains on the remaining subsets. This process is repeated $k$ times, leaving out one of the $k$ subsets each time. The size of $k$ can range from $N$ to $2$ ($k = N$ is called leave-one-out cross validation). The authors in [2] suggest setting $k = 5$ or $10$.

Monte Carlo cross-validation (MCCV) simply splits the $N$ data points into the two subsets $n_t$ and $n_v$ by sampling, without replacement, $n_t$ data points. The model is then trained on subset $n_t$ and validated on subset $n_v$.There exist ${N\choose n_t}$ unique training sets, but MCCV avoids the need to run this many iterations. Zhang [3] shows that running MCCV for $N^2$ iterations has results close to cross validation over all ${N\choose n_t}$ unique training sets. It should be noted that the literature lacks research for large N.

The choice of $k$ and $n_t$ affects the bias/variance trade off. The larger $k$ or $n_t$, the lower the bias and the higher the variance. Larger training sets are more similar between iterations, hence over fitting to the training data. See [2] for more on this discussion. The bias and variance of kFCV and MCCV are different, but the bias of the two methods can be made equal by choosing appropriate levels of $k$ and $n_t$. The values of the bias and variance for both methods are shown in [1] (this paper refers to MCCV as repeated-learning testing-model).

[1] Burman, P. (1989). A Comparative study of ordinary cross-validation, $v$-fold cross validation and the repeated learing testing-model methods. Bometrika 76 503-514.

[2] Hastie, T., Tibshirani, R. and Friedman, J. (2011). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Second ed. New York: Springer.

[3] Zhang, P. (1993). Model Selection Via Muiltfold Cross Validation. Ann. Stat. 21 299–313

-

The other two answers are great, I'll just add a two pictures as well as one synonym.

K-fold cross-validation (kFCV):

Monte Carlo cross-validation (MCCV) = Repeated random sub-sampling validation (RRSSV):

References:

The pictures come from (1) (pages 64 and 65), and the synonym is mentioned in (1) and (2).

-