31
$\begingroup$

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
$\endgroup$
  • 2
    $\begingroup$ To further add to confusion, note that the notation you used for cross entropy is also the same notation used for the joint entropy. I've used $H^x(P, Q)$ for the cross-entropy to avoid confusing myself, but that's for my benefit and I've never seen that notation elsewhere. $\endgroup$ – Michael McGowan Jul 25 '11 at 14:25
24
$\begingroup$

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”?"

$\endgroup$
  • $\begingroup$ Thanks @wolf. I'm inclined to accept this answer. If the first definition is standard, how would you define mutual information? $\endgroup$ – Amelio Vazquez-Reina Jul 23 '11 at 20:42
  • 2
    $\begingroup$ sorry. the first quantity, $IG(Y|X)=H(Y)−H(Y|X)$ is also often called mutual information. That's a case of inconsistent naming. As I said, I don't think there is any consistent, unambiguous, one-to-one correspondence of concepts and names. E.g. "mutual information" or "info gain" is a special case of K-L divergence, so that that wikipedia article is not that far off. $\endgroup$ – wolf.rauch Jul 25 '11 at 4:06
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

Extracting mutual information from textual datasets as a feature to train machine learning model: ( the task was to predict age, gender and personality of bloggers)

enter image description here

$\endgroup$
0
$\begingroup$

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*}

$\endgroup$
0
$\begingroup$

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.

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