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
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).
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.
You can use the Evaluate class to perform this 10-fold cross-validation. To define the cross-validation you have to set the parameter as '-x 10' in the EvaluateModel.
clear all; close all; clc;
%% Add jar file to path plus import dependencies
javaaddpath('/usr/local/weka-3-6-11/weka.jar');
import weka.classifiers.trees.RandomForest.*;
import weka.classifiers.meta.Bagging.*;
import weka.classifiers.Evaluation.*;
import weka.core.Instances.*
%% load the arff file and extract the informations
filename = 'algo_output/results_features_labeling2_2class.arff';
loader = weka.core.converters.ArffLoader();
loader.setFile(java.io.File(filename));
data = loader.getDataSet();
data.setClassIndex(D.numAttributes()-1);
%% classification
classifier = weka.classifiers.functions.MultilayerPerceptron();
classifier.buildClassifier(data);
classifier.toString()
%% 10-fold cross-validation
ev = weka.classifiers.Evaluation(data);
v(1) = java.lang.String('-t');
v(2) = java.lang.String(filename);
v(3) = java.lang.String('-x');
v(4) = java.lang.String('10');
v(5) = java.lang.String('-i');
prm = cat(1,v(1:end));
ev.evaluateModel(classifier, prm)
For more information, check this link.
Best Answer
Cross validation 'runs several times' but it only predicts each case one time.
In your example of 10-fold cross-validation on 160 cases, each of the 10 runs (folds) leaves out 10% of the cases (lets say cases #1-16) to be tested on while training on the remaining 90% (#17-160 cases). The trained model tests on the 16 cases in the hold-out sample, and then the process is repeated on a new hold-out sample (e.g. cases #17-32). This process is repeated until each case has been predicted one time.
The idea is to never use the same case for both the training and testing phase, which can help with problems associated with over-fitting.