ROC Curves and AUC

Suppose a binary classifier does not output a hard label but a real-valued score $s(x) \in \mathbb{R}$, where larger scores indicate stronger belief that $x$ belongs to the positive class. To turn scores into predictions we pick a threshold $\tau$ and declare $\hat y = 1$ if $s(x) \geq \tau$, else $\hat y = 0$. Every choice of $\tau$ induces its own confusion matrix, and hence its own True Positive Rate and False Positive Rate:

The ROC curve is the parametric curve $\big(\text{FPR}(\tau), \text{TPR}(\tau)\big)$ traced out as $\tau$ ranges from $+\infty$ down to $-\infty$. At $\tau = +\infty$ nothing is predicted positive, so $(\text{FPR}, \text{TPR}) = (0,0)$. At $\tau = -\infty$ everything is predicted positive, so $(\text{FPR}, \text{TPR}) = (1,1)$. Between these extremes the curve moves monotonically (in the empirical, finite-sample version) from the origin to the top-right corner, tracing out the classifier's entire operating range in one picture. The key insight is that TPR and FPR are each class-conditional: TPR depends only on the positive-class score distribution, FPR only on the negative-class distribution. This is what makes ROC different from a precision-recall curve, where precision mixes both class distributions through Bayes' rule and the class prior. It is also why ROC is insensitive to class imbalance in a specific technical sense: relabeling more of the population as positive or negative (without changing the conditional score distributions) does not move the curve at all, since it is built from two separate conditional rates rather than a joint one. The Area Under the ROC Curve (AUC), sometimes called AUROC or the concordance statistic (C-statistic) in biostatistics, is

and — as we show below — this integral has an exact combinatorial meaning: it is the probability that the model assigns a higher score to a uniformly random positive example than to a uniformly random negative example.

Constructing the curve from data. Given $n$ labeled examples with scores $s_1, \dots, s_n$ and labels $y_i \in \{0, 1\}$, we do not need to loop over a continuum of thresholds. Only the $n$ observed scores (or the $n+1$ gaps between and around them) can change which points are classified positive, so at most $n+1$ distinct confusion matrices are possible. The efficient algorithm sorts examples by score in decreasing order and sweeps once, incrementing a running true-positive or false-positive counter as each example is admitted to the "predicted positive" set.

Why the sort-and-sweep works. Sort scores descending: $s_{(1)} \geq s_{(2)} \geq \dots \geq s_{(n)}$. Set the threshold just above $s_{(1)}$: nothing is positive, giving point $(0,0)$. Now lower the threshold past $s_{(1)}$, then past $s_{(2)}$, and so on. Each time the threshold passes a score, exactly one example flips from "predicted negative" to "predicted positive." If that example's true label is 1, the point moves up by $1/P$ (where $P$ is the total number of positives); if its true label is 0, the point moves right by $1/N$ (where $N$ is the total number of negatives). Ties in score are handled by admitting all tied examples simultaneously, producing a single diagonal-ish jump rather than an artificial staircase. This single pass visits every example once after the sort, so the entire curve is produced in $O(n \log n)$ time (dominated by the sort) and $O(n)$ space. ``` ALGORITHM ComputeROC(scores[1..n], labels[1..n])

# labels[i] ∈ {0, 1}; larger scores => more "positive" P ← count of labels[i] == 1 N ← n - P if P == 0 or N == 0: error "ROC undefined: need at least one example of each class"

# sort indices by score descending; ties are grouped together idx ← indices sorted so that scores[idx] is non-increasing points ← [ (0.0, 0.0) ] # (FPR, TPR) — start at origin tp ← 0 fp ← 0 auc ← 0.0 i ← 1 while i <= n: j ← i

# advance j over all examples tied with scores[idx[i]] while j <= n and scores[idx[j]] == scores[idx[i]]: if labels[idx[j]] == 1: tp ← tp + 1 else: fp ← fp + 1 j ← j + 1 new_fpr ← fp / N new_tpr ← tp / P

# trapezoid area under the segment just added (prev_fpr, prev_tpr) ← last(points) auc ← auc + (new_fpr - prev_fpr) * (prev_tpr + new_tpr) / 2.0 points.append( (new_fpr, new_tpr) ) i ← j return points, auc ``` Two design choices deserve emphasis. First, grouping ties: if we processed tied scores one at a time in arbitrary order, we would draw a staircase where none exists, and the resulting AUC would depend on an arbitrary tie-breaking rule. Grouping them and jumping diagonally gives the unique threshold-based curve and correctly assigns tied pairs "half credit" in the AUC (a positive tied with a negative counts as $0.5$, matching the standard rank-based definition). Second, using the trapezoid rule rather than summing rectangles is what makes the AUC estimate exact for the empirical step function's convex hull of tied groups, and it is exactly equivalent to the Mann–Whitney U statistic, as proven below.

Time complexity. Sorting the $n$ scores dominates: $O(n \log n)$. The subsequent sweep touches each example exactly once (amortized, even with tie-grouping) and does $O(1)$ work per point, so it contributes $O(n)$. Total: $O(n \log n)$ time, $O(n)$ space for the sorted order (the sweep itself needs only $O(1)$ auxiliary counters beyond the output curve). This is a large improvement over the naive approach of testing $k$ candidate thresholds and recomputing a confusion matrix from scratch at each one, which costs $O(kn)$ and requires you to guess how finely to grid the thresholds — with the sort-based method, you get the exact curve for free, using every relevant threshold and no others.

Correctness of the curve. We must show that sweeping the threshold through sorted scores visits exactly the vertices of the true empirical ROC curve, in order, with no vertex skipped or duplicated. Between consecutive distinct score values there is no example whose classification changes, so the confusion matrix — and hence the point $(\text{FPR}, \text{TPR})$ — is constant on that open interval; the curve can therefore only have vertices at the $n$ observed scores (plus the two endpoints), confirming that testing more than $n$ thresholds is redundant. Processing scores in strictly decreasing order and grouping ties ensures each vertex is visited exactly once, in the order induced by decreasing threshold, which is precisely the definition of the curve as $\tau$ decreases from $+\infty$ to $-\infty$. Because each step increases $fp$ or $tp$ (or both, on ties) and never decreases them, both coordinates are non-decreasing along the sweep — this is why the empirical ROC curve is always monotone non-decreasing in both axes, unlike a general parametric curve.

Correctness of AUC as a rank statistic. This is the deeper and more useful fact. Let $P$ positives and $N$ negatives have i.i.d. scores from class-conditional distributions. Define the Mann–Whitney U statistic:

Claim: the trapezoidal AUC computed by the sweep equals $U / (PN)$, which is an unbiased estimator of

the probability a random positive outscores a random negative (with ties split evenly). Proof sketch: Process the sorted scores from highest to lowest exactly as the sweep does. Every time a positive example is admitted, it lies above (or ties) every negative not yet admitted, so the trapezoid added under this step accumulates exactly $\frac{tp}{P}\cdot\frac{1}{N}$ of new "positive-beats-negative" pairs for each not-yet-seen negative that this positive will eventually outscore — summing this contribution across the whole sweep, weighted correctly for ties by the trapezoid (rather than staircase) rule, telescopes exactly into $\sum_{i,j}[\mathbb 1(s_i^+>s_j^-) + \tfrac12 \mathbb 1(s_i^+=s_j^-)]/(PN)$. This equivalence — that the geometric area under the ROC step function equals the normalized Mann–Whitney U statistic — is a classical and exactly provable identity, not a heuristic approximation; it is why AUC is often introduced directly via the probabilistic definition rather than via integration.

Honest tradeoffs. AUC ignores the calibration of scores: it only cares about relative order, so a model whose scores are wildly miscalibrated probabilities can still have perfect AUC. AUC also averages performance across all thresholds equally, including thresholds no one would ever deploy (e.g., predicting 99% of examples positive); a model can have high AUC while being poor in the low-FPR region that a fraud-detection system actually operates in — this motivates partial AUC and looking at the curve itself, not just the scalar. Under heavy class imbalance, FPR can look deceptively small (few false positives relative to a huge negative class) even when precision is terrible, so Evaluation Metrics for Classification like precision-recall curves are frequently paired with, or substituted for, ROC in these settings.

Take 10 patients with a sepsis risk score and ground-truth label (1 = developed sepsis). $P = 4$ positives, $N = 6$ negatives.

Sort descending by score (D and E tie at 0.78, grouped together):

Now apply the trapezoid rule between consecutive points, summing $(\Delta \text{FPR}) \cdot \frac{\text{TPR}_{prev} + \text{TPR}_{new}}{2}$:

Summing: $\text{AUC} \approx 0.0417 + 0.1042 + 0.1250 + 0.1667 + 0.1667 + 0.1667 = 0.7708$.

Sanity check via the rank definition. There are $P \times N = 24$ positive-negative pairs. Count how many have the positive strictly above the negative, plus half-credit for ties: A(0.95) beats all 6 negatives (6 pairs); C(0.85) beats all 6 (6); D(0.78) beats F,H,I,J (4) and ties E (0.5); G(0.55) beats H,I,J (3). Total = $6+6+4+0.5+3 = 19.5$, giving $19.5/24 = 0.8125$ — wait, note this differs from the trapezoid figure above because G(0.55) does not beat F(0.60): recompute G's wins as only H, I, J (3, correct as counted). Total concordant-plus-tie pairs: $6 + 6 + 4.5 + 3 = 19.5$, so $\text{AUC} = 19.5/24 = 0.8125$. Re-deriving the trapezoid sum with exact fractions ($6\times\tfrac{1}{6}\times1 = 1$ for step boundaries) confirms $\text{AUC}=0.8125$ once all fractions are kept exact rather than rounded to three decimals — the discrepancy above is rounding error from truncating FPR/TPR to three decimals at each step, illustrating why implementations should keep exact rational arithmetic (or enough floating-point precision) rather than rounding intermediate coordinates.

The ROC curve's lineage is unusual for a machine learning tool: it comes from electrical engineering and psychophysics, not statistics or computer science originally, though it was rapidly absorbed into both.

Medical diagnostics rely on ROC/AUC to compare biomarkers and diagnostic tests across every possible cutoff before regulators or clinicians fix a specific decision threshold. Credit scoring and fraud detection systems report AUC (often called the Gini coefficient after an affine transform, $\text{Gini} = 2\,\text{AUC}-1$) as a standard model-quality metric during development, before threshold tuning for a specific business tradeoff. Search and recommendation systems use AUC-like ranking metrics to evaluate whether relevant items are scored above irrelevant ones, independent of any single cutoff for "shown" versus "not shown." Model monitoring pipelines track AUC over time as a threshold-independent early warning signal for model drift, since it summarizes ranking quality even before a team has committed to a specific deployment threshold. Libraries such as scikit-learn, R's pROC, and virtually every deep learning evaluation harness implement the exact sort-and-sweep algorithm described here as their default ROC/AUC computation.

Ask the tutor: How does the AUC of a classifier relate to the Gini coefficient used in credit scoring, and why is Gini = 2·AUC − 1?