Where does the Kullback-Leibler come from? [duplicate]

Question

Let $p(x)$ be some "true" distribution which we want to model using a simpler distribution $q(x)$. Why is the KL divergence $$KL(q||p)=\int q(x)\log{\frac{q(x)}{p(x)}}$$ a good way to represents the loss of information in using $q$ instead of $p$? Is the KL divergence some "ad hoc method" or it has a deeper meaning? Shouldn't be the entropy difference $$H(q)-H(p)$$ the right quantity to use?

Answer 1

KL divergence is very closely related to entropy. It helps to understand the motivation behind the expression for entropy.

For some distribution $p(x)$ we call $h(x) = -\log p(x)$ the information received by observing variable $x$. It's called "information" because it has the nice property that if we observe two completely independent events, $x$ and $y$, then the information gained is the sum of the information gained from each event. I.e. if $x$ and $y$ are independent, $p(x,y) = p(x) p(y),$ then $h(x,y) = -\log p(x) - \log p(y) = h(x) + h(y).$ Likewise, if $x$ and $y$ are completely mutually occurring, then it follows that observing $x$ and $y$ simply gives us the exact same information as observing $x$ alone. That is $p(x,y) = p(x) \implies h(x,y) = h(x).$ Also, this form of $h(x)$ ensures that the information gained is always positive, and more information is gained by observing events that are less likely.

To that end, entropy is the expected amount of information gained by observing a variable drawn from a distribution $p$. That is, $$ H[p] = E[h_p(x)] = \int p(x) h_p(x) dx = - \int p(x) \log p(x) dx, $$

where I'm calling $h_p(x)$ the information gained from observing $x$ if $x$ is drawn from distribution $p.$

The KL divergence is often used in situations where $p$ is some unknown true distribution, and $q$ is a proxy distribution that we're using to estimate $p.$ $KL(p \mid \mid q)$ is the expected difference in information received by observing $x$ if $q$ was the true distribution, vs if $p$ was the true distribution, and that expectation is taken over a single distribution. Another way of saying it is that it's the expected additional information we need to receive from observing $x$ in order to get all the information we need.

Suppose you couldn't draw from $p(x)$ but could only evaluate it for a given $x$ (or, at the very least, you could evaluate the ratio $p(x)/q(x)$). But you could draw from your proxy distribution $q(x),$ and you want to learn $p.$ Then the expected deficit of information you gain (or the expected additional information you need to gain in order to learn $p$) is

$$ KL(q \mid \mid p) = E_q[h_p(x) - h_q(x)] = \int q(x) [h_p(x) - h_q(x)] dx = \int q(x) \log \frac{q(x)}{p(x)} dx. $$

I gave an intuitive interpretation of the $KL$ divergence, but one thing about this form is that it's guaranteed to be non-negative. Even though individual instances of $q(x) \log \frac{q(x)}{p(x)}$ might be negative, the instances where $q>p$ will outweigh the others. (More explicitly, the Gibbs' inequality guarantees that it's non-negative.) This means that, as long as $p(x)$ is the true distribution you will always need more information if you're using a proxy, $q(x),$ to draw from. By contrast, your suggestion of using $H[q] - H[p]$ has no such guarantee.