Are the results from repeatedly performing k-fold cross-validation runs comparable?

Question

I have some questions regarding $k$-fold CV. So far, I understand how $k$-fold CV works as well as what type of results we can obtain at the end of the $k$-fold iterations. However, there is an interesting question that follows when we repeatedly perform $k$-fold CV, especially linked to how the samples are split. To help visualize the problem, let's assume that I'm using a dataset of $M$ distinct samples where $M = kI, I \in \mathbb{N}$. The feature length, or the number of predictors are not important here.

The principle of $k$-fold CV, as I understand it, is to partition the dataset into $k$ (roughly) equal-sized subsets, compose a test set using one of the available $k$ subsets and utilize the remaining $k-1$ subsets as a training set. The predictive model is obtained by training a learning machine using the training set and test this tuned predictive model on the test set in order to obtain some measure of generalization performance.

What is not mentioned, however, is that the $k$ subsets are non-overlapping. Now, assume that I repeatedly perform $k$-fold CV for $N$ runs. If I take the same $k$ subsets everytime, then I expect to obtain exactly the same result for each repeated run. However, since the samples are distinct (i.e. no two samples are equal), it is possible to group them into $k$ different non-overlapping subsets for each run.

To illustrate, let's assume $M = 10$ and $k = 5$ ($5$-fold CV). Consider a binary-valued vector $\mathbf{v}_{test}$ that basically selects the samples to be used as the test set. The most trivial ones would be

$$ \mathbf{v}_{test1} = [1 1 0 0 0 0 0 0 0 0]^{\mathrm{T}}\\ \mathbf{v}_{test2} = [0 0 1 1 0 0 0 0 0 0]^{\mathrm{T}}\\ \mathbf{v}_{test3} = [0 0 0 0 1 1 0 0 0 0]^{\mathrm{T}}\\ \mathbf{v}_{test4} = [0 0 0 0 0 0 1 1 0 0]^{\mathrm{T}}\\ \mathbf{v}_{test5} = [0 0 0 0 0 0 0 0 1 1]^{\mathrm{T}} $$

Suppose that we use the trivial way of splitting, as shown above, for run $n=1$. We get a performance figure $F_{1}$. Now we consider the following vectors

$$ \mathbf{v}_{test1} = [0 1 0 1 0 0 0 0 0 0]^{\mathrm{T}}\\ \mathbf{v}_{test2} = [0 0 1 0 1 0 0 0 0 0]^{\mathrm{T}}\\ \mathbf{v}_{test3} = [0 0 0 0 0 1 0 1 0 0]^{\mathrm{T}}\\ \mathbf{v}_{test4} = [0 0 0 0 0 0 1 0 1 0]^{\mathrm{T}}\\ \mathbf{v}_{test5} = [1 0 0 0 0 0 0 0 0 1]^{\mathrm{T}} $$

Performing the same maneuvers, we obtain $F_{2}$ for the next run, which in theory should be different from $F_{1}$.

Now, for each run, it is clear that no one sample belongs to two or more subsets. But when comparing between runs, we see that the subsets are clearly overlapping (ex. $\mathbf{v}_{test1}$ in run $n=1$ shares one similar sample with $\mathbf{v}_{test5}$ in run $n=2$)

So my questions are:

$\mathbf{Q1}$: Are the two figures $F_{1}$ and $F_{2}$ comparable despite this overlap?

$\mathbf{Q2}$: Can a summary statistics be computed on the ensemble of $F_{n}$'s (in particular, the mean)?

$\mathbf{Q3}$: Would there be a problem with the summary statistics if we authorized an insignificant number of sample overlaps (say less than $10\%$ of the samples are similar in the test sets of runs $n$ and $n+1$)?

Thanks,

Answer 1

Ideally, i.e. if your training is stable, predictions for the same case of all runs should be the same, and in consequence so should be the performance measures.

So yes, you can sensibly calculate aggregates, but you need to think about this similarity. Mean performance is OK, however, uncertainty/variance estimates are not that easy (and number of runs / surrogate models alone is not an appropriate denominator/estimate for degrees of freedom).

Any deviation you observe between the runs can only come from model instability, i.e. differences in the (surrogate) models: if you compare the 2 surrogate models tested with, say, case 1 in your example, the only difference (if your training is deterministic) is due to exchanging case 10 and 2 in the training sets.

Have a look at our paper: Beleites, C. & Salzer, R.: Assessing and improving the stability of chemometric models in small sample size situations, Anal Bioanal Chem, 390, 1261-1271 (2008). DOI: 10.1007/s00216-007-1818-6
(Please disregard our attempt at estimating an effective sample size - I'm now thinking it doesn't work that way.)