Evaluating Classifiers

This builds on Naive Bayes and Sentiment Classification, which trained a classifier that labels documents. Having a classifier is not the same as knowing it works. This lesson answers two questions that apply to any classifier in the module: how good is it, and — when a new model beats the old one — is the improvement real or an accident of the test set?

The confusion matrix

A trained classifier is worthless until we can say how good it is. Start with a binary detection task — spam vs. not-spam, or tweets about our pie vs. everything else — and the human-assigned truth we compare against, the gold labels.

Cross-tabulate what the system said against the gold truth and you get a confusion matrix. Each cell counts one kind of outcome: true positives (system says positive, gold agrees), false positives (system says positive, gold disagrees), false negatives (system misses a real positive), true negatives (both say negative).

The obvious metric, accuracy — the fraction of all items labeled correctly — is misleading on unbalanced data. Take a million tweets, only $100$ of them about our pie. A classifier that labels everything not about pie scores $999,900/1,000,000=99.99\%$ accuracy while finding not one of the comments we care about. When the classes are unbalanced — as spam, or about pie, always are — accuracy rewards ignoring the rare class.

Precision, recall, F1

Two metrics repair this by focusing on the positive class. Precision is the fraction of the items the system called positive that really are positive — how much to trust a positive verdict:

Recall is the fraction of the items that really are positive that the system found — how much it misses:

The nothing is pie classifier now scores a recall of $0/100=0$: precision and recall both hinge on true positives, so neither can be gamed by ignoring the rare class. They trade off — a system can raise recall by labeling everything positive (at very low precision), or raise precision by labeling only its surest cases (at very low recall) — so we want a single number combining both. That is the F-measure, the weighted harmonic mean of precision and recall:

The parameter $\beta$ tilts the balance: $\beta >1$ favors recall, $\beta <1$ favors precision. With $\beta =1$ the two weigh equally, giving the standard $F_1$:

The harmonic mean (not the plain average) is deliberate: it sits closer to the smaller of the two values, so a system cannot post a high $F_1$ by excelling at one metric while failing the other. Both precision and recall must be respectable to score well.

For example, say a spam filter flags $40$ messages, of which $30$ are truly spam (so $10$ are false alarms), and it misses $20$ real spam messages it should have caught. Then precision is $P=30/40=0.75$ and recall is $R=30/(30+20)=0.60$. The plain average would be $0.675$, but the harmonic mean pulls toward the weaker number: $F_1=2(0.75)(0.60)/(0.75+0.60)=0.667$. Push recall down to $0.20$ while holding precision at $0.75$, and the plain average is still a respectable $0.475$, but $F_1$ collapses to $0.316$ — the harmonic mean does not let strong precision compensate for weak recall.

More than two classes: macro vs. micro averaging

Sentiment often has three classes (positive, negative, neutral), and tasks like part-of-speech tagging have dozens. Naive Bayes is already multi-class — nothing in the arg-max depends on $|C|=2$ — but precision and recall need extending. Compute them per class (treat that class as positive, all others as negative), then combine the per-class numbers in one of two ways.

Macroaveraging computes precision (and recall) separately for each class, then averages those numbers, weighting every class equally. Microaveraging pools all classes' decisions into a single confusion matrix and computes one precision from the totals. The two answer different questions. A microaverage is dominated by the frequent class — if spam vastly outnumbers the others, spam's performance swamps the pooled count. A macroaverage gives a small, rare class the same vote as a big one, so it better reflects performance when every class matters equally.

Cross-validation

We train on a training set, tune on a development test set (devset), and report final numbers on a held-out test set the model has never seen — tuning on the test set would overfit it and inflate the score. But carving out fixed dev and test sets removes data from training, and a small fixed test set may not be representative.

Cross-validation uses all the data for both. Partition it into $k$ disjoint folds; hold out one fold as the test set, train on the other $k-1$, record the score; repeat with each fold as the held-out set in turn; average the $k$ scores. With $k=10$ this is 10-fold cross-validation — ten models, each trained on $90\%$ of the data and tested on the remaining $10\%$.

Cross-validation uses the whole corpus for testing, which means we can never look at the data to understand it or design features without peeking at the test set. The common compromise is to fix a small test set once, then run cross-validation inside the remaining training data.

Statistical significance testing

Suppose you build a new classifier and it scores higher than the old one on the test set — logistic regression's $F_1$ beats naive Bayes' by $0.04$. Is the new system really better, or did it just get lucky on this particular test set?¹Statistical hypothesis testing answers this, and no comparison of two systems is complete without it.

Write $M(A,x)$ for the score system $A$ earns on test set $x$ under some metric $M$ (accuracy, $F_1$, BLEU — anything). The quantity we care about is the performance difference between $A$ and $B$ on that test set:

This $\delta (x)$ is the effect size: a large $\delta$ says $A$ looks far ahead of $B$, a small one that it barely edges it out. We would like $\delta (x)>0$, but observing a positive $\delta$ on one test set is not enough. $A$ might be accidentally ahead on this $x$ and behind on the next. We want to know whether $A$'s lead would persist on some other test set $x^{\prime }$ drawn from the same source.

The null hypothesis and the p-value

Hypothesis testing formalizes this with two competing claims:

The null hypothesis $H_0$ supposes $A$ is not actually better than $B$ — that the observed lead is an accident of this test set. The goal is to rule $H_0$ out with enough confidence to accept $H_1$, that $A$ genuinely wins.

To do so, imagine a random variable $X$ ranging over all possible test sets and ask: if $H_0$ were true, how often would we see a difference as large as the $\delta (x)$ we actually observed? That probability is the p-value:

Read it carefully — it is the probability of seeing our result, or a more extreme one, under the assumption that $A$ is no better than $B$. A huge observed $\delta$ (say $A$ scores $0.9$ and $B$ scores $0.2$) would be astonishing if $H_0$ held, so its p-value is tiny. A small $\delta$ is unsurprising even under $H_0$, so its p-value is large. When the p-value falls below a threshold — commonly $0.05$ or $0.01$ — we reject the null hypothesis and call the result statistically significant.

In NLP we rarely compute the p-value with parametric tests like the $t$-test, because those assume the test statistic is normally distributed and that assumption does not hold for our metrics. Instead we use non-parametric tests based on sampling: artificially manufacture many versions of the test set and read the distribution of $\delta$ off them directly. The two common choices are approximate randomization and the bootstrap test. Both are usually run in a paired form, comparing $A$ and $B$ on the same items so each of $A$'s per-item results lines up with $B$'s.

The paired bootstrap test

The bootstrap test applies to any metric and rests on one idea: bootstrapping — repeatedly drawing samples with replacement from the observed test set to fabricate many virtual test sets.² The only assumption is that the original test set is representative of the population. Each virtual test set is a plausible alternative sample, and across thousands of them we can measure how often $A$'s lead is an accident.

Take a tiny example: a test set $x$ of $n=10$ documents, on which $A$ scores $0.70$ accuracy and $B$ scores $0.50$, so $\delta (x)=0.20$. Label each document by which systems got it right. Now draw a bootstrap sample $x^{(i)}$ by selecting a document from $x$ at random $10$ times with replacement — the same document may appear several times, others not at all — and record its own $\delta (x^{(i)})$. Repeat $b$ times (perhaps $b=10^5$) to build a whole distribution of deltas.

Now we count how surprising the observed $\delta (x)$ is. Under $H_0$ we would expect $\delta$ estimated over many true test sets to average zero. But the bootstrap sets are not drawn from a zero-mean distribution — they are resampled from $x$, which is itself biased in $A$'s favor by exactly $\delta (x)=0.20$. So the bootstrap distribution is centered on $\delta (x)$, not $0$. To measure how often $A$ beats expectations by $\delta (x)$ or more, count how often a resampled $\delta (x^{(i)})$ exceeds the biased center by another $\delta (x)$:

where $1(\cdot )$ is $1$ when its condition holds and $0$ otherwise. The key correction is the factor of two: because the bootstrap sets inherit $x$'s bias, we test against $2\delta (x)$, not $\delta (x)$. The result is a one-sided empirical p-value.

The whole procedure is a short loop: compute the real $\delta (x)$, then for each of $b$ bootstrap samples compute $\delta (x^{(i)})$ and tally how often it clears $2\delta (x)$.

To finish the example: with $b=10,000$ bootstrap test sets and a threshold of $0.01$, suppose only $47$ of them have $\delta (x^{(i)})\ge 2\delta (x)$. Then

so the observed $\delta (x)=0.20$ is sufficiently surprising under $H_0$: we reject the null hypothesis and conclude $A$ is genuinely better than $B$. Had hundreds or thousands of bootstrap sets matched $A$'s lead, the p-value would sit above the threshold and we could not rule out luck. Report the effect size $\delta (x)$ alongside the p-value — significance says the difference is real, the effect size says whether it is large enough to matter.