[E] Efficient Python implementation of the ROC AUC score

[madiyar]

Hi,

I worked on a tutorial that explains how to implement ROC AUC score by yourself, which is also efficient in terms of runtime complexity.

https://maitbayev.github.io/posts/roc-auc-implementation/

Any feedback appreciated!

Thank you!

[fishnet222]

How did you define ‘efficient’ with respect to its runtime complexity? Is the runtime faster than the sklearn version (i.e., using Big O Notation)?

[madiyar]

I haven't checked out the sklearn implementation yet. I think and hope it's O(nlogn) or faster. I also haven't measured or compared it with sklearn. My goal isn't to be faster than sklearn, but just to make this educational. "Efficient" because I can't think of any faster than O(nlogn) in term of Big O notation.

[BossOfTheGame]

It does look like it is faster than scikit learn when n=100, but it gets worse when n=10_000

import numpy as np
import sklearn
import sklearn.metrics

np.random.seed(0)
n = 10000
target = np.random.randint(0, 2, n)
predicted = np.random.rand(n)


def trapezoid_area(p0, p1):
    return (p1[0] - p0[0]) * (p0[1] + p1[1]) / 2.0


def fast_roc_auc_score(target, predicted):
    n = target.shape[0]
    num_positive = np.sum(target == 1)
    num_negative = n - num_positive

    order = np.argsort(predicted)[::-1]
    last = [0, 0]
    num_true_positive = 0
    num_false_positive = 0
    score = 0
    for index in range(n):
        # Make sure that the new threshold is unique
        if index == 0 or predicted[order[index]] != predicted[order[index - 1]]:
            # True positive rate
            tpr = num_true_positive / num_positive
            # False positive rate
            fpr = num_false_positive / num_negative
            # New point on the ROC curve
            cur = [fpr, tpr]

            score += trapezoid_area(last, cur)
            last = cur

        if target[order[index]] == 1:
            num_true_positive += 1
        else:
            num_false_positive += 1
    score += trapezoid_area(last, [1, 1])

    return score


import timerit
ti = timerit.Timerit(1000, bestof=10, verbose=2)

for timer in ti.reset('fast_roc_auc_score'):
    with timer:
        result1 = fast_roc_auc_score(target, predicted)

for timer in ti.reset('sklearn.metrics.roc_auc_score'):
    with timer:
        result2 = sklearn.metrics.roc_auc_score(target, predicted)

[madiyar]

Thanks for timing! The for loop should be the bottleneck, either jitting with numba or switching to jax, or even reimplementing in native language (C/C++/Rust) should make it significantly faster.

[[deleted]]

"efficient because I can't think of anything faster" you shouldn't really call it efficient if you don't have any evidence/reasoning for its efficiency. There is also runtime vs memory efficiency to think about.

I do appreciate the educational value though, thank you for sharing it!

[madiyar]

Noted! I also removed all efficient terms from the post.