# Information gain is KL divergence

I am slightly confused by the the statement that Kullback–Leibler divergence is the same as [information gain](Information gain in decision trees).

I cannot understand how $D_{KL}(P||Q) = H(P,Q)- H(P)$ can be represent as $IG(T,a) = H(T)-H(T|a)$

I would appreciate for explanation.

$Q$ is "wrong" distribution, while $P$ is the "right" distribution. The length of a code $i$ under the "wrong" coding is $-log(q_{i})$. So, the average message length under the "wrong" coding is:

$-\sum p_{i} log(q_{i}) = H(P,Q)$

Under the "right" coding, the average message length is $H(P)$. Imagine that we are using entropy coding like arithmetic coding, but we have not estimated the probability distribution right. Then the average message length is a bit larger then the theoretical limit $H(P)$. The difference is Kullback–Leibler divergence.

• Thank you very much for your answer, the problem is in wikipedia it is written than $D_{KL}$ is information gain, I simply cannot derive one formula from another, I cannot write a proof that it's indeed the same. Jun 13 '14 at 4:40
• Maybe you shouldn't take the definition of "information gain" quite so literally. Jun 13 '14 at 20:11
• The thing is that "information gain" is a term widely used in machine learning because of C4.5, a popular algorithm for learning decision trees. Jan 2 '16 at 5:53

I found myself stuck with the same question in the past. Here's a series of relationships that may help to understand differences between Mutual Information (MI), Information Gain(IG) and Kullback–Leibler divergence (DKL). I used a simplified version of Wikipedia notation.

\begin{aligned} MI(X,A) =& \sum_a P(a) IG_{X,A}{(X,a)} \\ &=\sum_a P(a) D_{\text{KL}}{\left(P{(x|a)}\|P{(x|I)}\right)}\\ &=-\sum_{a,x} P(a) P{(x|a)} \ln \left(\frac{P{(x)}}{P{(x|a)}}\right) \\ &=-\sum_{a,x} P(a) P{(x|a)} \ln \left(\frac{P{(x)}P(a)}{P{(x|a)}P(a)}\right) \\ &=-\sum_{a,x} P(x,a) \ln \left(\frac{P{(x)}P(a)}{P(x,a)}\right) \\ &\equiv D_{\text{KL}}{\left(P(x,a)\|P{(x)}P(a)\right)}\\ &= -\sum_{a,x} P{(x|a)} P(a) \ln \left(P{(x)}\right) +\sum_{a,x} P(a) P{(x|a)} \ln \left(P{(x|a)}\right)\\ &= -\sum_{x} P{(x)} \ln \left(P{(x)}\right) +\sum_{a,x} P(a) P{(x|a)} \ln \left(P{(x|a)}\right)\\ &\equiv H(x) - H(x|a) \end{aligned}