2
$\begingroup$

When evaluating a binary classifier, the basic data are as in this contingency table, where rows represent groundtruth value and columns represent the estimated value: $$ \begin{matrix} & + & - \\ \hline + & a & b \\ - & c & d \end{matrix} $$ where $a$ is the number of true positives, $c$ the number of false positives, etc. This information is often summarised on a ROC curve using the "true positive rate" and "false positive rate" statistics: $$ t = \frac{a}{a+b} \\ f = \frac{c}{c+d} $$ and from this we can calculate single values which summarise the performance, such as Area Under the Curve (AUC) (with only one contingency table, we can use $\text{AUC} = (t-f+1)/2$).

Another thing we could calculate is the mutual information between the estimated values and groundtruth values. This is a classic statistic that would tell us about the probabilistic relationship between our estimates and the groundtruth. In this case: $$ I = \frac{a}{n}\log{\frac{a n}{(a+b)(a+c)}} + \frac{b}{n}\log{\frac{b n}{(a+b)(b+d)}} + \frac{c}{n}\log{\frac{c n}{(c+d)(a+c)}} + \frac{d}{n}\log{\frac{d n}{(b+d)(c+d)}} $$ where $n=a+b+c+d$ and $0\log(0)=0$.

Calculating mutual information is straightforward if we know $a, b, c, d$. But what if we know only $t$ and $f$?

Clearly if all we know is $t$ and $f$ we can't directly calculate the mutual information, because the relative scale between $a$ and $b$ on one hand, and $c$ and $d$ on the other, isn't captured. But we must be able to lower-bound it. Here's a plot from random samples showing the relationship between AUC and mutual information:

auc vs mi

I've tried a few ways of writing out the mutual information but not been able to get it into a form where $t$ and $f$ lead to interesting bounds. Can you?

$\endgroup$

migrated from stats.stackexchange.com Nov 1 '13 at 19:52

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

1
$\begingroup$

Here's part of the answer...

We know that the mutual information is upper-bounded by the entropy of either of the marginal distributions (at least for discrete distributions, as here). So the maximum possible value for $I$ is when the ground-truth is fiftyfifty split between $+$ and $-$, i.e. when $a + b = c + d = n/2$. (In that case the entropy comes out as $\log(2)$.)

So, consider the case of $a + b = c + d = n/2$. In that situation we have the following: $$ a = \frac{n t}{2}, \quad b = \frac{n(1-t)}{2}, \quad c = \frac{n f}{2}, \quad d = \frac{n (1-f)}{2}, $$ which can be substituted into the expression for $I$ given in the OP. After some rearrangement, this gives us $$ I_{\text{fiftyfifty}} = \frac{1}{2}(2\log(2) + t\log(t) + f\log(f) - (t+f)\log(t+f) + (1-t)\log(1-t) + (1-f)\log(1-f) + (2-f-t)\log(2-f-t)) $$

If we evaluate this in the ideal case (perfect prediction means $t=1$ and $f=0$), we get a value for $I_{\text{fiftyfifty}}$ as $\log(2)$, the maximum attainable. Any other choices for $t$ and $f$ lead to lower values.

Therefore in the fiftyfifty case, the maximum possible mutual information is attainable for a specific choice of $t$ and $f$; and because the mutual information is bounded by the entropy, and all other binary distributions have a lower entropy than the fiftyfifty case, there is no other case that can reach this maximum.

I haven't yet shown that $I_{\text{fiftyfifty}} \ge I$ for all possible choices of $t$ and $f$. Nor have I expressed a bound directly in terms of the AUC value, which was not my question but is an optional extra.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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