Checking whether accuracy improvement is significant

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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 
                  0.81 

(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)
          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")

Answer 4

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.