Cross-validation or bootstrapping to evaluate classification performance?

Question

What is the most appropriate sampling method to evaluate the performance of a classifier on a particular data set and compare it with other classifiers? Cross-validation seems to be standard practice, but I've read that methods such as .632 bootstrap are a better choice.

As a follow-up: Does the choice of performance metric affect the answer (if I use AUC instead of accuracy)?

My ultimate goal is to be able to say with some confidence that one machine learning method is superior to another for a particular dataset.

Answer 1

One important difference in the usual way cross validation and out-of-bootstrap methods are applied is that most people apply cross validation only once (i.e. each case is tested exactly once), while out-of-bootstrap validation is performed with a large number of repetitions/iterations. In that situation, cross validation is subject to higher variance due to model instability. However, that can be avoided by using e.g. iterated/repeated $k$-fold cross validation. If that is done, at least for the spectroscopic data sets I've been working with, the total error of both resampling schemes seems to be the same in practice.

Leave-one-out cross validation is discouraged, as there is no possibility to reduce the model instability-type variance and there are some classifiers and problems where it exhibits a huge pessimistic bias.

.632 bootstrap does a reasonable job as long as the resampling error which is mixed in is not too optimistically biased. (E.g. for the data I work with, very wide matrices with lots of variates, it doesn't work very well as the models are prone to serious overfitting). This means also that I'd avoid using .632 bootstrap for comparing models of varying complexity. With .632+ bootstrap I don't have experience: if overfitting happens and is properly detected, it will equal the original out-of-bootstrap estimate, so I stick with plain oob or iterated/repeated cross validation for my data.

Literature:

• Kohavi, R.: A Study of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selection Artificial Intelligence Proceedings 14th International Joint Conference, 20 -- 25. August 1995, Montréal, Québec, Canada, 1995, 1137 - 1145.
  (a classic)

Dougherty and Braga-Neto have a number of publications on the topic, e.g.

• Dougherty, E. R. et al.: Performance of Error Estimators for Classification Current Bioinformatics, 2010, 5, 53-67

• Beleites, C. et al.: Variance reduction in estimating classification error using sparse datasets Chemom Intell Lab Syst, 2005, 79, 91 - 100.
  We have a comparison of doing cross validation only once or iterating/repeating, and compare that with out-of-bootstrap and .632 bootstrap as well for particularly wide data with multi-collinearities.

• Kim, J.-H.: Estimating classification error rate: Repeated cross-validation, repeated hold-out and bootstrap, Computational Statistics & Data Analysis , 2009, 53, 3735 - 374
  Also finds that repeated/iterated $k$-fold cross validation and out-of-bootstrap have similar performance (as opposed to doing the cross validation only once).

Choice of metric:

• accuray (of which @FrankHarrell will tell you that it is a bad choice as it is not a proper scoring rule) is subject to high variance because it counts each case either as completely correct or completely incorrect, even if the classifier predicted e.g. only 60 % posterior probability for the test case to belong to the class in question. A proper scoring rule is e.g. Brier's score, which is closely related to mean squared error in regression.

• Mean square error analoga are available for proportions like accuracy, sensitivity, specificity, predictive values: Beleites, C. et al.: Validation of soft classification models using partial class memberships: An extended concept of sensitivity & Co. applied to grading of astrocytoma tissues, Chemom Intell Lab Syst, 2013, 122, 12 - 22; DOI: 10.1016/j.chemolab.2012.12.003 (summary page giving link to preprint as well)

My ultimate goal is to be able to say with some confidence that one machine learning method is superior to another for a particular dataset.

• Use a paired test to evaluate that. For comparing proportions, have a look at McNemar's test.

• The answer to this will be affected by the choice of metric. As regression-type error measures do not have the "hardening" step of cutting decisions with a threshold, they often have less variance than their classification counterparts. Metrics like accuracy that are basically proportions will need huge numbers of test cases to establish the superiority of one classifier over another.

Fleiss: "Statistical methods for rates and proportions" gives examples (and tables) for unpaired comparison of proportions. To give you an impression of what I mean with "huge sample sizes", have a look at the image in my answer to this other question. Paired tests like McNemar's need less test cases, but IIRC still in the best case half (?) of the sample size needed for the unpaired test.

• To characterize a classifier's performance (hardened), you usually need a working curve of least two values such as the ROC (sensitivity vs. specificity) or the like.
  I seldom use overall accuracy or AUC, as my applications usually have restrictions e.g. that sensitivity is more important than specificity, or certain bounds on these measures should be met. If you go for "single number" sum characteristics, make sure that the working point of the models you're looking at is actually in a sensible range.

• For accuracy and other performance measures that summarize the performance for several classes according to the reference labels, make sure that you take into account the relative frequency of the classes that you'll encounter in the application - which is not necessarily the same as in your training or test data.

• Provost, F. et al.: The Case Against Accuracy Estimation for Comparing Induction Algorithms In Proceedings of the Fifteenth International Conference on Machine Learning, 1998

---

edit: comparing multiple classifiers

I've been thinking about this problem for a while, but did not yet arrive at a solution (nor did I meet anyone who had a solution).

Here's what I've got so far:

• The problem is that you run very swiftly into into massive multiple comparison situation.

• However, you may say that for the applications I have at hand, multiple comparisons is not really making things any worse, because I rarely have enought test cases to allow even a single comparison...

• I think tuning of model hyperparameters is a specialized version of the general model comparison problem, which may be easier to tackle for a beginning. However, there are rumours that the quality of models depends much on the expertise of the one who builds them, possibly even more so than on the choice of model type

For the moment, I decided that "optimization is the root of all evil", and take a very different approach instead:
I decide as much as possible by expert knowledge about the problem at hand. That actually allows to narrow down things quite a bit, so that I can often avoid model comparison. When I have to compare models, I try to be very open and clear reminding people about the uncertainty of the performance estimate and that particularly multiple model comparison is AFAIK still an unsolved problem.

---

Edit 2: paired tests

Among $n$ models, you can make $\frac{1}{2} (n^2 - n)$ comparisons between two different models (which is a massive multiple comparison situation), I don't know how to properly do this. However, the paired of the test just refers to the fact that as all models are tested with exactly the same test cases, you can split the cases into "easy" and "difficult" cases on the one hand, for which all models arrive at a correct (or wrong) prediction. They do not help distinguishing among the models. On the other hand, there are the "interesting" cases which are predicted correctly by some, but not by other models. Only these "interesting" cases need to be considered for judging superiority, neither the "easy" nor the "difficult" cases help with that. (This is how I understand the idea behind McNemar's test).

For the massively multiple comparison between $n$ models, I guess one problem is that unless you're very lucky, the more models you compare the fewer cases you will be able to exclude from the further considerations: even if all models are truly equal in their overall performance, it becomes less and less likely that a case ends up being always predicted correctly (or always wrongly) by $n$ models.

Answer 2

You need modifications to the bootstrap (.632, .632+) only because the original research used a discontinuous improper scoring rule (proportion classified correctly). For other accuracy scores the ordinary optimism bootstrap tends to work fine. For more information see this.

Improper scoring rules mislead you on the choice of features and their weights. In other words, everything that can go wrong will go wrong. For more see this.

Answer 3

From 'Applied Predictive Modeling., Khun. Johnson. p.78

"No resampling method is uniformly better than another; the choice should be made while considering several factors. If the sample size is small, we recommend using repeated 10-fold cross validation for several reasons; the bias and variance properties are good, and given the sample size, the computational costs are not large. If the goal is to choose between models, as opposed to getting the best indicator of performance, a strong case can be made for using one of the bootstrap procedures since these have very low variance. For large sample sizes, the differences between resampling methods become less pronounced, and computational efficiency increases in performance." p. 78

In addition, given the choice of two similar results, the more interpretable model is generally preferred. As an example (from the same text), using 10 fold CV, a SVM classifier had a 75% accuracy estimate with resample results between 66 and 82%. The same parameters were used on a logistic regression classifier with 74.9% accuracy, and same resample range. The simpler logistic regression model might be preferred as it is easier to interpret results.