Does the central limit theorem hold for the prediction error over different samples?

Given an (infinite) data population from which you repeatedly draw samples of a fixed size. On each sample you learn a classifier which you then evaluate by computing the prediction error on a large independent test set. The prediction error is defined as the average over all instances in the test set of the zero-one loss function $\mathcal{L}(y,\hat{y})$. (The zero-one loss function $\mathcal{L}(y,\hat{y})=0$ if the predicted label $\hat{y}$ of an instance equals the true label of the instance y, and is 1 otherwise.)

My question is whether the central limit theorem holds in this situation, so that the distribution of the prediction error over the samples approximates a normal distribution, given a sufficient number of samples?

I know that the theorem holds for a sufficiently large number of independent random variables. So I am in doubt because the individual predictions for one test set originate from the same classifier, and the classifiers vary over the samples.

• (1) Is the "large independent test set" the same for each sample or does it also vary from sample to sample? In the first case all evaluations of prediction error will be correlated, whereas in the second case they will be independent. (2) How are you presuming to apply the CLT here? The only correct way I can conceive of is to let the sample sizes grow large. The CLT says nothing about what happens when you just take more and more samples. – whuber Sep 14 '17 at 20:18

Your scenario is idealized, in reality you will not have infinitely many records with labels so that you can draw 30 training sets and 30 test sets each of ample size and such that no records overlap between any of the 60 sets. You need 30 of each because in addition to the independence issue, you also cannot assume a normal distribution of classification performance measures. With 30 i.i.d. measures of any distribution though, you're good.

You could always divide your existing data-set with $n$ records into 60 such sets though. The classification performance measures (of which you have one value per test-set) would then be independent across test-sets making the central limit theorem applicable which means you can basically use t-tests to compare classifier performance. Let's see how that plays out.

For simplicity, say you have only 2 classes. Your classification algorithm needs 100 records per class in the training set to adequately learn to recognize a class. That's already $30*2*100=6000$ training records.

Regarding test sets, you also need enough records per class per test set. The reason for this is different though. Your 0-1 loss function can be transformed into an accuracy score between 0 and 1 on each test set. (You could also leave it as a loss function, but then you need to have test sets of exactly the same size because sets with fewer records need to show fewer misclassifications to have the same actual classifier performance. Therefore, better express it as a standardized accuracy rating. Or perhaps an F-measure if mis-classification costs are imbalanced.) In any case, the measures based on such 0-1 loss outcomes can only be seen as interval variables (continuous variables that can take (almost) any value on a given scale) if they are based on many 0-1 loss decisions. You need interval variables to do the t-tests that your question is obviously aimed at. So you need say 100 records of each class in each training set. 100 is not a hard limit here, but if you have too few records you are not justified doing t-tests and are stuck with low power McNemar tests that are non-parametric and therefore difficult to aggregate (Ditterich, 1988). This makes for another 6000 test records and 12000 records in total.

To your last question: depending on what you mean with "classifier", you might be confusing independence with identical distribution here (and you need both, hence i.i.d.). If by "classifier" you mean "classification algorithm", then don't worry about using the same classification algorithm for all training- and test sets. On the contrary, if you used $k$NN on one traning-test combination, neural nets on the second, logistic regression on the third etc. you would be producing measures that are not identically distributed. Each training-test combination would be based on a different algorithm, some of which are better than others. In such a scenario, it would also be impossible to compare the performance of two algorithms each run on the same number of training-test set combinations.

If by "classifier" you mean, "classifier model based on specific algorithm as applied to training data", then you will have a different classifier for each training set as you should. They will produce independent performance measures if the training- and test sets don't overlap, which you made sure is the case by dividing your data set into 60 parts.

In conclusion, your approach is statistically sound. But it's not the most practical. Even with perfectly balanced binary classes, you need 12k records based on my assumptions (which I think are on the lower end). With 10 perfectly balanced classes, you would need 72k records. If classes are unbalanced, you still need enough records of the smallest class which further increases the required data set size. You need to make the 60 subsets randomly out of your data set without forcing uniform class distribution in all 60 via stratification (otherwise independence would be questionable). So some will have fewer records of some classes than some other subsets, better raise the total number of $n$ to compensate for that as well.

Many data sets are not that large, but even if they were, your approach wouldn't be the best use one can make of them. The same (Ditterich, 1988) paper rules out two common practices. You cannot repeatedly divide your data set into training and test data so that each training-test split covers the entire data-set. Even if you do that 30 times, the 30 test set performance measures you obtain are not independent (training- and test sets overlap). A similar objection is made to cross validation, here only the training sets overlap, but still.

In the meantime, progress has been made, (Nadeau and Bengio, 1999) found a way to correct for the fact that training sets overlap in a cross validation (and also for the fact that test sets overlap in a repeated cross validation). Those corrected resampled t-tests satisfy all the assumptions of the t-test if you have at least 30 measures (typically 3 repetitions of 10 fold CV). They can be used on much smaller data-sets than your approach because they don't need so many totally distinct subsets in the data-set. Applied to the same sufficiently large data-set, corrected resampled t-tests still have the advantage of constructing better classifiers based on more records than your approach does.