A score gives more than one possible decision
A classifier can assign a real score rather than a single positive or negative decision. Choosing a threshold converts the score into a decision, but different thresholds can have different true- and false-positive rates. The receiver operating characteristic (ROC) summarizes these rates across thresholds. This note treats a fixed labeled evaluation set; a computed area on that set is not automatically the population performance of a model or an unbiased estimate after repeated model selection.
Definition 11.1.1
(Empirical ROC curve)
Suppose there are positive examples and negative examples. Predict positive when the score is at least a threshold . Define
The ROC point has horizontal coordinate FPR and vertical coordinate TPR. A set with no positive or no negative example cannot supply both denominators, so this empirical ROC and its area are undefined there. Begin above the largest score at ; as the threshold decreases, admit all observations at each distinct score together. At the lowest score the point is . Tied scores cannot be ordered into separate deterministic score thresholds without adding a further rule.
From a staircase to an area
At one score level suppose positives and negatives are admitted together. The ROC moves right by and up by . To define the usual trapezoidal empirical AUC, join consecutive points by straight line segments and integrate height against horizontal displacement. Vertical segments contribute zero area. This interpolation can also represent expected rates from randomly choosing between the two endpoint threshold classifiers, or randomly admitting a common fraction of the tied group independently of label. An intermediate point need not be attainable by one deterministic threshold on the original score.
The empirical AUC has an exact ranking interpretation.
Theorem 11.1.2
(Pairwise form of the trapezoidal AUC)
Choose one of the positives and one of the negatives independently and uniformly, with scores and . Then the trapezoidal area under the empirical ROC curve equals
Here the probability refers to sampling uniformly from the observed positive and negative examples, with independent draws. It is not a probability that an individual prediction is correct, and it is tied to the half-credit interpolation just specified.
Proof
(Trapezoid areas, group by group)
Sort distinct score levels from high to low. At one level let and be its positive and negative counts, and let be the number of positives at strictly higher scores. Before the group, the ROC height is ; after it, the height is . The trapezoid for this group therefore has area
Summing groups counts each positive–negative pair once: a negative in the current group pairs with a strictly higher positive for one unit, and with a tied positive for half a unit. Pairs where the positive scores lower contribute zero. This is exactly the displayed probability. The proof covers groups containing only one class and score ties of any size.
Proof X-ray
Why a tie earns exactly half
The proof leans on three decisions. The ROC is built from whole score groups, so a tied group moves the curve along one straight segment. The area of that segment's trapezoid splits into a rectangle of height and a triangle of height , which is where full credit for strictly higher positives and half credit for tied positives come from. The proof closes by double counting: every positive–negative pair lies in exactly one of three cases (positive strictly higher, same group, positive strictly lower), and each case is counted once through the negative's group. If the tied group were instead split into separate thresholds in some arbitrary order, the rectangle and triangle would change and so would the area. The positivity of and is needed only so that the denominators exist.
A six-example trace
Worked example 11.1.3
(A six-example trace with a tie)
Consider three positive scores and three negative scores . Each threshold in the table is inclusive; the first row places it above every observed score.
| Threshold | Admitted group | FPR | TPR |
|---|---|---|---|
| above 0.9 | none | 0 | 0 |
| 0.9 | one positive | 0 | |
| 0.8 | one negative | ||
| 0.6 | two positives, one negative | 1 | |
| 0.2 | one negative | 1 | 1 |
The trapezoidal areas across the three nonzero horizontal intervals are , and , summing to . The pair count agrees: of nine positive–negative pairs, five have a strictly higher positive score and two are tied, so . The diagonal segment across the tied group is an interpolation, not an additional score threshold.
Worked example 11.1.4
(Counting pairs and checking against the curve)
Take positive scores and negative scores . The score beats all three negatives. The score beats , ties with and loses to . So there are wins and tie among pairs, and . The curve agrees: its points are , , , , , and the trapezoid areas are , and , which sum to .
Worked example 11.1.5
(All scores equal)
Let there be positives and negatives, all with score . There is one group with , and , so the ROC goes from straight to and the area is . All six pairs are ties, each worth half. This is the edge case in which the score carries no ranking information, and it does not depend on or .
Common mistake
(Dividing false positives by the wrong denominator)
In the six-example trace at threshold , the classifier has and . The false-positive rate is , with negatives. Dividing instead by the number of predicted positives gives , which is , a different quantity. The ROC coordinates always use the class sizes and as denominators.
Counterexample mode
Breaking ties arbitrarily changes the area
Claim: tied scores can be ordered arbitrarily before tracing the curve without changing the area. Take one positive and one negative, both with score . Ordering the positive first gives the path with area . Ordering the negative first gives with area . The tied-group trapezoid gives the straight segment from to and area , which matches the half-credit pair count. An arbitrary tie-breaking rule can therefore produce any value between the pessimistic and optimistic areas, so the convention must be stated, and this unit uses the half-credit one.
The explorer below lets you edit labeled scores and checks that the half-credit trapezoid area across tied groups equals (wins + ties/2)/(PN) from an independent count of all positive–negative pairs.
What AUC does and does not decide
A strictly increasing score transformation preserves every comparison and tie, so it preserves this AUC; a merely nondecreasing transformation can create ties and change it. AUC measures ranking over positive–negative pairs and aggregates the ROC curve over false-positive rates; it is not a uniform average over threshold values. It does not select a deployment threshold, measure calibration, or encode the cost of different mistakes. Two models with the same area can have different ROC points at the false-positive rate required in a particular application. A useful evaluation therefore also inspects the relevant operating region and uses data separated appropriately from model and threshold selection. When examples are treated as random, pair contributions sharing an example can be dependent, so the pairwise formula alone is not a confidence interval.
Concept lensCombinatorial
AUC from the rank sum of the positives
Rank all scores in increasing order, giving tied scores their average rank. If is the sum of the ranks of the positives, then . In the six-example trace, the positives have ranks , so and . Average ranks are exactly the half-credit convention for ties.
Exercises
Quick check
(For positive scores and negative scores , count strictly ordered and tied positive–negative pairs and compute the empirical AUC.)
List all four pairs.
Solution · Answer
The pair and the pair are wins. The pair is a loss. The pair is a tie. So .
Quick check
(If all scores are equal and both classes occur, what AUC results under the stated half-credit convention? Explain the interpolation.)
Every pair is tied, and the whole data set is one group.
Solution · Answer
All pairs are ties worth one half, so . The ROC goes from to along the diagonal, which represents randomly admitting the same fraction of both classes. This is an interpolation, not a deterministic threshold on the original score.
Quick check
(Give a nondecreasing but not strictly increasing score transformation that creates a tie from a correctly ordered pair. How does its half-credit contribution change?)
Cap the scores at some value.
Solution · Answer
The map sends the correctly ordered pair to the tie , so the pair's contribution falls from to . For the scores of the first exercise the transformed positives are and negatives , giving one win and two ties, so instead of .