5
$\begingroup$

This is a similar question to this one (which has unfortunately no answer yet), although I believe my question is more specific.

Let $X$ and $Y$ be two discrete random variables with outcome space, respectively, $\mathcal X$ and $\mathcal Y$. Then, the mutual information between $X$ and $Y$ is

$$I(X,Y) = -\sum_{x\in \mathcal X, y\in \mathcal Y}p_{X,Y}(x,y)\log \left(\frac{p_{X}(x)p_Y(y)}{p_{X,Y}(x,y)}\right),$$

where $p_X$ is the marginal pmf of $X$ and $p_{X,Y}$ is the joint distribution of $X$ and $Y$. The lower bound of the mutual information is zero, which occurs if and only if $X$ and $Y$ are independent. The upper bound of $I(X,Y)$, on the other hand, cannot exceed the entropies of either $X$ nor $Y$. So,

$$I(X,Y)\le \min\{H(X),H(Y)\},$$

where $H(X) = - \sum_{x\in \mathcal X} p_X(x)\log p_X(x)$.

Because of the variable upper bound of $I(X,Y)$, a normalized version of the mutual information is often used in research on, say, clustering comparisons. The most often used normalied versions that I've encountered are

$$ I_{AM}(X,Y) = \frac{I(X,Y)}{\frac{1}{2}[H(X)+H(Y)]} \quad \text{and}\quad I_{GM}(X,Y) = \frac{I(X,Y)}{\sqrt{H(X)H(Y)}}.$$

But

$$\min\{H(X),H(Y)\}\le HM(H(X),H(Y)) \le GM(H(X),H(Y)) \le AM(H(X),H(Y)) \le \max\{H(X),H(Y)\}$$

with equality if and only if $H(X)=H(Y)$, where $HM, GM$, and $AM$, respectively, stand for the harmonic, geometric, and arithmetic mean. So, the harnomic mean between the entropies would give us a tighter upper bound on the mutual information. I was wondering whether there is a specific reason why the geometric and arithmetic means are preferred for normalizing the mutual information.

Any suggestions would help. Thanks!

$\endgroup$
2
+50
$\begingroup$

The reason the Harmonic Mean is never mentioned as a normalization for MI is that it renders the measure equivalent to another commonly used clustering comparison method, the normalized Variation of Information (VI), where the regular VI is defined as:

\begin{equation} VI(X,Y) = H(X|Y) + H(Y|X) \end{equation}

and the normalized VI is defined as (see Appendix B from Lancichinetti et al; 2009):

\begin{equation} VI_{\text{norm}}(X,Y) = \frac{1}{2}\left(\frac{H(X|Y)}{H(X)} + \frac{H(Y|X)}{H(Y)}\right) \end{equation}

To see this, we use the relationship for condition entropy: $H(Y|X) = H(X,Y) - H(X)$

\begin{array} aI_{HM}(X,Y) &= \frac{H(X) + H(Y)-H(X,Y)}{\frac{2}{\frac{1}{H(X)}+\frac{1}{H(Y)}}} \\ &= \frac{H(X) + H(Y)-H(X,Y)}{2H(X)}+\frac{H(X) + H(Y)-H(X,Y)}{2H(Y)} \\ &= \frac{1}{2} - \frac{ H(X,Y) - H(Y)}{2H(X)}+\frac{1}{2} - \frac{ H(X,Y) - H(X)}{2H(Y)}\\ &= 1 - \frac{1}{2}\left(\frac{H(X|Y)}{H(X)} + \frac{H(Y|X)}{H(Y)}\right) \\ &= 1 - VI_{\text{norm}}(X,Y) \end{array}

$\endgroup$
  • $\begingroup$ Great answer. Thanks! One additional question from a newbie: It seems that the variation of information has some desirable properties for clustering comparisons. If the mutual information normalized by the harmonic mean coincides with $1 - VI_{norm}$, would this not be a good reason to use $I_{HM}$ instead of other normalizations? $\endgroup$ – baruuum Feb 23 at 21:55
  • 1
    $\begingroup$ Without sounding trite, a full answer to that question is beyond the character limits of this comment space ; ). If you want to ask it as a regular question, I would be happy to elaborate. This arXiv paper also touches on the drawbacks of information theoretic measures. $\endgroup$ – ComplexGates Feb 24 at 0:08

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.