3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

$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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user16168 Jun 13 '14 at 4:40
  • $\begingroup$ Maybe you shouldn't take the definition of "information gain" quite so literally. $\endgroup$ – Dmitry Negoda Jun 13 '14 at 20:11
  • $\begingroup$ 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. $\endgroup$ – hectorpal Jan 2 '16 at 5:53
0
$\begingroup$

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}

$\endgroup$

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.