20
$\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$
1
11
$\begingroup$

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 easiliy be seen to be 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.

This proof is taken from: https://pdfs.semanticscholar.org/1fcb/f15898db36990f651c1e5cdc0b405855de2c.pdf

$\endgroup$
0
7
$\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)$

$$\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$
1
  • $\begingroup$ This is one of the most concise and elegant derivation of the AUC I've seen. $\endgroup$
    – vathymut
    May 3 at 21:17
4
$\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$
1
$\begingroup$

Turns out I wrote a medium article just for that! Here it is :

https://medium.com/@nathanaim/mathematics-behind-roc-auc-interpretation-e4e6f202a015

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$$

Thanks for reading this far! Hope I helped :)

$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .