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