KL-Divergence and the chain rule

Question

I was trying to understand the mathematical proof of KL-Divergence when using the chain rule:

$D(p(x,y)||q(x,y)) = D(p(x)||q(x)) + D(p(y|x)||q(y|x))$

And I'm a bit lost in the last step (https://www.cs.princeton.edu/courses/archive/fall11/cos597D/L03.pdf, 1.3 Conditional Divergence). What I don't understand is why is this true?

$D(p(x)||q(x)) = \sum_x \sum_y p(x, y) log \frac{p(x)}{q(x)}$

The definition says something slightly different:

$D(p(x)||q(x)) = \sum_x p(x) log \frac{p(x)}{q(x)}$

I have also seen this written in another way that I still don't understand (https://homes.cs.washington.edu/~anuprao/pubs/CSE533Autumn2010/lecture3.pdf, 2.3 Conditional Divergence):

$D(p(x)||q(x)) = \sum_x p(x) log \frac{p(x)}{q(x)} \sum_y p(y|x)$

Why is that last part $\sum_y p(y|x)$ also absorbed into the KL definition?

gunes · Accepted Answer · 2019-02-21T13:16:34.867

2

First of all, $\sum_y{p(x,y)}=p(x)$, because you're fixing $x$ and summing over all possible $y$. Therefore, $$\begin{align}D(p||q) &= \sum_x \sum_y p(x, y) log \frac{p(x)}{q(x)}\\ &= \sum_x log \frac{p(x)}{q(x)} \sum_y p(x, y) \\ &= \sum_x log \frac{p(x)}{q(x)} p(x)\end{align}$$, which is what the definition says.

For the latter part, from the definition of joint PMF, we have $p(x,y)=p(x)p(y|x)$. So, $$\sum_y{p(x,y)}=\sum_y p(x)p(y|x)=p(x)\sum_y p(y|x)$$, which explains the factorization in the KL formulation.

edited Feb 21 '19 at 13:16

answered Feb 21 '19 at 13:00

gunes

57,205

It was p(y|x), sorry. – kuonb Feb 21 '19 at 13:12
OK, I have also commented on the last part. – gunes Feb 21 '19 at 13:17
And, @user20160's comment on $\sum_y p(y|x)=1$ is another good point by the way. – gunes Feb 21 '19 at 13:23

score 1 · Answer 2 · answered Feb 21 '19 at 12:59

What I don't understand is why is this true? $$D(p(x) \parallel q(x)) = \sum_x \sum_y p(x, y) \log \frac{p(x)}{q(x)}$$

$\log \frac{p(x)}{q(x)}$ doesn't depend on $y$, so it can be moved out of the inner sum:

$$D(p(x) \parallel q(x)) = \sum_x \log \frac{p(x)}{q(x)} \sum_y p(x, y)$$

$\sum_y p(x, y) = p(x)$ by the definition of marginal probability. Plugging this in gives the canonical expression for KL divergence:

$$D(p(x) \parallel q(x)) = \sum_x p(x) \log \frac{p(x)}{q(x)}$$

Why is that last part $\sum_y p(y \mid y)$ also absorbed into the KL definition?

I don't see that in the notes you linked. Maybe a typo? Assuming you meant $\sum_y p(y \mid x)$, then this is equal to one, since a probability distribution must sum to one by definition.

KL-Divergence and the chain rule

2 Answers2