---
title: Evaluating Classifiers
module: Text Classification
moduleNumber: 2
lessonNumber: 2
order: 202
summary: >
  A trained classifier is only useful once we can measure how good it is. We build
  the confusion matrix, see why accuracy misleads on unbalanced data, and define
  precision, recall, and the F-measure that balances them. Multi-class tasks need
  macro- versus micro-averaging; reliable estimates need cross-validation. We close
  on statistical significance — the paired bootstrap test for whether one system's
  lead over another is significant.
topics: [Classification]
sources:
  - book: Jurafsky
    ref: "§4.7 Evaluation: Precision, Recall, F-measure; §4.8 Cross-validation"
  - book: Jurafsky
    ref: "§4.9 Statistical Significance Testing; §4.9.1 The Paired Bootstrap Test"
---

This builds on [Naive Bayes and Sentiment Classification](/natural-language-processing/classification/naive-bayes-and-sentiment),
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).

$$
% caption: The binary confusion matrix. Precision reads across the top row (of all
% items called positive, how many truly are); recall reads down the left column
% (of all truly positive items, how many were found).
\begin{tikzpicture}[>=stealth, font=\small,
  cell/.style={draw, minimum width=26mm, minimum height=13mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[font=\footnotesize] at (1.3,3.15) {gold positive};
  \node[font=\footnotesize] at (3.9,3.15) {gold negative};
  \node[font=\footnotesize, rotate=90] at (-2.3,1.2) {system output};
  \node[font=\footnotesize, anchor=east] at (-0.35,1.85) {positive};
  \node[font=\footnotesize, anchor=east] at (-0.35,0.55) {negative};
  \node[cell, text=acc] (tp) at (1.3,1.85) {true positive};
  \node[cell, text=red] (fp) at (3.9,1.85) {false positive};
  \node[cell, text=red] (fn) at (1.3,0.55) {false negative};
  \node[cell, text=acc] (tn) at (3.9,0.55) {true negative};
  \node[font=\footnotesize, anchor=west, align=left] at (5.5,1.85) {precision =\\ tp / (tp + fp)};
  \node[font=\footnotesize, anchor=north, align=center] at (1.3,-0.5) {recall = tp / (tp + fn)};
\end{tikzpicture}
$$

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:

$$
P = \frac{\text{true positives}}{\text{true positives} + \text{false positives}}.
$$

**Recall** is the fraction of the items that _really are_ positive that the system
found — how much it misses:

$$
R = \frac{\text{true positives}}{\text{true positives} + \text{false negatives}}.
$$

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:

$$
F_\beta = \frac{(\beta^2 + 1)\,P R}{\beta^2 P + R}.
$$

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$:

$$
F_1 = \frac{2 P R}{P + R}.
$$

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.

$$
% caption: Macroaveraging averages the per-class precisions equally; microaveraging
% pools all classes' counts into one confusion matrix first, so the frequent class
% dominates.
\begin{tikzpicture}[>=stealth, font=\small,
  clsbox/.style={draw, minimum width=24mm, minimum height=11mm, align=center, font=\scriptsize},
  outbox/.style={draw, minimum width=30mm, minimum height=12mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[clsbox] (u) at (0,2.2) {class 1: P = 0.42};
  \node[clsbox] (n) at (0,0.9) {class 2: P = 0.52};
  \node[clsbox] (s) at (0,-0.4) {class 3: P = 0.86};
  \node[outbox, draw=acc, text=acc] (macro) at (5.6,0.9) {macroaverage\\= 0.60};
  \node[outbox, draw=acc, text=acc] (micro) at (5.6,-1.4) {microaverage\\= 0.73};
  \draw[->, black] (u.east) to[out=0, in=160] (macro.west);
  \draw[->, black] (n.east) -- (macro.west);
  \draw[->, black] (s.east) to[out=0, in=200] (macro.west);
  \node[font=\scriptsize, anchor=north west] at (-1.9,-2.3) {pool all counts, then divide};
  \draw[->, acc] (1.7,-1.4) to[out=0, in=180] (micro.west);
\end{tikzpicture}
$$

**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\%$.

```algorithm
caption: $\textsc{K-Fold-Cross-Validation}(D, k)$ — average performance over $k$ folds
partition $D$ into $k$ disjoint folds $D_1, \ldots, D_k$
for $i = 1$ to $k$ do
  $\textit{test} \gets D_i$
  $\textit{train} \gets D \setminus D_i$
  train a classifier on $\textit{train}$
  $\textit{score}[i] \gets$ evaluate the classifier on $\textit{test}$
return $\dfrac{1}{k}\sum_{i=1}^{k} \textit{score}[i]$
```

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?[^jm-sig]
**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:

$$
\delta(x) = M(A, x) - M(B, x).
$$

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'$ drawn from the same source.

### The null hypothesis and the p-value

Hypothesis testing formalizes this with two competing claims:

$$
H_0 : \delta(x) \le 0, \qquad H_1 : \delta(x) > 0.
$$

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**:

$$
P\bigl(\delta(X) \ge \delta(x) \;\big|\; H_0 \text{ is true}\bigr).
$$

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**.

$$
% caption: The sampling distribution of $\delta$ under the null hypothesis $H_0$
% (system A no better than B), centered near zero. The observed effect size
% $\delta(x)$ sits in the right tail; the shaded tail area past it is the p-value.
% A small tail area means the observed lead is unlikely under $H_0$, so we reject it.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, black] (-3.4,0) -- (3.9,0) node[right, black, font=\scriptsize] {delta};
  \draw[->, black] (0,0) -- (0,2.9) node[above, black, font=\scriptsize] {frequency};
  % bell curve (gaussian-ish) via plot
  \draw[acc, thick] plot[smooth, domain=-3.2:3.2, samples=60] (\x, {2.5*exp(-\x*\x/1.6)});
  % observed delta marker at x = 1.9
  \draw[red, thick] (1.9,0) -- (1.9,2.05);
  \node[red, anchor=south, font=\scriptsize] at (1.9,2.05) {observed delta(x)};
  % shaded tail past the marker
  \fill[red!16] plot[smooth, domain=1.9:3.2, samples=30] (\x, {2.5*exp(-\x*\x/1.6)}) -- (3.2,0) -- (1.9,0) -- cycle;
  \node[red, anchor=west, font=\scriptsize] at (2.15,0.55) {p-value};
  \node[black, anchor=north, font=\scriptsize] at (0,-0.12) {center: 0 under H0};
\end{tikzpicture}
$$

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.[^jm-boot] 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.

$$
% caption: Building bootstrap test sets. Each virtual set x(i) is drawn by
% sampling n=10 documents from the original test set x with replacement, so
% documents repeat or vanish. Each yields its own delta; the spread of these
% deltas is the sampling distribution used to compute the p-value.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  cellbox/.style={draw, minimum width=7mm, minimum height=7mm, font=\scriptsize, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  % original test set row
  \node[anchor=east, font=\scriptsize] at (-0.2,2.0) {x};
  \foreach \i/\v in {0/1,1/2,2/3,3/4,4/5,5/6,6/7,7/8,8/9,9/10}
    \node[cellbox] at (\i*0.72,2.0) {\v};
  \node[anchor=west, font=\scriptsize, text=acc] at (7.4,2.0) {delta = 0.20};
  % sampled rows
  \node[anchor=east, font=\scriptsize] at (-0.2,1.0) {x(1)};
  \foreach \i/\v in {0/2,1/2,2/5,3/1,4/9,5/3,6/9,7/4,8/2,9/7}
    \node[cellbox] at (\i*0.72,1.0) {\v};
  \node[anchor=west, font=\scriptsize] at (7.4,1.0) {delta = 0.00};
  \node[anchor=east, font=\scriptsize] at (-0.2,0.0) {x(2)};
  \foreach \i/\v in {0/6,1/1,2/1,3/8,4/8,5/3,6/5,7/10,8/2,9/6}
    \node[cellbox] at (\i*0.72,0.0) {\v};
  \node[anchor=west, font=\scriptsize] at (7.4,0.0) {delta = -0.10};
  \node[anchor=west, font=\scriptsize, text=black] at (0,-0.75) {sample n = 10 with replacement, b times};
  \draw[->, acc] (3.2,1.7) -- (3.2,1.25);
  \draw[->, acc] (3.2,0.7) -- (3.2,0.25);
\end{tikzpicture}
$$

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

$$
\text{p-value}(x) = \frac{1}{b} \sum_{i=1}^{b} \mathbb{1}\bigl(\delta(x^{(i)}) - \delta(x) \ge \delta(x)\bigr) = \frac{1}{b} \sum_{i=1}^{b} \mathbb{1}\bigl(\delta(x^{(i)}) \ge 2\,\delta(x)\bigr),
$$

where $\mathbb{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)$.

```algorithm
caption: $\textsc{Bootstrap}(x, b)$ — paired bootstrap p-value that $A$ beats $B$
input: test set $x$ of size $n$, number of bootstrap samples $b$
compute $\delta(x)$ // observed lead of $A$ over $B$ on $x$
$s \gets 0$
for $i = 1$ to $b$ do
  for $j = 1$ to $n$ do
    select a member of $x$ at random and add it to $x^{(i)}$ // resample with replacement
  compute $\delta(x^{(i)})$ // lead of $A$ over $B$ on this virtual set
  if $\delta(x^{(i)}) \ge 2\,\delta(x)$ then
    $s \gets s + 1$
$\textit{p-value} \gets s / b$ // fraction of samples where $A$ beat expectations
return $\textit{p-value}$
```

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

$$
\text{p-value}(x) = \frac{47}{10{,}000} = 0.0047 < 0.01,
$$

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.

[^jm-sig]: **Jurafsky & Martin**, §4.9 — Statistical Significance Testing: comparing two classifiers with the effect size $\delta(x) = M(A,x) - M(B,x)$, the null hypothesis $H_0: \delta(x) \le 0$, the p-value $P(\delta(X) \ge \delta(x) \mid H_0)$, significance thresholds of $0.05$ / $0.01$, and non-parametric (approximate-randomization and bootstrap) rather than parametric tests.
[^jm-boot]: **Jurafsky & Martin**, §4.9.1 — The Paired Bootstrap Test (Efron and Tibshirani 1993; Berg-Kirkpatrick et al. 2012): resampling $b$ virtual test sets with replacement, the sampling distribution of $\delta$, and the p-value $\frac{1}{b}\sum_i \mathbb{1}(\delta(x^{(i)}) \ge 2\,\delta(x))$ with the factor of two correcting for the bias of the observed test set.