Confusion Matrices

A classifier maps each input to a predicted label $\hat{y}$, while each input also carries a true label $y$. A confusion matrix is a $k \times k$ table $C$, for a $k$-class problem, where entry $C_{ij}$ counts the number of examples whose true class is $i$ and whose predicted class is $j$. The diagonal entries $C_{ii}$ count correct predictions; every off-diagonal entry counts a specific type of mistake — class $i$ mistaken for class $j$. For binary classification, where the classes are conventionally labeled positive and negative, the $2\times 2$ matrix has a standard vocabulary:

• True Positive (TP): predicted positive, actually positive.
• False Positive (FP): predicted positive, actually negative (a "Type I error").
• False Negative (FN): predicted negative, actually positive (a "Type II error").
• True Negative (TN): predicted negative, actually negative.

These four counts are the atomic quantities of classification evaluation. Every metric you have met when studying Evaluation Metrics for Classification — accuracy, precision, recall, F1-score, specificity — is a ratio built from TP, FP, FN, and TN. The confusion matrix is not itself a metric; it is the sufficient statistic from which all threshold-specific metrics are derived. Two classifiers with identical accuracy can have wildly different confusion matrices, and it is the matrix, not the accuracy scalar, that tells you whether a model over-predicts or under-predicts the positive class.

Constructing a confusion matrix requires only the true labels and predicted labels for a labeled test set — no retraining, no extra data. The procedure is a single pass that increments a counter for each (true, predicted) pair.

Step 1 — Fix the label set. Enumerate the $k$ distinct classes and fix an ordering (e.g., alphabetical, or "negative" then "positive" for binary problems). This ordering defines the row and column indices of the matrix.

Step 2 — Initialize. Allocate a $k \times k$ integer array, all zeros.

Step 3 — Tally. For every example in the evaluation set, look up its true class index $i$ and predicted class index $j$, and increment $C[i][j]$.

Step 4 — Derive metrics. Once the matrix is filled, all standard metrics follow from row sums, column sums, and the diagonal. For the binary case, given TP, FP, FN, TN:

For multiclass problems, per-class precision and recall are computed by treating each class in turn as "positive" and all others as "negative" (a one-vs-rest reduction), then optionally averaged (macro-average: unweighted mean across classes; micro-average: pool all TP/FP/FN globally before dividing). ``` function BUILD_CONFUSION_MATRIX(true_labels, pred_labels, classes):

# classes: ordered list of the k distinct labels k = length(classes) index = map each class to its position in `classes` # O(k) C = k x k array of zeros # O(k^2) space for t in 1 .. length(true_labels): # O(n) time i = index[true_labels[t]] j = index[pred_labels[t]] C[i][j] = C[i][j] + 1 return C

function BINARY_METRICS(C, pos_index, neg_index): TP = C[pos_index][pos_index] FN = C[pos_index][neg_index] FP = C[neg_index][pos_index] TN = C[neg_index][neg_index] accuracy = (TP + TN) / (TP + FP + FN + TN) precision = TP / (TP + FP) if (TP + FP) > 0 else undefined recall = TP / (TP + FN) if (TP + FN) > 0 else undefined specificity = TN / (TN + FP) if (TN + FP) > 0 else undefined f1 = 2 precision recall / (precision + recall) if precision, recall defined else undefined return {accuracy, precision, recall, specificity, f1}

function MACRO_AVERAGE_METRICS(C): k = number of rows in C total_precision = 0 total_recall = 0 for c in 1 .. k: TP_c = C[c][c] FP_c = sum over rows r != c of C[r][c] FN_c = sum over cols col != c of C[c][col] precision_c = TP_c / (TP_c + FP_c) if (TP_c + FP_c) > 0 else 0 recall_c = TP_c / (TP_c + FN_c) if (TP_c + FN_c) > 0 else 0 total_precision += precision_c total_recall += recall_c return {macro_precision = total_precision / k, macro_recall = total_recall / k} ```

Time complexity. Building the matrix is a single pass over the $n$ evaluation examples, with $O(1)$ work per example (a label lookup and an array increment), giving $O(n)$ time. Looking up the class index can be made $O(1)$ with a precomputed hash map from label to index, built once in $O(k)$ time where $k$ is the number of classes; without this map, a naive linear search over classes costs $O(k)$ per example, giving $O(nk)$ overall — a common inefficiency in careless implementations. Deriving any of the standard metrics from a filled matrix costs $O(1)$ for binary problems and $O(k)$ for a single class's precision/recall in the multiclass case, since each requires summing one row and one column of length $k$. Computing macro-averages over all classes costs $O(k^2)$, dominated by summing every row and column once — still cheap since $k \ll n$ in virtually all practical settings.

Space complexity. The matrix itself requires $O(k^2)$ integers. For binary classification this is a constant 4 numbers; even for a 1000-class problem it is one million counters, negligible next to the dataset that produced them. No auxiliary space beyond the label-to-index map ($O(k)$) is needed.

Correctness. The construction is correct by a straightforward counting invariant: after processing the first $t$ examples, $C_{ij}$ equals exactly the number of those $t$ examples with true label $i$ and predicted label $j$. This holds by induction — it is true vacuously at $t=0$ (all zeros), and each processing step increments exactly the one cell corresponding to the current example's (true, predicted) pair, preserving the invariant for $t+1$. At $t = n$, the invariant gives the full and exact matrix. Consequently:

• The sum of all entries equals $n$, since every example is counted exactly once.
• The sum of row $i$ equals the number of examples truly of class $i$ (the class's support).
• The sum of column $j$ equals the number of examples the classifier predicted as class $j$.
• The trace $\sum_i C_{ii}$ equals the total number of correct predictions, so accuracy $= \text{trace}(C)/n$ is exact, not an approximation.

These identities are not assumptions to be verified experimentally — they follow deterministically from the definition of the matrix as a partition of the $n$ examples into $k^2$ disjoint categories.

Honest tradeoffs. The confusion matrix is a point estimate tied to one fixed decision threshold (for probabilistic classifiers, wherever probability $\geq 0.5$, or whatever threshold was chosen, becomes "predicted positive"). It says nothing about how metrics would change if the threshold moved — that question is exactly what motivates sweeping the threshold and plotting the trajectory, which is the ROC curve. The matrix also does not itself weight errors by real-world cost; a false negative for cancer screening and a false negative for spam filtering are numerically identical entries even though their consequences differ by orders of magnitude — cost-weighting must be applied on top of the raw counts. Finally, with small test sets the counts in each cell carry high variance, and a matrix built from only a few dozen examples can look decisive while resting on statistically fragile numbers.

Binary case: a spam filter tested on 200 emails, where "positive" means "predicted spam."

Step through the derived metrics:

Reading the table directly (not just the metrics) tells a richer story than accuracy alone: the model catches 87.5% of actual spam (high recall) but nearly a quarter of its "spam" flags are false alarms on legitimate mail (precision only 74.5%). A user annoyed by lost real emails cares about precision; a user annoyed by spam in their inbox cares about recall — the confusion matrix lets both be read off the same table.

Multiclass case: a 3-class image classifier (Cat, Dog, Bird) tested on 90 images, 30 of each true class.

Per-class metrics, treating each class as "positive" in turn (one-vs-rest):

Macro-averaged precision $= (0.833+0.800+0.867)/3 \approx 0.833$, and macro-averaged recall is identical here by symmetry of this particular table (not true in general). Overall accuracy is $(25+24+26)/90 = 75/90 \approx 0.833$. Note that "Dog" is the weakest class — it is most often confused symmetrically with both Cat and Bird — information completely invisible in the single accuracy figure but immediately visible as the smaller diagonal entry and larger off-diagonal spread in its row and column.

The confusion matrix as a concept predates modern machine learning by decades, growing out of statistical hypothesis testing and signal detection theory rather than any single computer-science paper. Its terminology — Type I and Type II errors, sensitivity and specificity — was formalized in the statistics and psychometrics literature of the early-to-mid twentieth century, before being adopted wholesale by pattern recognition and later machine learning communities as the standard evaluation scaffold for classifiers.

Confusion matrices are the backbone of evaluation in every domain where classifiers make consequential decisions. In medical diagnostics, regulators and clinicians scrutinize the full matrix — not just accuracy — because false negatives (missed disease) and false positives (unnecessary alarm and treatment) carry very different costs; sensitivity and specificity, both derived directly from the matrix, are the standard reporting metrics in clinical validation studies. In fraud detection and anti-money-laundering systems at banks, the matrix is used to tune decision thresholds against a cost model, since a false negative (missed fraud) may cost thousands of dollars while a false positive merely triggers a manual review. In natural language processing and computer vision benchmarks, multiclass confusion matrices reveal systematic model weaknesses — for instance, an image classifier that specifically confuses "wolf" with "husky," a pattern invisible in aggregate accuracy but glaring in the matrix's off-diagonal structure. Spam and content-moderation systems tune thresholds using confusion-matrix-derived precision/recall tradeoffs, since aggressive filtering (high recall) trades directly against false removal of legitimate content (precision). Machine learning frameworks such as scikit-learn, TensorFlow, and PyTorch expose confusion-matrix utilities as first-class evaluation primitives precisely because nearly every higher-level metric — including the metrics that populate the ROC curve as the decision threshold varies — is computed from it.

Ask the tutor: How does sweeping the decision threshold turn a single confusion matrix into a full ROC curve?