ROC-AUC Score

Implement the area under the ROC curve (ROC-AUC) for a binary classifier from scratch with NumPy, without any library metric. Instead of sweeping thresholds to trace the curve and integrating, use the fact that AUC is equivalent to a rank statistic, which is both faster and easier to get exactly right.

Definition

AUC equals the probability that a randomly chosen positive example is scored higher than a randomly chosen negative example. Counting over all positive-negative pairs and giving ties a weight of one half gives the Mann-Whitney U statistic. That statistic can be read directly off the ranks of the scores:

AUC = ( sum_of_ranks_of_positives - n_pos*(n_pos+1)/2 ) / ( n_pos * n_neg )

Here scores are ranked in ascending order starting at 1, n_pos is the number of positive labels, and n_neg the number of negatives. When several examples share the same score they receive the average of the ranks they would otherwise occupy.

Task

Complete roc_auc_score(y_true, y_scores) so it returns the ROC-AUC as a float. y_true holds labels in {0, 1} and y_scores holds real-valued predictions where a larger value means “more likely positive”. Use average ranks to break ties correctly. If either class is missing, AUC is undefined; return float("nan"). Do not call sklearn or any built-in AUC/ranking helper such as scipy.stats.rankdata.

Example

y_true = np.array([0, 0, 1, 1])
y_scores = np.array([0.1, 0.4, 0.35, 0.8])
roc_auc_score(y_true, y_scores)   # -> 0.75

# with a tie between one negative and one positive
y_true = np.array([0, 0, 1, 1])
y_scores = np.array([0.1, 0.4, 0.4, 0.8])
roc_auc_score(y_true, y_scores)   # -> 0.875

In the first case the sorted scores are 0.1(neg), 0.35(pos), 0.4(neg), 0.8(pos) with ranks 1,2,3,4; the positives sit at ranks 2 and 4, so AUC = (6 - 3) / 4 = 0.75.

Constraints

• 1 <= n <= 10^6; use vectorized NumPy, not a Python loop over pairs (the naive pairwise count is O(n^2)).
• Labels are exactly 0 or 1; scores fit in float64 and may contain duplicates.
• Return float("nan") when n_pos == 0 or n_neg == 0.

Approach

Skip the threshold sweep and use the rank identity: AUC is the Mann-Whitney U statistic normalized by n_pos * n_neg. Rank the scores in ascending order with ties broken by their average rank, sum the ranks of the positive examples, and subtract the n_pos*(n_pos+1)/2 offset that removes the ordering among positives themselves. The average rank of each score is found without a sort-and-scan loop by using two searchsorted calls: for a value, the number of strictly smaller scores gives its first slot and the number of smaller-or-equal scores gives its last slot, and averaging those two positions handles ties exactly.

Solution

import numpy as np

def roc_auc_score(y_true, y_scores):
    y_true = np.asarray(y_true)
    y_scores = np.asarray(y_scores, dtype=float)

    pos = y_true == 1
    n_pos = int(np.count_nonzero(pos))
    n_neg = int(np.count_nonzero(~pos))
    if n_pos == 0 or n_neg == 0:      # AUC undefined with a single class
        return float("nan")

    # Average ranks (1-based). For each score:
    #   low  = # of strictly smaller scores        -> first 0-based slot it can take
    #   high = # of smaller-or-equal scores - 1    -> last  0-based slot it can take
    # Averaging the two slots gives the mean rank of a tie group; +1 makes it 1-based.
    s = np.sort(y_scores)
    low = np.searchsorted(s, y_scores, side="left")
    high = np.searchsorted(s, y_scores, side="right") - 1
    ranks = (low + high) / 2.0 + 1.0

    sum_pos_ranks = float(np.sum(ranks[pos]))
    auc = (sum_pos_ranks - n_pos * (n_pos + 1) / 2.0) / (n_pos * n_neg)
    return auc

Walkthrough

Take the tie example y_true = [0, 0, 1, 1], y_scores = [0.1, 0.4, 0.4, 0.8].

• pos = [F, F, T, T], so n_pos = 2, n_neg = 2; both classes present, continue.
• s = sort(y_scores) = [0.1, 0.4, 0.4, 0.8].
• low = searchsorted(s, y_scores, "left") = [0, 1, 1, 3] (strictly-smaller counts).
• high = searchsorted(s, y_scores, "right") - 1 = [1, 3, 3, 4] - 1 = [0, 2, 2, 3].
• ranks = (low + high)/2 + 1 = [1.0, 2.5, 2.5, 4.0]. The two tied 0.4 scores each get rank 2.5, the average of slots 2 and 3.
• Positive ranks are ranks[pos] = [2.5, 4.0], summing to 6.5.
• auc = (6.5 - 2*3/2) / (2*2) = (6.5 - 3) / 4 = 0.875.

That matches counting pairs directly: three of the four positive-negative comparisons are correctly ordered and the one tie counts as a half, 3.5 / 4 = 0.875.

Complexity & notes

• Time O(n log n) from the sort and the two searchsorted calls; space O(n) for the sorted copy and rank array. This beats the O(n^2) pairwise definition that an interviewer will expect you to avoid.
• The n_pos*(n_pos+1)/2 term is the sum of ranks 1..n_pos, i.e. the minimum possible rank mass the positives could hold; subtracting it converts “sum of positive ranks” into “number of correctly ordered pairs” (the U statistic), then dividing by n_pos*n_neg normalizes to [0, 1].
• Average ranks are what make ties correct: a positive and a negative sharing a score contribute 0.5 to U, exactly as the average-rank arithmetic yields. Using ordinal ranks instead would bias the score depending on input order.
• Guard the single-class case explicitly. With no positives or no negatives the denominator n_pos*n_neg is zero and the metric is genuinely undefined, so nan is the honest return.
• AUC is threshold-independent and invariant to any monotonic transform of the scores, which is why the rank formula works and why AUC says nothing about calibration.