I have a question about using k-fold cross-validation.

From what I have read, there are several steps for using it.

  1. Shuffle my data.
  2. Train my model for each fold on training data and test it using testing data.
  3. I get k different success-rates for the evaluation of the model so I take a mean and interpret it as the model's average performance.

Now for another model I repeat all steps, I get another average performance and I can compare these two models. Am I right?

Now comes the tricky part. Do I shuffle the data ahead of evaluation for each model?

I've tried searching this and haven't run into any solid mathematical argument. I think that both not-shuffling and shuffling before each model evaluation makes sense. Could you point me to some article?


Assumption 1: All initial problems orders are uniformly random, and that the only question we have is: how to randomize the problems (i.e. should we randomize them for each model? or should we randomize them once for all models?)? (which I think is your question).

Following assumption 1

If we model $k$-fold x-val as a function, I would suggest the following to represent the average accuracy of model $m$:

$$f(m,k,\mathcal{P}, o)$$ where $\mathcal{P}$ is the set of problems, and $o$ defines the order of the problems in $\mathcal{P}$ before they got partitioned into $k$ folds.

So, in other words, in my view, the score of $k$-fold x-val is only a function of:

  • Model under evaluation (i.e. $m$).
  • Total problems set (i.e. $\mathcal{P}$).
  • Initial order of problems set before partitioning them (i.e. $o$).
  • And total number of folds (i.e. $k$).

Let's now consider various cases and how they relate to the value $f(m,k,\mathcal{P}, o)$.

Case 1: If $k = |\mathcal{P}|$ (i.e. total number of folds is equal to total number of problems, then for any different orders $o_1$ and $o_2$, the scores are identical: $$f(m,k,\mathcal{P}, o_1) = f(m,k,\mathcal{P}, o_2)$$

So in the case when $k = |\mathcal{P}|$, clearly the order doesn't matter.

But, in some cases it's impossible to have $k = |\mathcal{P}|$ without causing a class imbalanced in training or testing folds. So I think we should not be too happy about Case 1.

Let's look at another case where the order $o$ does not matter.

Case 2: For any orders $o_1$ and $o_2$, the following is true:

$$ \lim_{|\mathcal{P}| \rightarrow \infty}f(m,k,\mathcal{P}, o_1) = \lim_{|\mathcal{P}| \rightarrow \infty}f(m,k,\mathcal{P}, o_2) $$

In my view this statement is true because of the law of large numbers.

But similarly to Case 1, I think we should not get too excited about this because usually our problems are not large enough to trigger this equality.

Let's look at another case that is more realistic.

Case 3: For a finite problems set, it is IMO very likely that there exists orders $o_1$ and $o_2$ such that:

$$f(m,k,\mathcal{P}, o_1) \ne f(m,k,\mathcal{P}, o_2)$$

This is an empirical thing. Personally, based on all datasets that I have evaluated against, the probability that this inequality is true is $1$.

Perhaps you can run a Monte-Carlo based simulation to estimate the probability that the inequality above is true as follows: $$\begin{split} =&\frac{\text{total num of times }f(m,k,\mathcal{P}, o_1) \ne f(m,k,\mathcal{P}, o_2)}{\text{total number of evaluations}}\\ =&\frac{1}{n} \sum_{i=0}^{n} I(f(m,k,\mathcal{P}, o_{1+i}) \ne f(m,k,\mathcal{P}, o_{2+i}))\\ >& 0 \ \ \ \ \ \text{(I think this is true for most cases)} \end{split}$$ where $I$ is an indicator function that returns 0 if statement is false, else returns 1.

I think you wouldn't be surprised if it's $> 0$ for all your datasets.

So, clearly, for any models $m_1$ and $m_2$, and any orders $o_1$ and $o_2$, the following test -by itself- is not very meaningful: $$f(m_1,k,\mathcal{P},o_1) > f(m_2,k,\mathcal{P},o_2) \ \ \ \ \ \ \ \ (1)$$ because there are two variables: two models $m_1$ and $m_2$, and also two different orders $o_1$ and $o_2$. Therefore, you can't know which one is causing which. Is it due to the order $o_1$ that is very lucky and helping $m_1$ to score better? Or is due $m_1$ being really good? Or a mixture of other factors?

Alternatively, if you choose a single fixed order $o_1$, then (note that order is $o_1$ for both models): $$f(m_1,k,\mathcal{P},o_1) > f(m_2,k,\mathcal{P},o_1) \ \ \ \ \ \ \ \ (2)$$ means that model $m_1$ is better than model $m_2$ when tested against $\mathcal{P}$ problems as ordered by the specific order $o_1$.

So clearly $(2)$ is telling us more information about the models than $(1)$. I.e. at least now we could say something about models $m_1$ and $m_2$ even though it is still somewhat useless as it is speific to the order $o_1$, but at least better than $(1)$ that didn't even isolate the effect of the order!

So, $(2)$ tells us more information about the models, but it is specific to order $o_1$. Do we care? Usually, no. We don't care about the order. So while $(2)$ is better than $(1)$, it is still not very useful.

Therefore, we need to repeat $(2)$ multiple times (forget about $(1)$), each time with a different order $o_i$ (where $i \in \{1, 2, \ldots, n\}$. Then, we need to perform statistical significance tests across all the orders $o_1, o_2, \ldots, o_n$, and then measure the $p$ value. Then we conclude that, for any $i \in \{1,2,\ldots,n\}$, $f(m_1,k,\mathcal{P},o_i) > f(m_2,k,\mathcal{P},o_i)$ is the case only if $p \le \alpha$.

Therefore, we now define another $k$-fold x-val function that is independent of the order $o$ as follows: $$ g(m,k,\mathcal{P}) = \lim_{n \rightarrow \infty} \frac{1}{n} \sum_{i=1}^n f(m,k,\mathcal{P},o_i) $$

But since we cannot realistically choose $n \rightarrow \infty$, we choose $n$ that is large enough. How large is large enough? I suggest the following:

  • Large enough to give us a $p$ value that is less than $\alpha$.

Important note: choosing $n$ that is large enough (maybe $n=1000$) to give you a small enough $p$ value (maybe $p \le \alpha$) does not necessarily mean that model $m_1$ is significantly better than $m_2$. Instead, it only means this:

  • A1: the order-independent $k$-old x-val process thinks that the score of $m_1$ is higher than that of $m_2$.

Which is a different answer than the following:

  • A2: $m_1$ is better than $m_2$.

Simply calculating the $p$ value above to show A1 does not show A2.

Unanswered useful questions (beyond your main question)

  • What if Assumption 1 is violated? This could be interesting for time series problems?
  • Is the number $n$ independent of the size of the problems set $\mathcal{P}$?
  • How to show A2?
  • $\begingroup$ Thank you, that was the kind of answer I was looking for. From my experience, people are only doing one cross validation whereas you advice to do this n=1000 times. Is one cross-validation a good estimate? A2: I thought the whole point of cross-validation was to get an idea on which model is better. Could you elaborate little bit on this? $\endgroup$ – svecon May 28 '16 at 20:33
  • $\begingroup$ I didn't suggest $n=1000$, I just put it as an example to make my post more readable. I suggest you to choose any $n$ that gives you $p \le \alpha$ (usually you want $n$ to be smallest that satisfies $p \le \alpha$ so that you don't waste your time repeating for too long. As for A2, nope, $k$-fold x-val doesn't aim to show statistical significance due to the difference. It only tries to measure some statistic (like accuracy). However, answering whether the score of $m_1$ is better than that of $m_2$ is due to a systematic difference (as opposed to sheer dumb luck) is a different question. $\endgroup$ – caveman May 28 '16 at 20:43
  • $\begingroup$ Sorry I forgot to answer your other question: is doing $k$-fold x-val one time good? Well, I think we can't tell. It depends on how lucky the order $o_i$ was right? One way to find out is to repeat it with different initial orders $o_i$ for $i \in \{1,2,.\ldots,n\}$, then estimate the order-independent variant $g$ good enough that gives you a different that is significant for the $k$-fold x-val process. $\endgroup$ – caveman May 28 '16 at 20:52

What you're doing here is an example of Adaptive Data Analysis, ie. selecting a model by looking at the CV results of two or more models. This could be dangerous and a lot of research is being carried out right now on how to mitigate it.

So, take extra precaution when you're doing CV for many models. For a demo of the failure of cross validation, see[1].

[1] Rao, R. B., Fung, G., & Rosales, R. (2008, April). On the Dangers of Cross-Validation. An Experimental Evaluation. In SDM (pp. 588-596).

  • 1
    $\begingroup$ Thank you. Could you please give a few reasons on why CV fails, and a few examples on how to mitigate it? $\endgroup$ – caveman May 28 '16 at 23:50

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.