Suppose I have an algorithm that classifies things into two categories. I can measure the accuracy of the algorithm on say 1000 test things -- suppose 80% of the things are classified correctly.

Lets suppose I modify the algorithm somehow so that 81% of things are classified correctly.

Can statistics tell me anything about whether my improvement to the algorithm is statistically significant? Is the concept of statistical significance relevent in this situation? Please point me in the direction of some resources that might be relevant.

Many Thanks.


In short, yes. Statistical significance is relevant here. You are looking at the classification error (or, as you give it here accuracy = 1- classification error). If you compare the classificators on different 1000 samples you can simply use the binomial test, if it is the same 1000 samples you need to use McNemar's test. Note that simply testing the classification error in this way is suboptimal because you either assume the classification error is independent of the true class or that the proportion of the true classes is the same across your potential applications.

This means you should take a look at measures like true positive rate, false positive rate or AUC. What measure to use and how to test it, depends on the output of your classicator. It might just be a class or it might be a continous number giving the probability of belonging to a certain class.

  • $\begingroup$ Thats great, thanks. I'm actually looking at sentiment analysis of text documents - classifying them into "positive" or "negative" - there is a lot of work published where people alter the feature selection in some subtle way, with say 1% accuracy improvement - and write a paper about this. I'm wondering whether in many of these cases the authors have failed to give evidence for a statistically significant improvement in classification accuracy. $\endgroup$ – Ben Apr 18 '12 at 13:50
  • $\begingroup$ McNemar's test tells you whether the models are significantly different, which does not always imply the difference in accuracy is significant (different models can have the same accuracy). To check significance of the accuracy increase directly, you'd want to make many accuracy estimates to map the distributions of accuracies and thus estimate if they are different. This would mean training your models multiple times. $\endgroup$ – drevicko May 12 at 20:52

As Erik said, yes you can check this for statistical significance. However, think for a moment exactly what it is you want to check. I think a more interesting question might be to ask how likely it is that the allegedly "improved" algorithm is better (or meaningfully better) than the original, given the data of an observed 1% difference. Asking questions in terms of "statistical significance" tends to lead to the opposite type of question: Given that the two algorithms are the same, is there less than a 5% chance observing an improvement of at least this much?

To me, the latter question is backwards, but it has somehow become the standard. You can check out Wikipedia on the controversy in statistical hypothesis testing. You might subsequently be interested in Bayesian inference. If you really want to get into Bayesian data analysis, you can check out Gelman et al's "Bayesian Data Analysis" or check out this question.


Applying Erik's answer to Michael's:

You can do the same kind of thinking Erik refers to when choosing the performance measure.

I find it helpful to refer to different such measures by the questions they answer (here in the medical diagnostics language which I'm most familiar with - but maybe you can just replace patient by text and disease by spam ;-) ):

  • Sensitivity: given the patient truly has the disease, how likely is the classifier to realize that?

  • Specificity: given the patient truly does not have the disease, how likely is the classifier to realize that?

  • Positive predictive value: given the classifier claims the patient to be diseased, how likely does the patient really have the disease?

  • Negative predictive value: given the classifier claims the patient not to be diseased, how likely does the patient really doesn't have the disease?

As you see, the predicitive values are what doctors and patients are really interested in. However, almost everyone characterizes his classifier by sensitivity and specificity. The reason is that the predictive values need to take the prevalence of the disease into account, and that can vary hugely (orders of magnitude!) for different kinds of patients.

More on topic for your question:

I bet you are right in worrying.

Taking both of Erik's scenarios into an example:

Here are the independent test samples:

> binom.test (x = 810, n = 1000, p = 0.8)

    Exact binomial test

data:  810 and 1000 
number of successes = 810, number of trials = 1000, p-value = 0.4526
alternative hypothesis: true probability of success is not equal to 0.8 
95 percent confidence interval:
 0.7842863 0.8338735 
sample estimates:
probability of success 

(note that this test was two-sided, assuming the two classifiers would have been published even if the results had been the other way round...)

Here's the best possible situation: paired test, and the new classifier is right for all samples the old one is right, too plus 10 more:

> ## mc.nemar: best possible case
> oldclassif <- c (rep ("correct", 800), rep ("wrong", 200))
> newclassif <- c (rep ("correct", 810), rep ("wrong", 190))
> table (oldclassif, newclassif)
oldclassif correct wrong
   correct     800     0
   wrong        10   190
> mcnemar.test (oldclassif, newclassif)

    McNemar's Chi-squared test with continuity correction

data:  oldclassif and newclassif 
McNemar's chi-squared = 8.1, df = 1, p-value = 0.004427

(the p-value stays below the magical 0.05 as long as not more than 10 samples out of the 1000 were predicted differently by the two classifiers).

Even if p-values are the right answer to the wrong question, there's indication that it's kind of a tight place.

However, taking into account the usual scientific practice i.e. an unknown (unpublished) number of new features was tested, and only the one that worked slightly better was published, the place gets even more tight. And then, the 80 % classifier may just be the successor of some 79 % classifer...

If you enjoy reading German, there are some really nice books by Beck-Bornhold and Dubben. If I remember correctly, Mit an Wahrscheinlichkeit grenzender Sicherheit has a very nice discussion of these problems. (I don't know whether there is an English edition, a rather literal translation of the title is "With a certainty bordering on probability")


I would highly discourage the use of any discontinuous improper scoring rule (an accuracy score such as sensitivity, specificity, proportion classified correct that when optimized results in a bogus model) and instead use likelihood ratio tests or partial F tests for added value of the new variables.

One of several ways to see the problems with proportion classified correctly is that if the overall proportion in one category is 0.9 you will be correct 0.9 of the time by ignoring the data and classifying every observation as being in that category.

  • 2
    $\begingroup$ Yes sometimes accuracy is a lousy metric to use, and sometimes it's a terrific method; it depends. That seems to be completely tangential to what the question is about though. The question is about determining whether a new algorithm is better according to a known metric, not about picking a metric in the first place. $\endgroup$ – Michael McGowan Apr 22 '12 at 5:11
  • $\begingroup$ I think that we need to carefully describe goals and utility functions, and if we don't want to provide utility functions we need to backsolve for the utility function that is effectively being assumed when classification is performed. $\endgroup$ – Frank Harrell Apr 22 '12 at 13:25
  • $\begingroup$ Any reason for so much anonymous downvotes? $\endgroup$ – chl May 10 '12 at 10:13
  • 2
    $\begingroup$ @chl I thought I explained that I downvoted for not really answering the question that was asked. $\endgroup$ – Michael McGowan May 13 '12 at 0:40
  • $\begingroup$ @MichaelMcGowan Fair enough. $\endgroup$ – chl May 13 '12 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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