7
$\begingroup$

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:

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.

$\endgroup$
0

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Thanks, that's what I'm thinking this way too - as I wrote, math tells exact equivalence. Are you familiar with Weka? I'm wondering where is the discrepancy coming from. $\endgroup$ Sep 24, 2014 at 23:37
  • $\begingroup$ I guess the discrepancy originated from the first articles on decision trees: about ID3 and C4.5. It was appealing to maximize the information gain to the class due to a split according to a feature. Then this term started to be commonly used in machine learning. However this is just my guess. $\endgroup$
    – Simone
    Sep 24, 2014 at 23:49
  • $\begingroup$ That is good to know! It seems that it can be concluded that it is just a matter of ambiguous naming. The only open question is how Weka produces different results $\endgroup$ Sep 25, 2014 at 0:28
  • $\begingroup$ What are you comparing weka with? are all features categorical with no missing values? $\endgroup$
    – Simone
    Sep 25, 2014 at 0:32
  • 1
    $\begingroup$ I just figured out that in these references the authors do not use Mutual Information but actually something called pointwise mutual information: en.wikipedia.org/wiki/Pointwise_mutual_information. Maybe try to post your examples here and the correspondent Weka outcome. $\endgroup$
    – Simone
    Sep 25, 2014 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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