# Advice on resampling scheme for a small sample/ costly computation situation?

I am testing combinations of preprocessing activities on a small data set (n=48, p=30). The script generates 3200 different versions of the original data and measures how they perform in a classification task against 5 classifiers. Classifier parameters are tuned with 10 times bootstrap.

I assume a good sampling scheme would be to repeat 10-fold cross-validation 10 times, but this is computationally too much, at least for my resources:

• 3200 times
• 10 * 10 (cross-validation)
• for each round tune and train the five models 10 * 5

The idea at this moment is to

1. For each data version
2. Tune the models' parameters with 10 times bootstrap sample (2/3 tuning set - 1/3 tuning test set)
3. Train the models with new bootstrap sample given the parameters
4. Test the learned models by taking 3/3 bootstrap repeated 100 times

This is a rather complicated sampling scheme and mixes training and test sets.

What would be a good yet computationally feasible sampling scheme in this situation?

• I think we'd need to know a bit more about your application: what exactly does "generate 3200 versions of the original data mean and why do you want to compare them? – cbeleites supports Monica Jan 23 '14 at 10:05
• Also: what exactly do you mean by 3/3 bootstrap? – cbeleites supports Monica Jan 23 '14 at 10:06
• Thank you for your extensive comments and help. It is evident that I need to study this topic much more. – user2968765 Jan 23 '14 at 13:20
• The application combines preprocessing activities: sampling, imputation, smoothing, scaling, outlier detection and feature selection. An example line could be: over-sample the smallest class, omit NA's, scale min-max, do not remove outliers and do feature ranking by correlation. The aim is to find out, what is the best preprocessing combination for classification task in that particular data. The aim is not to evaluate classifiers. BY 3/3 bootstrap I meant taking the complete data and sampling it with replacement (sample size equals number of rows in the data). – user2968765 Jan 23 '14 at 13:34
• BY 3/3 bootstrap I meant taking the complete data and sampling it with replacement (sample size equals number of rows in the data): but then on what data do you propose to train? On the left-out cases that would be an "inverted" out-of-bootstrap validation - probably terribly inefficient as you'd train on roughly 1/3 of the data only. By the way: welcome to cross validated! – cbeleites supports Monica Jan 23 '14 at 13:37

Cross-validation is a better idea for parameter tuning than using bootstrap samples. So why not replace your bootstrap approach for tuning with 10-fold cross-validation?

It's computational cost is comparable since you need to train 10 models in each. The CV-models will have slightly more training instances so computational time will be a bit higher but probably negligible.

• Care to explain why cross validation is better? After all, the total error on the performance estimate is comparable (possibly in the context of comparison, out-of-bootstrap is better because of lower testing variance), and for n=48 cases the testing uncertainty will probably overwhelm the slope of the learning curve. Also the possible bias of the bootstraped version towards less complex models (being the optimum for fewer training cases) may be seen as a slight counteracting effect to the overfitting bias due to picking the seemingly best model. – cbeleites supports Monica Jan 23 '14 at 15:14
• @cbeleites you are right, I had not considered the small sample size when writing my answer (which is why I upvoted yours). Outside of small-sample settings, cross-validation is the weapon of choice for tuning all classification approaches I use often. – Marc Claesen Jan 23 '14 at 16:16

I think a key point here is to realize that from a statistical point of view you are testing lots of hypoteses of "difference in performance".

• I think the step point should be to step back and check whether you can possibly get a sensible answer from all these calculations.
You say you want to compare 5 models $\times$ 3200 data sets (not sure whether I understood correctly how exactly you want to compare). That is a huge number of comparisons.
If you think in terms of correct/wrong predictions (i.e. dichotomized outcome as opposed to looking at continuous scores): what order of magnitude of difference in the performance do you expect?

McNemar's test looks at the numbers of cases misclassified by model A but not by model B ("b") compared to the number of cases misclassified by B but not by A ("c"): only those cases show differences between the models. Here's a plot of the $p$ values for different combinations:

Note that this applies to a single comparison.
So even in best case you need a difference of at least 12.5 % (0 vs. 6 cases) for a single comparison of the proportion-type performance you are looking at.

• Keep in mind that also a optimization of the type "pick the hyperparameters that gave maximum observed performance in the tuning tests" is a massive multiple comparison situation in the sense outlined above. In other words, you have hardly any chance here to do a meaningful optimization, you will only "skim" the testing variance.

As @DikranMarsupial says: Optimization is the root of all evil in statistics.

If at all possible, I'd recommend to avoid the optimization and instead fix the hyperparameters by your knowledge about the application, the data and the classifier. If your classifier doesn't allow you to do that, use another that is more suitable in that respect.
In the light of the McNemar thoughts above, unless you think that your hyperparameters may lead to far worse predictions than the truely optimal hyperparameters (far worse meaning e.g. 20 % misclassifications instead of 2 %) there is no need to worry here.

• If you still insist on tuning: Even if you have to report the final performance with proportion-type characteristics (% correct classified, sensitivtity, specificity, predictive values, ...) make sure that for the tuning you use a proper scoring rule, e.g. Brier's score. This has 2 advantages:

• they react continuously and thus are sensitive to small changes in the performance that the proportions cannot detect
• they typically have lower variance

The harder you optimize (the more models are compared during tuning), the more likely you are to overfit during the tuning step. The proper scoring rules can somewhat mitigate this. But again, they won't work miracles.

• Some arguments for doing a rather low number of iterations for the outer validation of the tuned model: Consider $i \times$ $k$-fold cross validation. In each of the $i$ runs, each case is tested exactly once. Thus the variance you observe over the $i$ runs is due to model instability. So measure the stability of the predictions with rather small $i$.

• If the variance is $\ll$ the variance due to a finite number of 48 test cases, there is no need for further iterations.
With a true e.g. correct classification rate of $p = 90 \%$, you get $\sigma ( \hat p) = \sqrt{\frac{p (1 - p)}{n}} \approx 4 \%$
• If the variance is high, your models are unstable. Which also means that most likely your optimization failed (check whether the chosen hyperparameters are stable). Do you relly need a good estimate of the performance when you know your modeling strategy failed?
• Also, I'd go for 6-fold cross validation here: if your models are much worse when trained on 40 cases as opposed to train on 43 cases, you are in trouble anyways.

What ever you do for the training, it is of utmost importance that the finally chosen model is validated by independent test cases:

• all kinds of preprocessing that calculate on more than one case, e.g. calculating the mean for centering, doing a PCA projection etc.
• all kinds of data-driven optimization like feature selection need to be re-calculated as part of the training for each of the resampling surrogate models.
• IMHO there are very few exceptions to this. One would be if you refrain from selecting a final model.

I work with vibrational spectra. For that type of data, a number of sensible pre-processing alternatives exist.

In my experience, which of the alternatives is chosen often has a surprisingly low influence on the predictive performance of the model.

• If you read German, I could give you my Diplomarbeit which shows that (though not looking at interactions).
• You can also look at Engel et al.: Breaking with trends in pre-processing? , TrAC Trends in Analytical Chemistry , 50, 96 - 106 (2013). DOI: 10.1016/j.trac.2013.04.015
They observe something like 93% accuracy for their best combination of pre-processing methods compared to ca. 88% without pre-processing.

A quick simulation of "best of 4912 tests with 267 cases $\times$ randomly predicting 83% correct" gives me almost always (> 99% of the runs) a best observed performance of 90 % or better, and in almost 1% of the runs 93% or better. Which underlines their message that choosing a good pre-processing strategy is not a trivial task at all also from a statistical point of view. (The simple simulation is just a very rough approximation to whether the observed difference in performance is significant: I model an unpaired comparison of independent outcomes, which is not the case for their data points).

• I'd recommend to run some Null hypothesis simulation/permutation test also for your data.

• Yes, I agree, the scheme is too complex and mixes train/test sets to deliver any sensible answer. I can skip the optimization of model parameters for each data version and use parameters that were found from the original, unprocessed data (or minimally processed). – user2968765 Jan 23 '14 at 13:56
• Well, no: then your test data contributed to the optimization, and you end up with an optimistically biased performance estimate. Depending on how aggressively this optimization is done, I've seen the hit rate dropping for a proper validation from seeming > 95 % to 60% (for a rather aggressive optimiztation scheme) or, for "mild dependence" from say, 95 % to 85% or so (that would be quite typical with our data). – cbeleites supports Monica Jan 23 '14 at 14:42