I am curious about definition of information gain and mutual information in the context of feature selection.

It looks like two these measures define exactly the same thing, however I didn't find that someone stated it explicitly that "IG and I are the same".

In wikipedia you could find: "in the context of decision trees, the term is sometimes used synonymously with mutual information".

In An introduction to information retrieval: "Show that mutual information and information gain are equivalent", page 285, exercise 13.13.

No one says that it's exactly the same.

$I(X;Y) = H(X) - H(X|Y)$

$IG(X;Y) = H(X) - \sum_{y \in values(Y)} \frac{|X_y|}{|X|}H(X_y)$

the task is to show that $\sum_{y \in Y} \frac{|X_y|}{|X|}H(X_y) = H(X|Y)$ or not.

$\sum_{y \in Y} \frac{|X_y|}{|X|}H(X_y) =\sum_{x \in X, y \in Y}^{} p(x,y) \log \frac{p(y)}{p(x,y)}$

$\sum_{y \in Y} \frac{|X_y|}{|X|}\sum_{x \in X_y}^{}p(x)\log\frac{1}{p(x)} =\sum_{x \in X, y \in Y}^{} p(x,y) \log \frac{p(y)}{p(x,y)}$

I am stuck here, I would appreciate any help.

if they are not equal, what "equivalent" and "synonym" mean? What are the properties of both of them for feature selection?


Firstly "equivalent" with respect some context may mean that maximizing/minimizing one is equivalent to maximizing the other.

But anyway the generally accepted definitions, i.e. those given in wiki and in books, are NOT the same. In fact Mutual Information (MI) is defined in terms of Kullback Leibler divergence (KL) (aka Information Gain) as follows:

ML(X, Y) = KL( p(X, Y) || p(X) p(Y) )

In other words MI is defined as the KL between the joint probability of X & Y and the probability we would get if we assumed the distributions are independent. So MI is to mean "how dependent are these variables", whereas KL is a general measure of "how much information do I need given X to get to Y".

If you look at the actual equations on wiki, you will see they are different.

Finally wiki even says that MI is symmetric, whereas KL is not - so this is an easy indication they are NOT THE SAME.

Suggest reading "Concepts in Statistical Mechanics" - Arthur Hobson for the proof of why KL is the only measure of information that satisfies the set of reasonably accepted axioms.


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.