Information gain, mutual information and related measures

Question

Andrew More defines information gain as:

$IG(Y|X) = H(Y) - H(Y|X)$

where $H(Y|X)$ is the conditional entropy. However, Wikipedia calls the above quantity mutual information.

Wikipedia on the other hand defines information gain as the Kullback–Leibler divergence (aka information divergence or relative entropy) between two random variables:

$D_{KL}(P||Q) = H(P,Q) - H(P)$

where $H(P,Q)$ is defined as the cross-entropy.

These two definitions seem to be inconsistent with each other.

I have also seen other authors talking about two additional related concepts, namely differential entropy and relative information gain.

What is the precise definition or relationship between these quantities? Is there a good text book that covers them all?

• Information gain
• Mutual information
• Cross entropy
• Conditional entropy
• Differential entropy
• Relative information gain

Answer 1

I think that calling the Kullback-Leibler divergence "information gain" is non-standard.

The first definition is standard.

EDIT: However, $H(Y)−H(Y|X)$ can also be called mutual information.

Note that I don't think you will find any scientific discipline that really has a standardized, precise, and consistent naming scheme. So you will always have to look at the formulae, because they will generally give you a better idea.

Textbooks: see "Good introduction into different kinds of entropy".

Also: Cosma Shalizi: Methods and Techniques of Complex Systems Science: An Overview, chapter 1 (pp. 33--114) in Thomas S. Deisboeck and J. Yasha Kresh (eds.), Complex Systems Science in Biomedicine http://arxiv.org/abs/nlin.AO/0307015

Robert M. Gray: Entropy and Information Theory http://ee.stanford.edu/~gray/it.html

David MacKay: Information Theory, Inference, and Learning Algorithms http://www.inference.phy.cam.ac.uk/mackay/itila/book.html

also, "What is “entropy and information gain”?"

Answer 2

The Kullback-Leiber Divergence between $p(X,Y)$ and $P(X)P(Y)$ is the same as mutual information, which can be easily derived:

$$ \begin{align} I(X; Y) &= H(Y) - H(Y \mid X)\\ &= - \sum_y p(y) \log p(y) + \sum_{x,y} p(x) p(y\mid x) \log p(y\mid x)\\ &= \sum_{x,y} p(x, y) \log{p(y\mid x)} - \sum_{y} \left(\sum_{x}p(x,y)\right) \log p(y)\\ &= \sum_{x,y} p(x, y) \log{p(y\mid x)} - \sum_{x,y}p(x, y) \log p(y)\\ &= \sum_{x,y} p(x, y) \log \frac{p(y\mid x)}{p(y)}\\ &= \sum_{x,y} p(x, y) \log \frac{p(y\mid x)p(x)}{p(y)p(x)}\\ &= \sum_{x,y} p(x, y) \log \frac{p(x, y)}{p(y)p(x)}\\ &= \mathcal D_{KL} (P(X,Y)\mid\mid P(X)P(Y)) \end{align} $$

Note: $p(y) = \sum_x p(x,y)$

Answer 3

Both definitions are correct, and consistent. I'm not sure what you find unclear as you point out multiple points that might need clarification.

Firstly: $MI_{Mutual Information}\equiv$ $IG_{InformationGain}\equiv I_{Information}$ are all different names for the same thing. In different contexts one of these names may be preferable, i will call it hereon Information.

The second point is the relation between the Kullback–Leibler divergence-$D_{KL}$, and Information. The Kullback–Leibler divergence is simply a measure of dissimilarity between two distributions. The Information can be defined in these terms of distributions' dissimilarity (see Yters' response). So information is a special case of $K_{LD}$, where $K_{LD}$ is applied to measure the difference between the actual joint distribution of two variables (which captures their dependence) and the hypothetical joint distribution of the same variables, were they to be independent. We call that quantity Information.

The third point to clarify is the inconsistent, though standard notation being used, namely that $\operatorname{H} (X,Y)$ is both the notation for Joint entropy and for Cross-entropy as well.

So, for example, in the definition of Information: \begin{aligned}\operatorname {I} (X;Y)&{}\equiv \mathrm {H} (X)-\mathrm {H} (X|Y)\\&{}\equiv \mathrm {H} (Y)-\mathrm {H} (Y|X)\\&{}\equiv \mathrm {H} (X)+\mathrm {H} (Y)-\mathrm {H} (X,Y)\\&{}\equiv \mathrm {H} (X,Y)-\mathrm {H} (X|Y)-\mathrm {H} (Y|X)\end{aligned} in both last lines, $\operatorname{H}(X,Y)$ is the joint entropy. This may seem inconsistent with the definition in the Information gain page however: $DKL(P||Q)=H(P,Q)−H(P)$ but you did not fail to quote the important clarification - $\operatorname{H}(P,Q)$ is being used there as the cross-entropy (as is the case too in the cross entropy page).

Joint-entropy and Cross-entropy are NOT the same.

Check out this and this where this ambiguous notation is addressed and a unique notation for cross-entropy is offered - $H_q(p)$

I would hope to see this notation accepted and the wiki-pages updated.

Answer 4

Mutual information can be defined using Kullback-Liebler as \begin{align*} I(X;Y) = D_{KL}(p(x,y)||p(x)p(y)). \end{align*}