16
$\begingroup$

TLDR:

My dataset is pretty small (120) samples. While doing 10-fold cross validation, should I:

  1. Collect the outputs from each test fold, concatenate them into a vector, and then compute the error on this full vector of predictions (120 samples)?

  2. Or should I instead compute the error on the outputs I get on each fold (with 12 samples per fold), and then get my final error estimate as the average of the 10 fold error estimates?

Are there any scientific papers that argue the differences between these techniques?


Background: Potential Relationship to Macro/Micro scores in multi-label classification:

I think this question may be related to the difference between micro and Macro averages that are often used in a multi-label classification task (e.g. say 5 labels).

In the multi-label setting, micro average scores are computed by making an aggregated contingency table of true positive, false positive, true negative, false negative for all 5 classifier predictions on 120 samples. This contingency table is then used to compute the micro precision, micro recall and micro f-measure. So when we have 120 samples and five classifiers, the micro measures are computed on 600 predictions (120 samples * 5 labels).

When using the Macro variant, one computes the measures (precision, recall, etc.) independently on each label and finally, these measures are averaged.

The idea behind the difference between micro vs Macro estimates may be extended to what can be done in a K-fold setting in a binary classification problem. For 10-fold we can either average over 10 values (Macro measure) or concatenate the 10 experiments and compute the micro measures.

Background - Expanded example:

The following example illustrates the question. Let's say we have 12 test samples and we have 10 folds:

  • Fold 1: TP = 4, FP = 0, TN = 8 Precision = 1.0
  • Fold 2: TP = 4, FP = 0, TN = 8 Precision = 1.0
  • Fold 3: TP = 4, FP = 0, TN = 8 Precision = 1.0
  • Fold 4: TP = 0, FP = 12, Precision = 0
  • Fold 5 .. Fold 10: All have the same TP = 0, FP = 12 and Precision = 0

where I used the following notation:

TP = # of True Positives, FP = # False Positive, TN = # of True Negatives

The results are:

  • Average precision across 10 folds = 3/10 = 0.3
  • Precision on the concatenation of the predictions of the 10 folds = TP/TP+FP = 12/12+84 = 0.125

Note that the values 0.3 and 0.125 are very different!

$\endgroup$
  • $\begingroup$ CV is not really a great measure of predicting future performance. The variance is just too small. Better to go with bootstrap for validating your model. $\endgroup$ – user765195 Aug 19 '12 at 20:09
  • 2
    $\begingroup$ @user765195: could you backup your claim with some citations? $\endgroup$ – Zach Aug 19 '12 at 20:33
  • $\begingroup$ I've been searching but I haven't found any literature regarding the aggregated CV method. It seems to be a more appropriate way to compute the measure as it has less variance. $\endgroup$ – user13420 Aug 19 '12 at 21:15
  • 1
    $\begingroup$ @Zach, there's some discussion here, in Harrell's book: tinyurl.com/92fsmuv (look at the last paragraph in page 93 and the first paragraph in page 94.) I'll try to remember other references that are more explicit. $\endgroup$ – user765195 Aug 19 '12 at 23:42
  • 1
    $\begingroup$ AFAIK, deciding between out-of-bootstrap and iterated $k$-fold cross validation is not quite that clear. It may depend on the type of data you have and on the interpretation that you want to do. $\endgroup$ – cbeleites unhappy with SX Aug 20 '12 at 9:02
4
$\begingroup$

The described difference is IMHO bogus.

You'll observe it only if the distribution of truely positive cases (i.e. reference method says it is a positive case) is very unequal over the folds (as in the example) and the number of relevant test cases (the denominator of the performance measure we're talking about, here the truly positive) is not taken into account when averaging the fold averages.

If you weight the first three fold averages with $\frac{4}{12} = \frac{1}{3}$ (as there were 4 test cases among the total 12 cases which are relevant for calculation of the precision), and the last 6 fold averages with 1 (all test cases relevant for precision calculation), the weighted average is exactly the same you'd get from pooling the predictions of the 10 folds and then calculating the precision.


edit: the original question also asked about iterating/repeating the validation:

yes, you should run iterations of the whole $k$-fold cross validation procedure:
From that, you can get an idea of the stability of the predictions of your models

  • How much do the predictions change if the training data is perturbed by exchanging a few training samples?
  • I.e., how much do the predictions of different "surrogate" models vary for the same test sample?

You were asking for scientific papers:

Underestimating variance Ultimately, your data set has finite (n = 120) sample size, regardless of how many iterations of bootstrap or cross validation you do.

  • You have (at least) 2 sources of variance in the resampling (cross validation and out of bootstrap) validation results:

    • variance due to finite number of (test) sample
    • variance due to instability of the predictions of the surrogate models
  • If your models are stable, then

    • iterations of $k$-fold cross validation were not needed (they don't improve the performance estimate: the average over each run of the cross validation is the same).
    • However, the performance estimate is still subject to variance due to the finite number of test samples.
    • If your data structure is "simple" (i.e. one single measurement vector for each statistically independent case), you can assume that the test results are the results of a Bernoulli process (coin-throwing) and calculate the finite-test-set variance.
  • out-of-bootstrap looks at variance between each surrogate model's predictions. That is possible with the cross validation results as well, but it is uncommon. If you do this, you'll see variance due to finite sample size in addition to the instability. However, keep in mind that some pooling has (usually) taken place already: for cross validation usually $\frac{n}{k}$ results are pooled, and for out-of-bootstrap a varying number of left out samples are pooled.
    Which makes me personally prefer the cross validation (for the moment) as it is easier to separate instability from finite test sample sizes.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Also, I'm doing multi-label classification with four classifiers. So I want to look into the Micro and Macro F-measures across the 4 task. I assume the "combined" cross-validation would be even necessary in this case ? Also I'm not certain if the out-of-bootstrap is same as the "combined" CV method I'm mentioning above. There was also some discussion at stats.stackexchange.com/questions/4868/… $\endgroup$ – user13420 Aug 20 '12 at 14:37
  • 1
    $\begingroup$ @user13420: Thanks. I was thinking at the iteration level. At the moment I don't see much advantage of pooling the results for each fold. I'd rather look at average and variance across all samples (thus holding to the assumption that all surrogate models are equivalent - which is underlying the cross validation procedure and which is a hypothesis you probably won't be able to reject for a 10-fold cross validation on total 120 samples) for the 10 folds. $\endgroup$ – cbeleites unhappy with SX Aug 20 '12 at 22:08
  • 1
    $\begingroup$ @cbeleites - When you answered yes at the top of your answer - Do you mean that approach 1 as described at the top of the OP is recommended over 2 or viceversa? $\endgroup$ – Josh Oct 28 '13 at 21:50
  • 1
    $\begingroup$ @Josh: that yes belongs to a part of the question which was deleted in some later (your?) edit of the question, where the OP asked whether iterations/repetitions should be run. Methods 1 and 2 yield the same result if the pooling weights for the number of cases, so IMHO the difference is bogus. I'll add a clarification to the answer. $\endgroup$ – cbeleites unhappy with SX Oct 29 '13 at 11:03
  • 2
    $\begingroup$ Thanks cbeleites - I added those clarifications because I found the wording of the original question a bit confusing. I hope my edits were for the better - I tried to highlight the dilemma better - but please let me know otherwise. All that said, when you mentioned that you find the difference bogus - I would like to note that @user13420 gets two substantially different results at the bottom of his OP when following approaches 1 or 2. I have found myself facing this dilemma myself. I believe the 2nd approach is more common though, but it would be great to get your take on it. $\endgroup$ – Josh Oct 29 '13 at 13:38
1
$\begingroup$

You should do score(concatenation). It is a common misconception in the field that mean(scores) is the best way. It can introduce more bias into your estimate, especially on rare classes, as in your case. Here is a paper backing this up:

http://www.kdd.org/exploration_files/v12-1-p49-forman-sigkdd.pdf

In the paper, they use "Favg" in place of your "mean(scores)" and "Ftp,fp" in place of your "score(concatenation)"

Toy Example:

Imagine that you have 10 fold cross validation and a class which appears 10 times, and happens to be assigned so that it appears once in each fold. Also the class is always predicted correctly but there there is a single false-positive in the data. The test fold containing the false positive will have 50% accuracy, while all other folds will have 100%. So avg(scores)=95%. On the other hand, score(concatenation) is 10/11, about 91%.

If we assume that that true population is well represented by the data, and that the 10 cross-validation classifiers well represent the final classifier, then real world accuracy would be 91%, and the avg(scores) estimate of 95% is way biased.

In practice, you will not want to make those assumptions. Instead you can use distribution statistics to estimate confidence, by randomly permuting the data and re-computing score(concatenation) multiple times, as well as bootstrapping.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is a great paper! I think the result in the language of the original question (not used in the paper) is that when computing F score, use a "micro averaging" approach; specifically, sum the TP, TN, FP, FN from all folds, to get a single confusion matrix, and then compute F score (or other desired metrics). $\endgroup$ – travelingbones Sep 20 '16 at 15:35

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.