Imagine I have a classifier with some parameter $a$. I want to perform parameter optimisation and model selection. Imagine that my grid for the values of $a$ has three values 1,5 and 10 and I want perform 10-fold cross-validation as follows:

  • For each iteration, the dataset is partitioned into a 9:1 ratio of training and testdata, whereby at each iteration the two consists from other sampled datapoints of the full dataset (which is the description of 10-fold cross-validation)

  • Now, each of these iterations is done three times: one time for each parameter value.

Hence I end up with 30 iterations (10-fold cv basically, but for each parameter once) and pick the parameter which on average performed best. I am aware that this chosen model has not YET been tested on new data. However during all the iterations, since test and training set have been disjunct and independent, it's performance has been evaluated on this unseen test set. So why is this approach incorrect (as in comparison with nested cv with an inner and outer loop)?

  • $\begingroup$ I don't understand your description of your procedure. Please clarify. $\endgroup$ – Erik Oct 28 '15 at 12:47
  • $\begingroup$ Basically I would perform 10-fold cross-validation, for each parameter value 1,5 and 10 once $\endgroup$ – user24544 Oct 28 '15 at 12:49
  • 1
    $\begingroup$ What you describe is not a nested CV. I edited your title to represent that, feel free to edit again if you want to improve it. $\endgroup$ – amoeba Oct 28 '15 at 14:33

The approach is not incorrect per se; it depends on the purpose you are using it for. For parameter optimisation and model selection it is fine, though you should iterate the cross validation for a more stable selection.

An error would be to just use the performance estimates obtained for the best model as your expectation of future model performance.

Some intuition on that:

Consider the extreme case that the real model performance $p_i$ is identical for all three possible hyperparameter values. Since you have a finite sample the observed model performance is $$ \hat{p}_i= p_i + \epsilon_i $$ Here $\epsilon_i$ is an error term. If you now select the model with the best $\hat{p}_i$ it is very likely that the corresponding $\epsilon_i$ is positive. If we assume that $\epsilon_i$ is symmetrical around zero, then the probability of at least one $\epsilon_i$ being posiitve is $\frac{7}{8}$ and obviously if one is positive we won't get a negative one by choosing the highest $\hat{p}_i$. This means you will overestimate the real performance of the model.

Now, in a nested cross validation what you do (I agree with @amoeba that what you do is not nested CV) is the inner or nested part of the cross validation. Out of it you get a single model which you apply to the training data of the outer CV loop (which is new to the model).

This means you get a new error estimate with is independent from the one in the inner cross validation and therefore does not inherit the bias. Since you have just one model at this point you do not need to made a choice of models, which would introduce a new bias.

  • $\begingroup$ wow, what a lucid example! however, how is this problem resolved when using nested cv? $\endgroup$ – user24544 Oct 28 '15 at 15:39
  • $\begingroup$ @TestGuest I added a bit on that. $\endgroup$ – Erik Oct 28 '15 at 15:54
  • $\begingroup$ so do I understand it correctly that the bias is lower in the outer loop since - if we stay with your example - the probability of a positive epsilon is now only 0.5? $\endgroup$ – user24544 Oct 28 '15 at 17:13
  • $\begingroup$ ................:-) $\endgroup$ – user24544 Oct 29 '15 at 10:56
  • 1
    $\begingroup$ @TestGuest In my example, the bias is zero (it is an average, and is symmetric around zero). In practice, it depends on your performance estimator (which could be biased itself). In addition, cross validation can slightly underestimate the performance since you use only (for example) 90% of the data the model is not as well trained as it will be with 100%. Both of these issues tend to have little impact in practice. $\endgroup$ – Erik Oct 29 '15 at 11:25