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.

up vote 38 down vote accepted
+50

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.

Choice of metric:

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:

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.

  • Thanks for you detailed answer! I'd really appreciate if you could elaborate on the point you made: "Use a paired test to evaluate that. For comparing proportions, have a look at McNemar's test." I should slightly rephrase my question: I would like to compare several machine learning methods at once, not necessarily just pairs. It's not immediately clear to me how paired tests could accomplish this. – kelvin_11 Sep 26 '13 at 22:31
  • 3
    (+6) Nice response. – chl Sep 28 '13 at 21:05
  • @cbeleites I love you for this comment. For the significance of multiple model comparison - what about analysis of variance (ANOVA) methods? such as Kruskal–Wallis ? – Serendipity Jan 21 '16 at 17:24
  • @Serendipity: I really don't know enough about Kruskal-Wallis to give you an answer here. But I suspect that ANOVA-like methods are not what is wanted here as (1) it doesn't use the paired nature of the data and (2) it gains power compared to the multiple comparisons because the null hypothesis is just "all models perform equally" - if that is rejected, you still don't know which algorithm(s) performs differently. So it can only be used to emphasize negative results (it doen't matter which algorithm you choose). I'd suspect that there is a large zone where ANOVA tells you not all models ... – cbeleites Jan 22 '16 at 10:12
  • ... are equal but you do not have enough information to allow the multiple comparisons that are needed for identifying better models. – cbeleites Jan 22 '16 at 10:15

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 http://biostat.mc.vanderbilt.edu/RmS#Studies_of_Methods_Used_in_the_T

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

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.

  • 3
    Note that the variance you can reduce by running large numbers of bootstrap / cross validation iterations/repetitions is only the part of variance that comes from instability of the surrogate models. You can measure whether this is a major contribution to the total variance by cross validation as it tests each sample exactly once during each run, so the variance due to finite sample size does not show up in the comparison of the averages of complete cross validation runs. For "hard" classification, you can calculate the variance due to the finite sample size from the binomial distribution. – cbeleites Sep 26 '13 at 21:12
  • @cbeleites: Can you please explain a bit what you mean by "it tests each sample exactly once during each run, so the variance due to finite sample size does not show up in the comparison of the averages of complete cross validation runs." (references are fine too!) (+1 clearly) – usεr11852 Mar 7 '17 at 0:20
  • @usεr11852: each case is tested exactly once per cross validation run. Imagine a table of n_sample x r CV run results. If we have stable predictions, all r predictions for the same case are the same. I.e. there is no variance along the rows. But different cases may get different predictions (unless we have e.g. 100% accuracy): we have variance along the colums. Now the standard evaluation of iterated/repeated cross valiation is to compare the column averages. For stable models, these are exactly the same, even though we do have variance along the columns, i.e. between the cases. – cbeleites Mar 7 '17 at 20:04
  • (If the models/predictions are unstable, we do get different predictions by different surrogate models, and see variance along the rows as well. Plus some additional variance along the columns, as each column in k-fold CV covers k different surrogate models.) So for measuring model/prediction (in)stability, it is maybe even more direct to go directly for the variance along the rows, i.e. variance of the predictions of different surrogate models for the same case. – cbeleites Mar 7 '17 at 20:08
  • 1
    @cbeleites:Thank you very much for the clarification. I can now appreciate the point you are making more. – usεr11852 Mar 7 '17 at 20:10

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.