35
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Of possible interest: Differences between cross validation and bootstrapping to estimate the prediction error. $\endgroup$ – chl Mar 5 '13 at 23:05
  • $\begingroup$ 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. $\endgroup$ – Liam Mar 6 '13 at 16:02
  • $\begingroup$ 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? $\endgroup$ – cbeleites unhappy with SX Mar 15 '13 at 12:48
  • $\begingroup$ 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. $\endgroup$ – Liam Mar 25 '13 at 15:51
40
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ 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! $\endgroup$ – Matt Krause Dec 3 '14 at 18:37
13
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
9
$\begingroup$

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


K-fold cross-validation (kFCV):

enter image description here

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

enter image description here


References:

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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 be of size $n_c = 1,000 = \sqrt[4]{10,000^3}$. Additionally, the $n_c$ training exemplars for each of the $b$ folds in MCCV were randomly drawn, either with or without replacement (he did not state).

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. If the number $n = kn_c$ of data points is odd, one might be forced to select an odd number $k$ of folds in order to strictly make each training set the same size $n_c = n/k$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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