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.
 A: 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{equation}
 \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}
\end{equation}
A: $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.
