26
$\begingroup$

My understanding is that with cross validation and model selection we try to address two things:

P1. Estimate the expected loss on the population when training with our sample

P2. Measure and report our uncertainty of this estimation (variance, confidence intervals, bias, etc.)

Standard practice seems to be to do repeated cross validation, since this reduces the variance of our estimator.

However, when it comes to reporting and analysis, my understanding is that internal validation is better than external validation because:

It is better to report:

  • The statistics of our estimator, e.g. its confidence interval, variance, mean, etc. on the full sample (in this case the CV sample).

than reporting:

  • The loss of our estimator on a hold-out subset of the original sample, since:

    (i) This would be a single measurement (even if we pick our estimator with CV)

    (ii) Our estimator for this single measurement would have been trained on a set (e.g. the CV set) that is smaller than our initial sample since we have to make room for the hold-out set. This results in a more biased (pessimistic) estimation in P1 .

Is this correct? If not why?

Background:

It is easy to find textbooks that recommend dividing your sample into two sets:

  • The CV set, which is subsequently and repeatedly divided into train and validation sets.
  • The hold-out (test) set, only used at the end to report the estimator performance

My question is an attempt to understand the merits and advantages of this textbook approach, considering that our goal is to really address the problems P1 and P2 at the beginning of this post. It looks to me that reporting on the hold-out test set is bad practice since the analysis of the CV sample is more informative.

Nested K-fold vs repeated K-fold:

One can in principle combine hold-out with regular K-fold to obtain nested K-fold. This would allow us to measure the variability of our estimator, but it looks to me that for the same number of total models trained (total # of folds) repeated K-fold would yield estimators that are less biased and more accurate than nested K-fold. To see this:

  • Repeated K-fold uses a larger fraction of our total sample than nested K-fold for the same K (i.e. it leads to lower bias)
  • 100 iterations would only give 10 measurements of our estimator in nested K-fold (K=10), but 100 measurements in K-fold (more measurements leads to lower variance in P2)

What's wrong with this reasoning?

$\endgroup$
  • 1
    $\begingroup$ I have tweaked your title so that it is more specific to what I gather you want to know. I think you are more likely to get the info you need this way. Feel free to change it back if you disagree. Note also that this thread has automatically become CW due to the high number of edits. If you don't want it to be CW, flag it for moderator attention; it should be possible to reverse that (I think). $\endgroup$ – gung - Reinstate Monica Jul 16 '13 at 0:29
  • 1
    $\begingroup$ Thanks @gung. My only concern is that some people may confuse hold-out with 2-fold CV, with this, I think internal vs external CV as in Steyerberg03 is clearer $\endgroup$ – Amelio Vazquez-Reina Jul 16 '13 at 0:39
20
+50
$\begingroup$

Let me add a few points to the nice answers that are already here:

Nested K-fold vs repeated K-fold: nested and repeated k-fold are totally different things, used for different purposes.

  • As you already know, nested is good if you want to use the inner cv for model selection.
  • repeated: IMHO you should always repeat the k-fold cv [see below].

I therefore recommend to repeat any nested k-fold cross validation.

Better report "The statistics of our estimator, e.g. its confidence interval, variance, mean, etc. on the full sample (in this case the CV sample).":

Sure. However, you need to be aware of the fact that you will not (easily) be able to estimate the confidence interval by the cross validation results alone. The reason is that, however much you resample, the actual number of cases you look at is finite (and usually rather small - otherwise you'd not bother about these distinctions).
See e.g. Bengio, Y. and Grandvalet, Y.: No Unbiased Estimator of the Variance of K-Fold Cross-Validation Journal of Machine Learning Research, 2004, 5, 1089-1105.

However, in some situations you can nevertheless make estimations of the variance: With repeated k-fold cross validation, you can get an idea whether model instability does play a role. And this instability-related variance is actually the part of the variance that you can reduce by repeated cross-validation. (If your models are perfectly stable, each repetition/iteration of the cross validation will have exactly the same predictions for each case. However, you still have variance due to the actual choice/composition of your data set). So there is a limit to the lower variance of repeated k-fold cross validation. Doing more and more repetitions/iterations does not make sense, as the variance caused by the fact that in the end only $n$ real cases were tested is not affected.

The variance caused by the fact that in the end only $n$ real cases were tested can be estimated for some special cases, e.g. the performance of classifiers as measured by proportions such as hit rate, error rate, sensitivity, specificity, predictive values and so on: they follow binomial distributions Unfortunately, this means that they have huge variance $\sigma^2 (\hat p) = \frac{1}{n} p (1 - p)$ with $p$ the true performance value of the model, $\hat p$ the observed, and $n$ the sample size in the denominator of the fraction. This has the maximum for $p = 0.5$. You can also calculate confidence intervals starting from the observation. (@Frank Harrell will comment that these are no proper scoring rules, so you anyways shouldn't use them - which is related to the huge variance). However, IMHO they are useful for deriving conservative bounds (there are better scoring rules, and the bad behaviour of these fractions is a worst-case limit for the better rules),
see e.g. C. Beleites, R. Salzer and V. Sergo: Validation of Soft Classification Models using Partial Class Memberships: An Extended Concept of Sensitivity & Co. applied to Grading of Astrocytoma Tissues, Chemom. Intell. Lab. Syst., 122 (2013), 12 - 22.

So this lets me turn around your argumentation against the hold-out:

  • Neither does resampling alone (necessarily) give you a good estimate of the variance,
  • OTOH, if you can reason about the finite-test-sample-size-variance of the cross validation estimate, that is also possible for hold out.

Our estimator for this single measurement would have been trained on a set (e.g. the CV set) that is smaller than our initial sample since we have to make room for the hold-out set. This results in a more biased (pessimistic) estimation in P1 .

Not necessarily (if compared to k-fold) - but you have to trade off: small hold-out set (e.g. $\frac{1}{k}$ of the sample => low bias (≈ same as k-fold cv), high variance (> k-fold cv, roughly by a factor of k).

It looks to me that reporting on the hold-out test set is bad practice since the analysis of the CV sample is more informative.

Usually, yes. However, it is also good to keep in mind that there are important types of errors (such as drift) that cannot be measured/detected by resampling validation.
See e.g. Esbensen, K. H. and Geladi, P. Principles of Proper Validation: use and abuse of re-sampling for validation, Journal of Chemometrics, 2010, 24, 168-187

but it looks to me that for the same number of total models trained (total # of folds) repeated K-fold would yield estimators that are less biased and more accurate than nested K-fold. To see this:

Repeated K-fold uses a larger fraction of our total sample than nested K-fold for the same K (i.e. it leads to lower bias)

I'd say no to this: it doesn't matter how the model training uses its $\frac{k - 1}{k} n$ training samples, as long as the surrogate models and the "real" model use them in the same way. (I look at the inner cross-validation / estimation of hyper-parameters as part of the model set-up).
Things look different if you compare surrogate models which are trained including hyper-parameter optimization to "the" model which is trained on fixed hyper-parameters. But IMHO that is generalizing from $k$ apples to 1 orange.

100 iterations would only give 10 measurements of our estimator in nested K-fold (K=10), but 100 measurements in K-fold (more measurements leads to lower variance in P2)

Whether this does make a difference depends on the instability of the (surrogate) models, see above. For stable models it is irrelevant. So may be whether you do 1000 or 100 outer repetitions/iterations.


And this paper definitively belongs onto the reading list on this topic: Cawley, G. C. and Talbot, N. L. C. On Over-fitting in Model Selection and Subsequent Selection Bias in Performance Evaluation, Journal of Machine Learning Research, 2010, 11, 2079-2107

$\endgroup$
6
$\begingroup$

A key reference explaining this is:

@ARTICLE{pic90,
  author = {Picard, R. R. and Berk, K. N.},
  year = 1990,
  title = {Data splitting},
  journal = The American Statistician,
  volume = 44,
  pages = {140-147}
}

See also:

@Article{mic05pre,
  author =       {Michiels, Stefan and Koscielny, Serge and Hill, Catherine},
  title =        {Prediction of cancer outcome with microarrays: a
multiple random validation strategy},
  journal =      {Lancet},
  year =         2005,
  volume =       365,
  pages =        {488-492},
  annote =       {comment on
p. 454; validation;microarray;bioinformatics;machine learning;nearest
centroid;severe problems with data splitting;high variability of list
of genes;problems with published studies;nice results for effect of
training sample size on misclassification error;nice use of confidence
intervals on accuracy estimates;unstable molecular signatures;high
instability due to dependence on selection of training sample}
}

In my own work I've found that data splitting requires training and test sample sizes approaching 10,000 to work satisfactorily.

$\endgroup$
  • $\begingroup$ Frank - These are great resources. I wonder how this information relates to what @Dan has provided in his answer. Perhaps I am misreading this, but it looks like the community is divided on this issue. $\endgroup$ – Amelio Vazquez-Reina Jul 18 '13 at 0:21
  • $\begingroup$ I didn't have time to read the first, but as for the second, I took a quick glance and it seems to echo exactly what my papers said. Take a close look at the "Statistical analysis" section, and you will see that they describe the same feature selection process that Dikran describes in the post I linked above. I'm guessing the people they studied did not do it that way, and that's why they find that "Because of inadequate validation, our chosen studies published overoptimistic results compared with those from our own analyses". I don't think there is any disagreement. $\endgroup$ – Dan L Jul 18 '13 at 13:35
4
$\begingroup$

It really depends on your model building process, but I found this paper helpful

http://www.biomedcentral.com/content/pdf/1471-2105-7-91.pdf

The crux of what is discussed here is the significant liberal bias (estimating model performance to be better than it will actually be) that will occur if you are selecting your model based on the same thing that you are using to estimate its performance. So, if you are selecting your model from a set of possible models by looking at its cross validation error, you should not use cross validation error (or any other internal estimation method) to estimate the model performance.

Another useful resource is

https://stats.stackexchange.com/a/27751/26589

This post lays out a clear example of how selecting your features when all the data is "seen" will lead to a liberal bias in model performance (saying your model will perform better than it actually will).

If you would like me to lay out an example that is more specific to what you do, maybe you could give a general description of the types of models you're building (how much data you have, how many features your selecting from, the actual model, etc.).

$\endgroup$
  • $\begingroup$ Thank you Dan. This is all interesting. For simplicity we can assume that we are trying to estimate the kernel parameters of an SVM (e.g. an RBF kernel) for binary classification (< ~10 parameters) and that we are working with 100 samples (e.g. 20 positives) from a large population. $\endgroup$ – Amelio Vazquez-Reina Jul 18 '13 at 0:27
  • $\begingroup$ A couple quick questions. 1) When you build your SVM's, do you allow yourself to choose a subset of the 10 parameters, or do you always use all of the ones that you're handed? 2) Do you ever consider different kernels or models (logistic, random forest, etc.)? 3) What software/package are you using? Built in cross validation implementations vary, and I'd like to know which you'd be using. $\endgroup$ – Dan L Jul 18 '13 at 13:23
  • $\begingroup$ Thank you @Dan - I do a grid search across models and parameters (i.e. the kernels and parameters are different through the grid search). For each experiment in the grid search I do CV (repeated K-fold cross validation). I am using scikit-learn. $\endgroup$ – Amelio Vazquez-Reina Jul 18 '13 at 13:39
  • 1
    $\begingroup$ Thanks @Dan. I guess my only question left about nested cross validation is how to choose the model (since I get a different model in each fold of the outer loop). It would not look reasonable to me to pick the model that has the highest score in this outer loop, since the winning model in each fold is measured against a different part of the dataset. $\endgroup$ – Amelio Vazquez-Reina Jul 22 '13 at 13:34
  • 1
    $\begingroup$ Say you have 3 outer folds. This means you run an entire model building process 3 times, giving you three different models. You don't use any of those models in the end -- to get your final model, you run the entire model building process on all of your data (except for possibly an independent evaluate set). It seems like this would lead to overfitting, but if your model building strategy overfits, it should also overfit in the outer cross validation, leading to a appropriately higher error estimate. $\endgroup$ – Dan L Jul 22 '13 at 16:52
2
$\begingroup$

I think your understanding is correct, the estimator for loss obtained by using a single hold-out test set usually has high variance. By performing something like K-folds cross validation you obtain a more accurate idea of the loss, as well as sense of distribution of the loss.

There is usually a tradeoff, the more CV folds the better your estimate, but more computational time is needed.

$\endgroup$
  • $\begingroup$ Thanks. I have added a background piece to the OP to clarify my question further. $\endgroup$ – Amelio Vazquez-Reina Jul 12 '13 at 14:28

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.