cross-validation to predict distribution of errors on finite test sets

Question

In one use of k-fold cross-validation for evaluating classifiers, one trains k models, each on n(k-1)/k examples, and tests each on n/k examples. The average accuracy on those k test sets of size n/k is used as an estimate of the accuracy of a classifier trained on n examples.

There's different ways to define the true accuracy that we're estimating. One is the expected value of a 0/1 (incorrect/correct) random variable that would result by selecting a random instance from the population and applying the classifier. This expectation is the same as the expectation of accuracy on randomly selected test sets of any size m, not just 1. (Note while true for accuracy, this would not be true for other effectiveness measures, e.g. Van Rijsbergen's F-measure.)

However, suppose one wants to estimate the distribution of observed accuracies that one would see from applying the classifier across lots of randomly selected test sets of size m. One application would be to estimate the probability of having a "failing grade" on a held out test set of size m.

The true distribution of test set accuracy on a test set of size m is binomial with parameters m and p, where p is the true error rate of the classifier. But it's not obvious to me that simply plugging in m and the k-fold CV estimate of p into a binomial is the best thing to do. It certainly ignores the fact that we have uncertainty about our estimate of p. Beyond that, my real interest is in measures like the F-measure where the distribution would not be binomial even if we did know the true p.

Does anyone know of literature on this question? The question is clearly related to the notion of prediction intervals (http://en.wikipedia.org/wiki/Prediction_interval) but with the added complexity of cross-validation.

Answer 1

However, suppose one wants to estimate the distribution of observed accuracies that one would see from applying the classifier across lots of randomly selected test sets of size m. One application would be to estimate the probability of having a "failing grade" on a held out test set of size m.

I would use bootstrapping (see also the Wikipedia site on resampling methods). It allows to approximate the true (unknown) distribution from bootstrap samples (subset of samples obtained by sampling with replacement.

It allows to perform inferencial statistics on the variable (confidence intervals, F-test and so on). A really nice paper on the bootstrap method and its applications is The Bootstrap And Its Application In Signal Processing. It provides you with all the details you need for your case.

Still, what method works best, depends on the particular classifier and the problem you are working on. For example, Kohavi compares different methods to estimate the accuracy of a classifier, and discuss when they work or fail, and why.

Last, notice that when performing CV-resampling to estimate the accuracy of the classifier, the resulting estimates are not i.i.d. samples. Hence, standard inference tests tend not to give accurate estimates. Particularly in extreme situations with little data, and/or highly imbalanced data sets, you might need to double check how accurate your measurements are.

Answer 2

I don't think this totally answers your question, but perhaps provides a useful framework.

An Asymptotic Preliminary

Let $X_{i}$ denote the training data in fold $i$, let $T_i \equiv T(X_i)$ be the trained classifier under data $X_i$, and let $L(T_i, Y_k)$ be the observed loss of the classifier under test data $Y_k$. In all cases, let's assume test data $Y_k$ is independent within and between folds.

It will be helpful to consider two limiting cases: (a) $X_i=X_j$ for all $i, j$ and (b) $X_i \perp X_j$ for all $i,j$. Case (a) corresponds to training on a fixed data set, so for large enough $Y$, will give you the conditional risk of your estimator (conditional on the training data $X_i$), while case (b) corresponds to training on completely independent data, and will allow an estimate of the average risk of your estimator (averaging over the distribution of the training data and test data).

Now for both cases (a) and (b) you can just invoke empirical process theory to establish that the empirical distribution of $L(T_i, Y_k)$ will converge to its true distribution over independent training and test samples, with the rate of convergence given by standard results on the empirical process.

To make this concrete, suppose that $L(T_i, Y_k)$ is zero-one loss, and we are operating under scenario (a). Then we'd have that $L(T_i, Y_k)$ is just the average mis-classification in training set $k$, and for every mis-classification rate $p$, the distribution of $L(T_i, Y)$ (loosely speaking) converges pointwise to a $$N\left(\hat F(p), \frac{\hat F(p)(1-\hat F(p))}{\sqrt n }\right),$$ distribution, where $\hat F(p)$ is the empirical distribution function of the average misclassification. Note that there are some simplifications that you can exploit in the linearity of the training loss $L(T_i, Y_k)$ in observations $Y$ to reduce the previous display to something prettier, I think.

So you can see the flavor of this analysis ends up looking like confidence intervals on Binomial variables, because we are converging to something with a variance equal to $p(1-p)/\sqrt n$. But it also would generalize to other losses, like your Rijsbergen's F-measure.

What's missing

There are (at least) two missing pieces to this. First, it's almost certain that you don't have enough data to want to employ the somewhat absurd cross-validation procedure suggested in (a) and (b). So instead, your training samples and estimators $T_i$ are going to be dependent, and I think that in general it is not possible to estimate the amount of dependence. Cross validation, in general, does something that ends up being a mix of procedures (a) and (b). Section 7.10 in "Elements of Statistical Learning" provides a good discussion on this point. I am pessimistic that that's any solution to be found to this.

Secondly, I just gave you an asymptotic result, but if the amount of independent test data $Y$ is small, then the asymptotics will be doubtful. This is how I'd translate your concern about plugging in the estimate for $p$. For this, it seems intuitively likely that you should be able to account for the uncertainty in the plug-in estimate through some sort of monte carlo procedure. Like cross-validation nested within a bootstrap? Or vice-versa?