3
$\begingroup$

According to "no free lunch theorem" (also here and here), we cannot deduce just from the data alone (without any domain knowledge) which classifier is better. Of course, we use cross-validation to do precisely that.

So what are the assumptions that we implicitly make that make cross-validation a meaningful procedure?

$\endgroup$
  • $\begingroup$ Well first one is that your collected data is representative of future data. In particular, with large number of variables, much of the input space is unexplored by training data. $\endgroup$ – seanv507 Apr 12 '16 at 6:37
  • $\begingroup$ @seanv507 What is your definition of "representative"? $\endgroup$ – max Apr 12 '16 at 8:08
  • 1
    $\begingroup$ For now just a comment: "we cannot deduce just from the data alone" seeing that superiority of algorithms is often claimed without even a practical specification what is suitable data and what is not, deducing from data is IMHO already a big step into the right direction. $\endgroup$ – cbeleites supports Monica Apr 12 '16 at 23:15
2
$\begingroup$

I had this question for myself and found three (really only two) assumptions that are important and could be violated in practice. I decided to write what I found here since this question helped to think about it.

Representative of Future Data

I personally don't like when people bring this up because NO algorithm does well when your training data is different than the test data. This is the whole point of the "no free lunch" theorem that in order to do better than random guessing you must have additional information or anything can happen.

No Information Leakage

Okay assuming we are even in a universe where historical data is helpful then we have to make sure there is no information leakage. By that I mean information from the validation set leaks to the training set. When we partition the data into K-folds and designate one fold to be the validation set then we have "lost" information. K-fold cross validation uses that "lost" information to estimate test accuracy.

However, lets consider an extreme case. What happens if the model you used could completely guess every single point in the validation set with just the training set? Then instead of K-fold cross validation you are instead running your model k times getting exactly the same result. Obviously that would be no help whatsoever on estimating test accuracy.

In practice you couldn't tell so easy because there could just be some information leakage. A practical example is looking at the sales of different years of the same make and model of car. Car models don't change much from year to year and so sales will be really similar from year to year. If you have information from 1990-2016 and then take out 2000 as your validation partition then you haven't lost much information in your model.

Bias vs Variance trade off

K-fold cross validation make any model more complicated. That is because we believe the model is very biased by the training data. We add variance into the model (which parameters to be picked) to decrease bias. This is a known trade-off in statistics that has no clear cut optimal solution. I think this is basically a corollary of information leakage assumption though.

TLDR (Summary)

K-fold cross validation assumes that the good historical data gives a very biased model and isn't too redundant. Otherwise we are now in the domain of the free lunch theorem where even "anti-cross validation" is a good way to go.

Some references:

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