Feature Selection: Information Gain VS Mutual Information

Question

Setting: Multi-class classification problem with discrete nominal features.

There are many references mentioning the use of IG(Information Gain) and MI (Mutual Information) as measure of feature relevancy for filter-based feature selection. However, from the information-theoretic viewpoint it's not completely clear to me what is the difference between these two (and if there is any):

IG(X,Y) ?=? MI(X,Y) = H(X)-H(X|Y) = H(Y)-H(Y|X) = H(X) + H(Y) - H(X,Y) = ...

Notes:

• There are many ways to estimate MI either in Matlab, R or even by hand with toy example. However, I couldn't find a single reference mentioning both measures and the differences between them.

• My calculation (and understanding) of MI for discrete features returns the expected results and match existing MI f-ns (in R, Matlab). However, Weka has a f-n InfoGainAttributeEval: http://weka.sourceforge.net/doc.dev/weka/attributeSelection/InfoGainAttributeEval.html, which produces IG measure that is not equal to MI for the same data.

• There are some similar questions in SE forums and all suggest equivalence of IG and MI (e.g. Information gain, mutual information and related measures). In that case - how IG is calculated in Weka and why it doesn't match MI?

• Weka's IG is available from http://featureselection.asu.edu/documentation/infogain.htm in the context of feature selection

ANSWER:

Please see accepted answer below. There is no indication that MI and IG have different meaning in context of information theory - they are the same measures.

Regarding WEKA and different results. I have used Feature Selection package, which always assumed continuous attributes and therefore Weka's discretization was applied before computing Information Gain. Running IG directly from WEKA without discretization, produced the result equivalent to MI.

Answer 1

They are identically the same.

If $X$ is a nominal feature with $k$ different values and $C$ is your target class with $m$ classes.

\begin{align} \mbox{MI} &= \sum_{i=1}^k\sum_{j=1}^m P(x_i,c_j)\log \frac{P(x_i,c_j)}{P(x_i)P(c_j)}\\ &=-\sum_{i=1}^k\sum_{j=1}^m P(x_i,c_j)\log P(c_j) + \sum_{i=1}^k\sum_{j=1}^m P(c_j|x_i)P(x_i)\log P(c_j|x_i)\\ &= -\sum_{j=1}^m P(c_j)\log P(c_j) + \sum_{i=1}^kP(x_i)\sum_{j=1}^m P(c_j|x_i)\log P(c_j|x_i)\\ &= H(C) - H(C|X) = \mbox{IG} \end{align}

This is a case of inconsistent naming. You might want to have a look at this question too.