Kullback–Leibler divergence

Say you're flipping a coin N times, and you get outcomes x_1, x_2, ...., x_N. You want to determine whether the coin comes up heads with probability P or probability Q (kind of a weird fiction that there are only two options, but roll with it). The classic way to do this would be a likelihood (log) ratio test, you compute this test statistic:

Y = log( Pr[x_1,...,x_n|P] / Pr[x_1,...,x_N|Q] )

Depending on the value of Y you make a decision about whether to go with P or Q, and IMO the definition makes intuitive sense for this purpose: if Y is positive then you favor P, if Y is negative you favor Q. If it's 0 then you can't pick between them. Simple and easy, plus the Neyman-Pearson lemma basically says that it's the best you could do (among the set of decision making criteria which satisfy a certain set of desirable properties).

Having defined your test statistic Y, you might then ask what kind of values you can expect to get, even before you make any experimental measurements. Well, if you assume that P is the true probability (the null hypothesis) then E_X[Y|P,Q] = KL[P|Q]. Basically the expected value of the log-likelihood ratio, the thing you would use to decide between P and Q, characterizes how similar or different they are. When the expected value is close to 0, and hence P and Q are similar, then before conducting the experiment you can expect that it will be hard to distinguish between them. When the divergence is very large then you can expect it will be easy.

Minimizing mean-squared-error loss is equivalent to minimizing KL divergence (and thus cross entropy) under the assumption that your model produces a vector that parameterizes the mean of a multivariate Gaussian distribution which is then used to predict your data. This is the most natural way to set up a model that predicts continuous data.

https://www.assemblyai.com/blog/diffusion-models-for-machine...

As motivation, say you're an internet provider, providing internet service to a business. You naturally want to save money, so you perhaps want to compress packets before they go over the wire. Let's say the business you're providing service to also compresses their data, but they've made a mistake and do it inefficiently.

Let's say the business has, incorrectly, determined the probability distribution for their data to be $q(x)$. That is, they assign probability of seeing symbol $x$ to be $q(x)$. Let's say you've determined the "true" distribution to be $p(x)$. The entropy, or number of bits, they expect to transmit per packet/symbol will be $-\sum p(x) lg(q(x))$. Meaning, they'll compress their stream under the assumption that the distribution is $q(x)$ but the actually probability of seeing a packet, $x$, is $p(x)$, which is why the term $p(x) lg(q(x))$ shows up.

The number of bits you're transmitting is just $-\sum p(x) lg(p(x))$. Now we ask, how many bits, per packet, is the savings of your method over the businesses? This is $-\sum p(x) lg(q(x)/p(x))$, which is exactly the Kullback-Leibler divergence (maybe up to a sign difference).

In other words, given a "guess" at a distribution and the "true" distribution, how bad is it between them? This is the Kullback-Leibler distribution and why it shows up (I believe) in machine learning and fitness functions.

As a more concrete example, I just ran across a paper talking [0] about using WFC [1] to asses how well it, and other algorithms, do when trying to create generative "super mario brothers" like levels. Take a 2x2 or 3x3 grid, make a library of tiles, use that to generate a random level, then use the K-L divergence to determine how well your generative algorithm has done compared to the observed distribution from an example image.

[0] https://arxiv.org/pdf/1905.05077.pdf

[1] https://github.com/mxgmn/WaveFunctionCollapse

1. This definition of entropy is not invariant to coordinate transforms. If you change the parameters of your distribution, you get a different value for the entropy, despite the change of parameters not adding or removing information.

2. You can get negative values for the entropy.

Jaynes argued (in a way that’s quite readable if you find his original paper, I’m on mobile) that really you should pick a base reference measure q and define the entropy as -KL(p; q). This fixes the first bug which is the critical one. The second bug is halfway fixed because this quantity is always non-positive. However that’s alright because often we really care about the change in entropy not the absolute value (like how we care about the change in potential energy not the absolute value).

This gets at why the KL divergence is often called the relative entropy. It is the entropy relative to the reference measure q.