K-fold vs. Monte Carlo cross-validation

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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

• (1) Remesan, Renji, and Jimson Mathew. Hydrological Data Driven Modelling: A Case Study Approach. Vol. 1. Springer, 2014.

• (2) Dubitzky, Werner, Martin Granzow, and Daniel P. Berrar, eds. Fundamentals of data mining in genomics and proteomics. Springer Science & Business Media, 2007.

Answer 4

What about in practice?

In certain situations (smaller data), I combine both Monte Carlo and K-Fold CV, into repeated, nested cross-validation:

1. Inner K-fold CV for hyperparameter selection
2. Outer K-fold CV for estimating generalization performance
3. Now, repeat steps 1 and 2 many times (Monte Carlo).

If for 2. you use K=5, and then repeat it 100 times in step 3, you will have 5*100 = 500 estimates of generalization performance.

This is available in scikit-learn as Repeated (stratified) K-fold cross-validation: scikit-learn docs. Also see nested vs non-nested cross-validation: scikit-learn docs

Answer 5

k-fold CV trains on more data than are held out for validation; this is a problem. MCCV has great potential to correct this error; for details, see below, but the validation set should always be at least as big as the training set, and not the other way around.

According to Jun Shao's seminal 1993 paper, "Linear Model Selection by Cross-Validation," which appeared in Volume 88, Issue 422 of the the Journal of the American Statistical Association, Monte Carlo Cross-Validation (MCCV) would optimally have at least the same number $b$ of folds as points $n$ in the overall data set for training and testing (paper simulations use $b = 2n$ repeated a thousand times with empirical probability of selecting a known "true" model reported in the last section of the paper).

In Shao's simulations, the size of each training set, whether for LOOCV or MCCV (also included an approximate Balanced Incomplete Block Design or BIBD) was $n_c \approx \sqrt[4]{n^3}$; i.e., the integer part of the fraction (after truncating). For example, with an overall set of $n = 10,000$ data points, each training set would be of size $n_c = 1,000 = \sqrt[4]{10,000^3}$. Additionally, the $n_c$ training exemplars for each of the $b \geq n $ folds for MCCV were randomly drawn without even stratifying by class, and without regard to whether the draws were with or without replacement.

For $k$-fold cross-validation, on the other hand, one arbitrarily determines the number $k$ of folds before starting, as well as the sizes of each training ($n_c$) and testing ($n - n_c$) partition. One does not draw randomly, but in the order of data appearance within the data frame/matrix (although it could be shuffled once before choosing the folds). If the number $n = k \cdot n_c$ of data points is odd, one might be arbitrarily forced to select an odd number $k$ of folds in order to strictly make each training set the same size $n_c = n/k$.