Hacker News Reader

Comment by max_ | Hacker News Reader

K-L Divergence is something that Keeps coming up in my research but I still don't understand what it is.

Could someone give me a simple explanation as to what it's is.

And also, what practical use cases does it have?

For me, the intuitive way of understanding it is, "how badly would a gambler lose in the long term, if they keep betting on a game believing the probability distribution is X but it is in actual fact Y". It also explains why KL divergence is assymetric, and why it goes to infinity / undefined when the expected probability distribution has zeros where the true distribution has non-zeros. Suppose an urn can have red, blue and green balls. If the true distribution (X) is that there are no red balls at all, but the gambler believes (Y) that there is a small fraction of red balls, the gambler would lose a bit of money with every bet on red, but overall the loss is finite. But suppose the gambler beleives (Y) there are absolutely no red balls in the urn, but in actual fact (X) there is some small fraction of them. According to the gambler's beliefs it would be rational to gamble potentially infinite money on the ball not being red, so the loss is potentially infinite. There is a parallel here to data compression, transmission, etc (KL divergence between expected and actual distributions in information theory) - if you believe a certain bit sequence will never occur in the input sequence, you won't assign it a code, and so if it ever does actually occur you won't be able to transmit it at all ("infinite loss"). If you beleive it will occur very infrequently, you will assign it a very long code, and so if it actually occurs very frequently your output data will be very long (large loss, large KL divergence).

One intuition is that KL-divergence represents a sort of “distance” between probability distributions. However, this isn’t quite right as it doesn’t satisfy some basic properties a real distance (a norm) would satisfy, including the fact that it isn’t symmetric: KL(Q, P) != KL(P,Q), and it does not satisfy the triangle inequality. Nonetheless, KL(P,Q) gives you a good idea of how “far” is P is from Q: in the context of encoding, if you wanted to come up with an ideal encoding of symbols coming from P, but you guessed Q as the distribution of these symbols, then KL(P, Q) is the extra number of bits you’d have to use. One nice property is that in the case that KL(P,Q) = 0, P and Q are equal (almost everywhere, which for most applications is irrelevant). This makes it useful in the ML context as you can minimize KL divergence and know that the resulting “guessed” distribution is getting closer to the data distribution you’re trying to guess using some parametrized function (an NN).

> it doesn’t satisfy some basic properties a real distance (a norm) would satisfy, including the fact that it isn’t symmetric [...] and it does not satisfy the triangle inequality.

Not sure about "real" but one can have useful distances which are not symmetric like the distance between cities measured in time or in gallons.

It just needs to be clarified that KL divergence isn’t a proper mathematical norm, so it doesn’t behave the way we intuitively think a distance should. As mentioned, it doesn’t satisfy the triangle inequality, which is a basic property for any distance-like function.

In comparison, both of your examples are much closer to norms as they both satisfy the triangle inequality.

For reference, this is what I’m referring to when I say a “norm”:

https://en.m.wikipedia.org/wiki/Norm_(mathematics)

I was just clarifying that norm and distance are not the same as you seemed to imply with "a real distance (a norm)". (And I think one can also intuitively understand that the distance from A to B may not be the same as the distance from B to A as soon as we step outside of geometry.)

In addition to what others have said, it fixes a “bug” in Shannon’s continuous version of the entropy. Shannon assumed you could just replace the sum with an integral and call it a day. However, two bad things happen:

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.

I assume you're referring to his most famous work, where he introduces his maxent stuff? http://bayes.wustl.edu/etj/articles/theory.1.pdf

I would also highly recommend the free and excellent book by MacKay for understanding this: http://www.inference.org.uk/mackay/itila/book.html

My favorite physical interpretation (discrete version):

How many extra bits per character your data compression algorithm would need to store text from distribution P if it (mistakenly) assumed it were drawn from Q.

That is, reserve the shortest “words” for the most common characters based on the assumption that the data will be drawn from Q. Then KL(P||Q) is how much bigger the compressed data will be (per input character) if the data is actually drawn from P.

Lots of different ways of motivating KL, but I think one that's frequently neglected in the ML era is its relationship to a likelihood ratio test. Kullback and Leibler originally characterized the KL divergence as the measure of the ability of discriminate between two distributions (ie. perform a hypothesis test between them), given some set of observations (the thing you're averaging over). You can read their original paper for free if you want to hear it in their own words, Kullback and Leibler 1951, although they go kind of deep on the stat theory.

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.

This likelihood ratio approach highlights the fact that KL divergence is a member of the family of Csiszár F-divergences. These are measures of "distance" between distributions of the form E_Q[ F(p(x)/q(x)) ] where F is any convex function with F(1) = 0. This is kind of a generalization of log-likelihood where F kind of "weights" the badness of ratios different to 1. When F is -log you get KL divergence.

Another curious fact about KL divergences is they are also a Bregman divergence: take a convex function H and define B_H(P, Q) = \sum_x H(p(x)) - H(q(x)) - <∇H(q(x)), p(x) - q(x)>. These generalize pointwise square Euclidean distance. KL is obtained when H(P) is negative entropy \sum_x p(x) log p(x).

I spent a bunch of time studying divergences over distributions (e.g., see my blog post[1]) and in particular these two classes and the really neat fact about KL divergence is that it is essentially the only divergence that is both an F-divergence and a Bregman divergence. This is basically due to the property of log that turns logs of products into sums.

[1]: https://mark.reid.name/blog/meet-the-bregman-divergences.htm...

As for practical use cases, one is to find an approximate optimization to a function

- You want to find the min/max of some probability distribution P(x)

- P(x) is too complicated to find a closed-form min, but you can draw samples from it.

- So instead, you carefully construct some OTHER probability distribution Q(x|θ) that you claim is structurally similar "enough" to P(x), parameterized by θ.

- Now you find the theta which minimizes the KL divergence KL(P(x) || Q(x|θ)), which is equivalent to delivering you the parameters of θ to Q(x|θ) that make it [approximately] "most" similar to P(x) without ever having minimized P(x)

It was a trick that came up a lot when AI consisted of giant Bayesian plate models for each specific task that you had to hand-optimize.

Note that "drawing samples from P(x)" means to have training data drawn from P(x).

You can form the 'empirical' probability distribution P'(x) from your n training samples {x_i}, with P'(x_i) = 1/n and P'(x) = 0 for all other x.

Then finding the θ which minimizes KL(P'(x) ∥ Q(x|θ)) is equivalent to finding the maximum likelihood estimate (MLE) given your training data.

(Note: I don't know what's meant by "the min/max of some probability distribution P(x)" and suggest ignoring that)

MLE | training data

Just writing hand wavily :)

I think KL divergence is best understood through the lens of variational inference. Inference in the Bayesian regime is a balancing act between best explaining the data and “keeping it simple”, by staying close to the prior. KL divergence is the (only) divergence measure that places just the right amount of weight on the prior to make variational inference proper Bayesian inference. I’ve written about it here: http://www.openias.org/variational-coin-toss

Intuitively, it measures the difference between two probability distributions. It's not symmetric, so it's not quite that, but in my opinion, it's good intuition.

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

Your characterization (originally due to Cover, I think) is a strong one because it concretely ties KL divergence to nature. I also like Sanov's theorem for this.

I have sat through many frustrating anti-explanations of the following sort:

>What is KL divergence you ask? Why, it's simply a quantitative difference between distributions. The further away distributions are, the higher KL divergence is... It's like a distance-squared between distributions... but it isn't symmetric and it doesn't obey any usual triangle inequality, so this analogy isn't helpful for analysis... Pinsker's inequality gives a useful lower bound. A useful general upper bound is, uhh,... uh...

This class of answer is totally uninformative (and discrediting if given, IMO) because it does not provide a useful, unique characterization of KL divergence, only fundamentally inaccurate descriptions of it.

It just describes how two probability distributions are different. If they are the same then it’s 0.

Example: an LLM gives a probability distribution of the next word. If it is perfectly accurate at predicting the next word then divergence is 0 (100% probability on the actual next word). If it is slightly off or unsure then the divergence goes up.

It's a useful way of measuring how different two probability distributions are. If F and G are distributions, Kl(F||G) is non-negative real number which is larger if F and G are less similar.

In a lot of statistical estimation procedures, you have some kind of "current estimate" distribution which has nice properties and some kind of "true distribution" which you'd like to use your nice distribution to approximate. It's then common to create a system which manipulates the parameters of your current estimate distribution to minimize the KL-divergence with the true distribution.

A relatively simple example of this is fitting a Gaussian mixture model. If you look up how that process is derived you'll see it depends centrally on minimizing the KL-divergence between two distributions.

There are other ways to measure the difference between two probability distributions, but the KL-divergence has some nice properties. It shows up as the answer to lots of well-motivated questions around statistical inference (Neyman-Pearson testing, information geometry, Bayesian inference, entropy) and it has a form which is somewhat amenable to algebraic manipulation.

In some sense it's popular because it keeps showing up and working. People recognize its form, consider it relatively simple, and find it meaningful to talk about. It's common enough that you might even begin considering a problem by asking if you can minimize the KL-divergence between your estimate and some goal just knowing that outright it will likely lead to a successful solution to your problem.

In the context of Bayesian inference, the KL divergence between the prior p(m) and the posterior p(m|x) is the information gained by observing x.

With VAEs, adding a KL divergence to the loss term can be thought of as regularizing information gain from individual inputs.

One practical use might be assessing the similarity of a high-dimensional data set and its low-dimensional projection, as used in e.g. t-SNE.

Here is another view, which also explains where the logarithm comes from.

The KL between two distributions of a random variable, say Kl[p|q], says that if you made a perfect compression algorithm for samples from distribution q, how many extra bits/nats you expect to need to code samples that actually come from p instead if you use that compression algorithm.

And compression is all about keeping only the true information that is encoded in a sample.

One use case is in the training of Diffusion Models. In the original formulation, the likelihood-maximizing objective is recast in terms of KL divergences. This is done because the KL divergence between Gaussians has a closed form, and the transition distributions in Diffusion Models are taken to be Gaussian, which makes the problem tenable.

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

My intro to K-L divergence was in the context of maximum likelihood estimation with a misspecified model. The asymptotic expected value of a parametric MLE is the parameter value that minimizes the K-L divergence from the true distribution to the model. That means that when the parametric model contains the true distribution, the MLE is a consistent estimator (as is well known). But it also gives you a way of analytically finding the (asymptotic) bias of the MLE when the model does not contain the true distribution.

"The content of an information itself, maybe a signal, random variable, or event",

"...defined through a negative logarithm of probability",

"...to model a given outcome", occurred.

P-:

Reply on news.ycombinator.com