26
$\begingroup$

K-fold cross-validation can be used to estimate the generalization capability of a given classifier. Can I (or should I) also compute a pooled variance from all validation runs in order to obtain a better estimate of its variance?

If not, why?

I have found papers which do use the pooled standard deviation across cross-validation runs. I have also found papers explicitly stating there is no universal estimator for the validation variance. However, I have also found papers showing some variance estimators for the generalization error (I am still reading and trying to comprehend this one). What do people really do (or report) in practice?

EDIT: When CV is used to measure the crude classification error (i.e. either a sample has been labeled correctly or it hasn't; e.g. true or false) then it may not make sense to talk about a pooled variance. However, I am talking about the case in which the statistic we are estimating does have a variance defined. So, for a given fold, we can end up with both a value for the statistic and a variance estimate. It does not seems right to discard this information and consider only the average statistic. And while I am aware I could build a variance estimate using bootstrap methods, (if I am not very wrong) doing so would still ignore the fold variances and take only the statistic estimates into consideration (plus requiring much more computation power).

$\endgroup$
  • $\begingroup$ Did you calculate the variance considering the two possible ways to see if they differ greatly from each other? $\endgroup$ – zeferino Jul 3 '12 at 18:09
  • $\begingroup$ Yes, I did. In some experiments there was a change of about an order of magnitude between the variance and the pooled variance for training samples. There wasn't much difference for validation samples. The larger changes seemed to be associated with less accurate models. $\endgroup$ – Cesar Jul 4 '12 at 3:17
  • 1
    $\begingroup$ @Cesar: nice observation: your models are very unstable (high variance between iterations). In classification (unless the classifier is worse than guessing), unstable predictions will lead to wrong predictions. An illustrative thought for that is that a deviation from a correct prediction will always be in direction "wrong", there is no too high which would cancel with too low. $\endgroup$ – cbeleites Jul 4 '12 at 12:02
  • 1
    $\begingroup$ @cbeleites: wouldn't this be somewhat expected then, since the large variance changes occur mostly with models showing higher error rates? By the way, nice update on your answer. I still have to read it more carefully, but I am already very grateful. Thanks. $\endgroup$ – Cesar Jul 5 '12 at 5:01
  • 1
    $\begingroup$ @Cesar: Thx. Sure it is expected, a less illustrative way to state that is the variance formula for proportions (see my answer): the more extreme the true error rate is, the lower the variance, the maximum variance is at error rate = 50%. $\endgroup$ – cbeleites Jul 5 '12 at 9:51
13
+50
$\begingroup$

Very interesting question, I'll have to read the papers you give... But maybe this will start us in direction of an answer:

I usually tackle this problem in a very pragmatic way: I iterate the k-fold cross validation with new random splits and calculate performance just as usual for each iteration. The overall test samples are then the same for each iteration, and the differences come from different splits of the data.

This I report e.g. as the 5th to 95th percentile of observed performance wrt. exchanging up to $\frac{n}{k} - 1$ samples for new samples and discuss it as a measure for model instability.

Side note: I anyways cannot use formulas that need the sample size. As my data are clustered or hierarchical in structure (many similar but not repeated measurements of the same case, usually several [hundred] different locations of the same specimen) I don't know the effective sample size.

comparison to bootstrapping:

  • iterations use new random splits.

  • the main difference is resampling with (bootstrap) or without (cv) replacement.

  • computational cost is about the same, as I'd choose no of iterations of cv $\approx$ no of bootstrap iterations / k, i.e. calculate the same total no of models.

  • bootstrap has advantages over cv in terms of some statistical properties (asymptotically correct, possibly you need less iterations to obtain a good estimate)

  • however, with cv you have the advantage that you are guaranteed that

    • the number of distinct training samples is the same for all models (important if you want to calculate learning curves)
    • each sample is tested exactly once in each iteration
  • some classification methods will discard repeated samples, so bootstrapping does not make sense

Variance for the performance

short answer: yes it does make sense to speak of variance in situation where only {0,1} outcomes exist.

Have a look at the binomial distribution (k = successes, n = tests, p = true probability for success = average k / n):

$\sigma^2 (k) = np(1-p)$

The variance of proportions (such as hit rate, error rate, sensitivity, TPR,..., I'll use $p$ from now on and $\hat p$ for the observed value in a test) is a topic that fills whole books...

  • Fleiss: Statistical Methods for Rates and Proportions
  • Forthofer and Lee: Biostatistics has a nice introduction.

Now, $\hat p = \frac{k}{n}$ and therefore:

$\sigma^2 (\hat p) = \frac{p (1-p)}{n}$

This means that the uncertainty for measuring classifier performance depends only on the true performance p of the tested model and the number of test samples.

In cross validation you assume

  1. that the k "surrogate" models have the same true performance as the "real" model you usually build from all samples. (The breakdown of this assumption is the well-known pessimistic bias).

  2. that the k "surrogate" models have the same true performance (are equivalent, have stable predictions), so you are allowed to pool the results of the k tests.
    Of course then not only the k "surrogate" models of one iteration of cv can be pooled but the ki models of i iterations of k-fold cv.

Why iterate?

The main thing the iterations tell you is the model (prediction) instability, i.e. variance of the predictions of different models for the same sample.

You can directly report instability as e.g. the variance in prediction of a given test case regardless whether the prediction is correct or a bit more indirectly as the variance of $\hat p$ for different cv iterations.

And yes, this is important information.

Now, if your models are perfectly stable, all $n_{bootstrap}$ or $k \cdot n_{iter.~cv}$ would produce exactly the same prediction for a given sample. In other words, all iterations would have the same outcome. The variance of the estimate would not be reduced by the iteration (assuming $n - 1 \approx n$). In that case, assumption 2 from above is met and you are subject only to $\sigma^2 (\hat p) = \frac{p (1-p)}{n}$ with n being the total number of samples tested in all k folds of the cv.
In that case, iterations are not needed (other than for demonstrating stability).

You can then construct confidence intervals for the true performance $p$ from the observed no of successes $k$ in the $n$ tests. So, strictly, there is no need to report the variance uncertainty if $\hat p$ and $n$ are reported. However, in my field, not many people are aware of that or even have an intuitive grip on how large the uncertainty is with what sample size. So I'd recommend to report it anyways.

If you observe model instability, the pooled average is a better estimate of the true performance. The variance between the iterations is an important information, and you could compare it to the expected minimal variance for a test set of size n with true performance average performance over all iterations.

$\endgroup$
  • $\begingroup$ You iterate with new random splits, with replacement, like in bootstrap? Or you repeat k-fold cross-validation several times? This is interesting, because it doesn't seems like bootstrap but may work like so. But how many replications do you perform? This could get very costly easily. $\endgroup$ – Cesar Jul 3 '12 at 15:33
  • $\begingroup$ @Cesar: it is very similar to bootstrap, see the expanded answer. $\endgroup$ – cbeleites Jul 4 '12 at 12:06
  • $\begingroup$ How does CV leave the "same number of distinct training samples" for each model, but bootstrapping does not? I don't follow, as the CV "replicate data sets" are a different combination of observations - how can they possibly provide the same number of distinct observations? Perhaps you are assuming that each record is distinct in the original training set? $\endgroup$ – probabilityislogic Dec 28 '13 at 21:32
  • $\begingroup$ @probabilityislogic: the CV replicate data sets are smaller than the original data set. Thus, different such replicates can be produced even with resampling without replacement. Resampling with replacement you can draw the same record several times. Thus, the number of unique records can vary. Yes, I assume the original records to be distinct. In order to keep statistical independence which is crucial for many applications, resampling should be done at the highest level of the data hierarchy. (E.g. I work with patient data with hundreds of rows for each patient => resample patients) $\endgroup$ – cbeleites Dec 29 '13 at 18:21
  • 1
    $\begingroup$ The problem with estimating variance (and then with confidence intervals) is that the cross validation models and tests (over iterations) are not independent: in the end you only have $n$ independent cases. The models should not be independent at all - in fact, the usual evaluation of CV assumes them to be equal. But regardless of how many iterations you have, each case has been tested already in the first iteration. And there's always the question how representative your small data set is. $\endgroup$ – cbeleites Sep 14 '14 at 14:37
1
$\begingroup$

Remember CV is an estimate only and can never represent the 'real' generalisation error. Depending on your sample size (which will impact your number of folds or fold size) you can be severely limited in your ability to calculate any parameter estimates of the distribution of the generalisation error. In my opinion (and I've seen it purported in various text books, 'Knowledge Discovery with Support Vector Machines'-Lutz Hamel)you can do some bootstrapping variant of CV to estimate the distribution of the generalisation error, but a standard 10-1 (for example) once off CV will not give you enough data points to make inferences about the true gen-error. Bootstrapping requires you to take multiple samples with replacement from your training/test/val effectively doing multiple (say 1000 or so) 10-1 (or whatever) CV tests. You then take your sample distribtion of averages for each CV test as an estimate of the sampling distribution of the mean for the population of CV errors and from this you can estimate distributional parameters i.e. mean, median, std min max Q1 Q3 etc... It's a bit of work, and in my opinion only really required if your application is important/risky enough to warrant the extra work. i.e. perhaps in a marketing environment where the business is simply happy to be better than random then maybe not required. BUT if you are trying to evaluate patient reactions to high risk drugs or predict income expectations for large investments you may well be prudent to carry it out.

$\endgroup$
  • $\begingroup$ It is an estimate, but so could be said about virtually any use of a statistic. However, when each fold already has a variance estimate, it doesn't seems correct to discard this information. I have updated the question with clarifications. $\endgroup$ – Cesar Jul 3 '12 at 15:58
  • $\begingroup$ Perhaps I'm not getting it. I don't really understand why you are agonizing over the variance of a single fold? $\endgroup$ – clancy Jul 4 '12 at 0:46
  • $\begingroup$ Running a single 10-fold CV is not exactly cheap for the particular problem I am trying to tackle. You are correct I could estimate the variance by taking multiple samples with replacement as in bootstrap. But taking a large number of CVs, even a few hundred, could be very impractical in my case. I am looking for a way (if there is any) to combine individual fold variance estimates so I could at least reduce the number of bootstrap samples needed. And besides, curiosity. $\endgroup$ – Cesar Jul 4 '12 at 3:07
  • $\begingroup$ ah okay. Perhaps then the variance of each of the 10 fold means from the from the overall fold mean will be a random variable selected from the sampling distribution for variances...(which I think is a chi sq dist or F dist) $\endgroup$ – clancy Jul 4 '12 at 4:10
  • $\begingroup$ @clancy: with 10-1 do you mean a leave-one-out cv for n = 10 samples? Note that for leave-one-out iterations do not make sense. $\endgroup$ – cbeleites Jul 4 '12 at 12:13

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.