36
$\begingroup$

Why is the area under the ROC curve the probability that a classifier will rank a randomly chosen "positive" instance (from the retrieved predictions) higher than a randomly chosen "positive" one (from the original positive class)? How does one prove this statement mathematically using integral, giving the CDFs and PDFs of the true positive and negative class distributions?

$\endgroup$
4
  • 3
    $\begingroup$ I wrote a very elementary proof of this here: madrury.github.io/jekyll/update/statistics/2017/06/21/… $\endgroup$ Commented Nov 12, 2017 at 23:44
  • 2
    $\begingroup$ sorry, but I've read this question 5 times and I'm still not sure how your statement: "probability that a classifier will rank a randomly chosen "positive" instance (from the retrieved predictions) higher than a randomly chosen "positive" one (from the original positive class)" is the same thing as: "the probability that a randomly drawn member of class 0 will produce a score lower than the score of a randomly drawn member of class 1." $\endgroup$ Commented Jul 14, 2022 at 4:29
  • $\begingroup$ @MatthewDrury : In your proof you have mentioned "Consequently, the threshold corresponding to the green point on the ROC curve is the minimal possible threshold that classifies the orange point correctly (i.e. as a positive class)." and also, "The threshold associated with the point along the ROC curve where a vertical line drawn from the point meets is the minimal possible threshold incorrectly classifying it as positive". Would not the minimal possible threshold in both the cases be 0? Threshold 0 means you classify everything as positive. all correct for y axis and all incorrect for x axis $\endgroup$ Commented Sep 29, 2022 at 13:00
  • $\begingroup$ Here, that's how: It's a link a to a pdf document. They give a simple proof using the trapezoid rule. Notice that the proof has some typos, and that the article is dealing credit scores, not general model scores. IMO it shouldn't be a major issue. bundesbank.de/resource/blob/704150/… $\endgroup$
    – Alex Teush
    Commented Jun 18, 2023 at 16:09

5 Answers 5

22
$\begingroup$

From Measuring classifier performance: a coherent alternative to the area under the ROC curve :

First thing, let's try to define the area under the ROC curve formally. Some assumptions and definitions:

  • We have a probabilistic classifier that outputs a "score" s(x), where x are the features, and s is a generic increasing monotonic function of the estimated probability p(class = 1|x).

  • $f_{k}(s)$, with $k = \{0, 1\}$ := pdf of the scores for class k, with CDF $F_{k}(s)$

  • The classification of a new observation is obtained compraing the score s to a threshold t

Furthermore, for mathematical convenience, let's consider the positive class (event detected) k = 0, and negative k = 1. In this setting we can define:

  • Recall (aka Sensitivity, aka TPR): $F_{0}(t)$ (proportion of positive cases classified as positive)
  • Specificity (aka TNR): $1 - F_{1}(t)$ (proportion of negative cases classified as negative)
  • FPR (aka Fall-out): 1 - TNR = $F_{1}(t)$

The ROC curve is then a plot of $F_{0}(t)$ against $F_{1}(t)$. Setting $v = F_1(s)$, we can formally define the area under the ROC curve as: $$AUC =\int_{0}^{1} F_{0}(F_{1}^{-1}(v)) dv$$ Changing variable ($dv = f_{1}(s)ds$): $$AUC =\int_{ - \infty}^{\infty} F_{0}(s) f_{1}(s)ds$$

This formula can easily be seen as the probability that a randomly drawn member of class $0$ will have a score lower than the score of a randomly drawn member of class $1$.

$\endgroup$
2
  • 4
    $\begingroup$ Can you elaborate on how this "can easily be seen", because I can't ? :) $\endgroup$
    – ado sar
    Commented Nov 20, 2022 at 16:11
  • $\begingroup$ @adosar look a it this way: you are multiplying the probability of of 1 of having a score s to the probability of a 0 of having a score less than s, summing up across all the possible s's. $\endgroup$
    – alebu
    Commented Feb 17, 2023 at 16:12
20
$\begingroup$

@alebu's answer is great. But its notation is nonstandard and uses 0 for the positive class and 1 for the negative class. Below are the results for the standard notation (0 for the negative class and 1 for the positive class):

Pdf and cdf of the score for negative class: $f_0(s)$ and $F_0(s)$

Pdf and cdf of the score for positive class: $f_1(s)$ and $F_1(s)$

FPR = $x(s) = 1-F_0(s)$

TPR = $y(s) = 1-F_1(s)$

Now, using that $dx(\tau)=x'(\tau)d\tau$

and $y(x(\tau))=y(\tau)$ by definition of the ROC curve.

$$\begin{align} \text{AUC} &= \int_0^1 y(x) dx\\ &= \int_0^1 y(x(\tau)) dx(\tau) \\ &= \int_{+\infty}^{-\infty} y(\tau) x'(\tau) d\tau \\ &= \int_{+\infty}^{-\infty} \big( 1-F_1(\tau) \big) \big( -f_0(\tau) \big) d\tau \\ &= \int_{-\infty}^{+\infty} \big( 1-F_1(\tau) \big) f_0(\tau) d\tau \end{align}$$

where $\tau$ stands for threshold. One can apply the interpretation in @alebu's answer to the last expression.

$\endgroup$
2
  • 1
    $\begingroup$ This is one of the most concise and elegant derivation of the AUC I've seen. $\endgroup$
    – vathymut
    Commented May 3, 2021 at 21:17
  • $\begingroup$ Shouldn't $y(x(\tau))=y(\tau)$ be $y(x(\tau))=y(x)$ (your last line before the equation)? $\endgroup$
    – ado sar
    Commented Apr 5 at 18:52
7
$\begingroup$

Turns out I wrote a medium article just for that.

TL;DR : to go through the end of the demonstration, one needs to use the convolution theorem.

If you don't want to change sites, here is the full trick. We want to show that, for a given binary classifier, :

$$ROC-AUC = P\left(X_1>X_0\right) = P\left(X_1-X_0>0\right)$$

where :

  • X₁ is a continuous random variable giving the “score” output by our binary classifier for a randomly chosen positive sample
  • X₀ is a continuous random variable giving the “score” output by our binary classifier for a randomly chosen negative sample

Definitions and preliminary results

First, some definitions :

  • Let X₁ and X₀ be defined as above
  • Let f₁ and f₀ be, respectively, the density function of X₁ and X₀
  • Let F₁ and F₀ be, respectively, the repartition function of X₁ and X₀
  • True Positive Rate (TPR) and False Positive Rate (FPR) have their usual meaning, i.e. :

$$TPR=\frac{TP}{P}\:\:\,FPR=\frac{FP}{N}$$

We can already observe that, for a classifier threshold T, a randomly chosen positive sample would be correctly classified (true positive) if X₁>T. So, for a randomly chosen positive sample, the probability of correctly classifying it is P(X₁>T). By definition of the TPR, it corresponds to the probability of correctly classifying a randomly chosen positive sample, so TPR(T) = P(X₁>T) = 1- P(X₁⩽ T) = 1-F₁(T). (1)

This also means, by definition of the density function, that :

$$TPR(T) = \int\limits_{T}^{+\infty} f_1(x)\: \mathrm{d}x$$

Similarly, we can show that FPR(T) = 1- F₀(T) (2) Demonstration

Now let’s dig into the calculus!

By definition of the ROC, we have that :

$$ROC-AUC = \int\limits_0^1 TPR(FPR)\: \mathrm{d}FPR$$ $$= \int\limits_0^1 TPR(FPR^{-1}(x))\: \mathrm{d}x$$

By using this change in variable :

$$T=FPR^{-1}(x)\iff\ x=FPR(T)$$

the integral becomes :

$$\int\limits_{+\infty}^{-\infty} TPR(T) \times FPR'(T)\: \mathrm{d}T$$

Now, thanks to (2) we know that we can express this integral as :

$$\int\limits_{+\infty}^{-\infty} TPR(T) \times (-f_0(T))\: \mathrm{d}T = \int\limits_{-\infty}^{+\infty} TPR(T) \times f_0(T)\: \mathrm{d}T$$

Thanks to (1) we know that this can be expressed as :

$$\int\limits_{-\infty}^{+\infty} \int\limits_{T}^{+\infty} f_1(x)\: \mathrm{d}x \times f_0(T)\: \mathrm{d}T$$

By using this change in variable for the inner integral :

$$v=x-T$$

the integral becomes :

$$\int\limits_{-\infty}^{+\infty} \int\limits_{0}^{+\infty} f_1(v+T)\: \mathrm{d}v \times f_0(T)\: \mathrm{d}T$$ $$= \int\limits_{0}^{+\infty} \int\limits_{-\infty}^{+\infty} f_0(T)\: \mathrm{d}T \times \: f_1(v+T)\: \mathrm{d}v$$

and by using this change in variable for the inner integral :

$$u=v+T$$

it becomes :

$$\int\limits_{0}^{+\infty} \int\limits_{-\infty}^{+\infty} f_1(u)\: \times f_0(u-v)\: \mathrm{d}u \: \mathrm{d}v$$

Do you get where we’re going? Yes, right to the convolution theorem! First, let’s point out that since f₀(t) is a density function of X₀, f₀(-t) is a density function of (-X₀). Then, according to the convolution theorem and assuming the convergence, a density of X₁- X₀=X₁+(- X₀) is :

$$\int\limits_{-\infty}^{+\infty} f_1(u)\: \times f_0(u-v)\: \mathrm{d}u$$

This means that :

$$P\left(X_1>X_0\right)=P\left(X_1-X_0>0\right)$$ $$=\int\limits_{0}^{+\infty} \int\limits_{-\infty}^{+\infty} f_1(u)\: \times f_0(u-v)\: \mathrm{d}u \: \mathrm{d}v$$

And eventually we have that :

$$P\left(X_1>X_0\right) = ROC - AUC$$

$\endgroup$
5
$\begingroup$

The way to calculate AUC-ROC is to plot out the TPR and FPR as the threshold, $\tau$ is changed and calculate the area under that curve. But, why is this area under the curve the same as this probability? Let's assume the following:

  1. $A$ is the distribution of scores the model produces for data points that are actually in the positive class.
  2. $B$ is the distribution of scores the model produces for data points that are actually in the negative class (we want this to be to the left of $A$).
  3. $\tau$ is the cutoff threshold. If a data point get's a score greater than this, it's predicted as belonging to the positive class. Otherwise, it's predicted to be in the negative class.

Note that the TPR (recall) is given by: $P(A>\tau)$ and the FPR (fallout) is given be: $P(B>\tau)$.

Now, we plot the TPR on the y-axis and FPR on the x-axis, draw the curve for various $\tau$ and calculate the area under this curve ($AUC$).

We get:

$$AUC = \int_0^1 TPR(x)dx = \int_0^1 P(A>\tau(x))dx$$ where $x$ is the FPR. Now, one way to calculate this integral is to consider $x$ as belonging to a uniform distribution. In that case, it simply becomes the expectation of the $TPR$.

$$AUC = E_x[P(A>\tau(x))] \tag{1}$$ if we consider $x \sim U[0,1)$ .

Now, $x$ here was just the $FPR$

$$x=FPR = P(B>\tau(x))$$ Since we considered $x$ to be from a uniform distribution,

$$P(B>\tau(x)) \sim U$$ $$=> P(B<\tau(x)) \sim (1-U) \sim U$$ \begin{equation}=> F_B(\tau(x)) \sim U \tag{2}\end{equation}

But we know from the inverse transform law that for any random variable $X$, if $F_X(Y) \sim U$ then $Y \sim X$. This follows since taking any random variable and applying its own CDF to it leads to the uniform.

$$F_X(X) = P(F_X(x)<X) =P(X<F_X^{-1}(X))=F_XF_X^{-1}(X)=X$$ and this only holds for uniform.

Using this fact in equation (2) gives us: $$\tau(x) \sim B$$

Substituting this into equation (1) we get:

$$AUC=E_x(P(A>B))=P(A>B)$$

In other words, the area under the curve is the probability that a random positive sample will have a higher score than a random negative sample.

$\endgroup$
4
  • 1
    $\begingroup$ This explanation is reminiscent of what actuaries sometimes call the Darth Vader rule. See Blitztein and Hwang, Ed. 2, page 230. I'm still looking for the best intuitive explanation to use with my students. $\endgroup$
    – Mkanders
    Commented Feb 23, 2023 at 21:18
  • 1
    $\begingroup$ Why do they call it the darth vader rule? $\endgroup$
    – ryu576
    Commented Feb 23, 2023 at 21:48
  • 1
    $\begingroup$ I don't know. "Actuaries sometimes call it the Darth Vader rule, for obscure reasons; statisticians are more likely to refer to it as finding the expectatioin by integrating the survival function." Bltzstein/Hwang 2nd Edition, p. 230. $\endgroup$
    – Mkanders
    Commented Feb 24, 2023 at 0:21
  • $\begingroup$ I think that the $x$ is completely unnecessary after the first equality. It should be just $\tau$ instead. Otherwise, what are you trying to convey by making $\tau$ a function of $x$ in the term $\tau(x)$? $\endgroup$ Commented Jun 16, 2023 at 20:57
0
$\begingroup$

Let $C$ and $S$ be two random variables over a sample space $\Omega$, such that $C$ is binary while $S$ is continuous. $C$ can either take the value of $0$ or $1$, with $1$ denoting the class of the true positives and false negatives. $S(\Omega)$ is contained within $[0,1]$

$$\begin{align} \text{AUC} &= \int_0^1 TPR(FPR) \space dFPR\\ &= \int_{FPR^{-1}(0)}^{FPR^{-1}(1)} TPR(FRP(\tau)) dFPR(\tau) \\ &= \int_1^0 P( S > \tau \,|\, C=1)dP(S > \tau \, |\,C =0) \\ &= \int_1^0 P( (S | C=1) > \tau)dP((S|C =0) > \tau) \\ &= \int_1^0 P( (S |C=1) > \tau)d\left(\int_{\tau}^{1} p_{\small{S|C=0}}(t)dt\right) \\ &= \int_1^0 P( (S |C=1) > \tau)\left( -p_{\small{S|C=0}}(\tau)d\tau\right) \\ &= -\int_1^0 P((S|C=1) > \tau)p_{\small{S|C=0}}(\tau)d\tau \\ &= \int_0^1 P((S|C=1) > \tau)p_{\small{S|C=0}}(\tau)d\tau \\ &= P((S|C=1) >(S|C=0))\\ \end{align}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.