This is a linkpost for https://www.perfectlynormal.co.uk/blog-kl-divergence

Six (and a half) intuitions for KL divergence

12th Oct 2022

11tailcalled

16CallumMcDougall

7jsd

1CallumMcDougall

6Joseph Van Name

4Steveot

3lalaithion

1CallumMcDougall

2Zack_M_Davis

2CallumMcDougall

2TekhneMakre

1CallumMcDougall

1CallumMcDougall

2TekhneMakre

1[anonymous]

1Nina Rimsky

1CallumMcDougall

1Ethan (EJ) Watkins

1Ethan (EJ) Watkins

1CallumMcDougall

1DeLesley Hutchins

1CallumMcDougall

1Archimedes

1Ulisse Mini

1CallumMcDougall

New Comment

25 comments, sorted by Click to highlight new comments since: Today at 3:43 AM

I also saw a good intuitive example of the asymmetry once. If you've got a bimodal distribution and a monomodal distribution that lies at one of the peaks of the bimodal distribution, then the KL-divergence will be low when P is the monomodal distribution and Q is the bimodal distribution, while the KL-divergence will be high when P is the bimodal distribution and Q is the monomodal distribution.

Oh yeah, I really like this one, thanks! The intuition here is again that a monomodal distribution is a bad model for a bimodal one because it misses out on an entire class of events, but the other way around is much less bad because there's no large class of events that happen in reality but that your model fails to represent.

For people reading here, this post discusses this idea in more detail. The image to have in mind is this one:

Thanks for this post! Relatedly, Simon DeDeo had a thread on different ways the KL-divergence pops up in many fields:

Kullback-Leibler divergence has an enormous number of interpretations and uses: psychological, epistemic, thermodynamic, statistical, computational, geometrical... I am pretty sure I could teach an entire graduate seminar on it.

Psychological: an excellent predictor of where attention is directed.http://ilab.usc.edu/surprise/

Epistemic: a normative measure of where you ought to direct your experimental efforts (maximize expected model-breaking)http://www.jstor.org/stable/4623265

Thermodynamic: a measure of work you can extract from an out-of-equlibrium system as it relaxes to equilibrium.

Statistical: too many to count, but (e.g.) a measure of the failure of an approximation method.https://www.countbayesie.com/blog/2017/5/9/kullback-leibler-divergence-explained

Computational (machine learning): a measure of model inefficiency—the extent to which it retains useless information.https://arxiv.org/abs/1203.3271

Computational (compression): the extent to which a compression algorithm designed for one system fails when applied to another.

Geometrical: the (non-metric!) connection when one extends differential geometry to the probability simplex.

Biological: the extent to which subsystems co-compute.

Machine learning: the basic loss function for autoencoders, deep learning, etc. (people call it the "cross-entropy")

Algorithmic fairness. How to optimally constrain a prediction algorithm when ensuring compliance with laws on equitable treatment.https://arxiv.org/abs/1412.4643

Cultural evolution: a metric (we believe) for the study of individual exploration and innovation tasks...https://www.sciencedirect.com/science/article/pii/S0010027716302840…

Digital humanism: Kullback-Leibler divergence is related to TFIDF, but with much nicer properties when it comes to coarse-graining. (The most distinctive words have the highest partial-KL when teasing apart documents; stopwords have the lowest)http://www.mdpi.com/1099-4300/15/6/2246

Mutual information: Well, it's a special case of Kullback-Leibler—the extent to which you're surprised by (arbitrary) correlations between a pair of variables if you believe they're independent.

Statistics: it's the underlying justification for the Akiake Information Criterion, used for model selection.

Philosophy of mind: It’s the “free energy” term in the predictive brain account of perception and consciousness. See Andy Clark’s new book orhttps://link.springer.com/article/10.1007%2Fs11229-017-1534-5

The Radon-Nikodym theorem allows us to define the Kullback-Leibler divergence in a more general setting. Even though this setting is more abstract, in this abstract setting it is clear how the KL-divergence is a way to define relative entropy. The abstract setting limits our options to only the correct option.

Suppose that is the probability density function of a random variable supported on . Then we define the continuous entropy of as .

Suppose that we are given two probability measures on the Borel subsets of and we know that is the Lebesgue probability measure on . Then is there any way to abstractly define the continuous entropy of that only refers to the abstract measures without referring to or by recovering from the abstract properties of ? Yes there is. The Radon-Nikodym theorem allows us to recover from the measure theoretic properties of and it therefore allows us to recover the continuous entropy.

Suppose that is a -algebra. Let be two measures on . We say that is absolutely continuous with respect to if , and we write in this case. Recall that a measure is -finite if there are for each natural number such that for each and .

Theorem: (Radon-Nikodym theorem) Suppose that and are both -finite measures. Then there exists a positive measurable function where for each .

The function is called the Radon-Nikodym derivative of with respect to and is denoted by . The Radon-Nikodym derivative is unique up to a set of measure zero.

We therefore define the Kullback-Kiebler divergence as which coincides with the continuous entropy without the factor.

Now, the assumption that is isomorphic to the Lebesgue probability measure on is a surprisingly general assumption that works for many probability measures .

A Boolean algebra is said to be -complete if whenever for each natural number , the set has a least upper bound which we denote by .

A measure algebra is a pair where is a -complete Boolean algebra and is a function with iff and whenever for . If is a measure algebra, then define a metric (and hence a topology and uniformity and whatnot) on by setting . Recall that a topological space is separable if it has a countable dense subset.

For example, if is the collection of Lebesgue measurable subsets of , and is the collection of measure zero subsets of , then the quotient Boolean algebra is complete and if is the Lebesgue measure on , then is a separable atomless probability measure algebra, and this measure algebra is unique.

Theorem: (Caratheodory) Every separable atomless probability measure algebra is isomorphic.

We have an even stronger uniqueness theorem for this measure algebra.

Theorem: Every Borel probability measure on a complete separable metric space without any atoms is isomorphic to the Lebesgue measure on the interval .

Suppose now that are Borel probability measures on a complete separable metric space that possibly have atoms. Then there is some measure where is isomorphic to the Lebesgue probability measure. In this case, for almost all , so

. In this case, we can pretend that is the Lebesgue measure on and that just measures the continuous entropy of with respect to the Lebesgue probabilty measure on .

The KL-divergence also generalizes greatly. Given a function ( is usually convex or concave), one can define another measure of similarity between probability measures such as known as the -divergence. One can also define a measure on from the Radon-Nikodym derivative by where if and is a measure on , then is the measure on defined by . The random variable gives information about the similarity between the probability measures from which one can always recover the -divergence. In this case,.

Another intuition I often found useful: KL-divergence behaves more like the square of a metric than a metric.

The clearest indicator of this is that KL-divergence satisfies a kind of Pythagorean theorem established in a paper by Csiszár (1975), see https://www.jstor.org/stable/2959270#metadata_info_tab_contents . The intuition is exactly the same as for the euclidean case: If we project a point A onto a convex set S (say the projection is B), and if C is another point in the set S, then the standard Pythagorean theorem would tell us that the angle of the triangle ABC at B is larger than 90 degree, or in other words . And the same holds if we project with respect to KL divergence, and we end up having .

This has implications if you think about things like sample efficiency (instead of a square root rate as usual, convergence rates with KL divergence usually behave like 1/n).

This is also reflected in the relation between KL divergence and other distances for probability measures, like total variation or Wasserstein distance. The most prominent example would be Pinsker's inequality in this regard, stating that the total variation norm between two measures is bounded by a constant times the square root of the KL-divergence between the measures.

It would be nice to have a couple examples comparing concrete distributions Q and P and examining their KL-divergence, why it's large or small, and why it's not symmetric.

Rich, mostly succinct pedagogy of timeless essentials, highly recommended reference post.

The prose could be a little tighter and less self-conscious in some places. (Things like "I won't go through all of that in this post. There are several online resources that do a good job of explaining it" break the flow of mathematical awe and don't need to be said.)

Nice. I didn't know about the hypothesis testing one (or Bregman, but I don't get that one). I wonder if one can back out another description of KL divergence in terms of mutual information from the expression of mutual information in terms of KL divergence: https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence#Mutual_information

And yeah, despite a whole 16 lecture course on convex opti I still don't really get Bregman either, I skipped the exam questions on it 😆

Oh yeah, I hadn't considered that one. I think it's interesting, but the intuitions are better in the opposite direction, i.e. you can build on good intuitions for to better understand MI. I'm not sure if you can easily get intuitions to point in the other direction (i.e. from MI to ), because this particular expression has MI as an expectation over , rather than the other way around. E.g. I don't think this expression illuminates the nonsymmetry of .

The way it's written here seems more illuminating (not sure if that's the one that you meant). This gets across the idea that:

is the true reality, and is our (possibly incorrect) model which assumes independence. The mutual information between and equals , i.e. the extent to which modelling and as independent (sharing no information) is a poor way of modelling the true state of affairs (where they do share information).

But again I think this intuition works better in the other direction, since it builds on intuitions for to better explain MI. The arguments in the expression aren't arbitrary (i.e. we aren't working with ), which restricts the amount this can tell us about in general.

The arguments in the expression aren't arbitrary (i.e. we aren't working with ), which restricts the amount this can tell us about in general.

Yeah, I was vaguely hoping one could phrase $P$ and $Q$ so they're in that form, but I don't see it.

This is nitpicky but I believe the reasoning for **3 **is mistaken, mainly because of the counterintuitive claim that minimising cross-entropy over is equivalent to maximising KL divergence.

Writing the log-likelihood in the equation

we have the RHS tends to the **negative **cross entropy (by LLN), instead of just the cross entropy. Then, since with being the fixed (true) distribution and varying with , we have that MLE means we minimise the cross entropy which means we minimise the KL divergence.

By the law of large numbers, almost surely. This is the

cross entropyof and . Also note that if we subtract this from the entropy of , we get . So minimising the cross entropy over is equivalent to maximising .

I think the cross entropy of and is actually (note the negative sign). The entropy of is . Since then the KL divergence is actually the cross entropy minus the entropy, not the other way around. So minimising the cross entropy over will minimise (not maximise) the KL divergence.

I believe the next paragraph is still correct: the maximum likelihood estimator is the parameter which maximises , which minimises the cross-entropy, which minimises the KL divergence.

Apologies if any of what I've said above is incorrect, I'm not an expert on this.

This video breaks it down nicely along the lines of what you describe as the "common theme".

Nice! This is a significantly more developed intuition than the one I stumbled across (which is #1 for you I believe)

:)

KL-divergence is a topic which crops up in a ton of different places in information theory and machine learning, so it's important to understand well. Unfortunately, it has some properties which seem confusing at a first pass (e.g. it isn't symmetric like we would expect from most distance measures, and it can be unbounded as we take the limit of probabilities going to zero). There are lots of different ways you can develop good intuitions for it that I've come across in the past. This post is my attempt to collate all these intuitions, and try and identify the underlying commonalities between them. I hope that for everyone reading this, there will be at least one that you haven't come across before and that improves your overall understanding!

One other note - there is some overlap between each of these (some of them can be described as pretty much just rephrasings of others), so you might want to just browse the ones that look interesting to you. Also, I expect a large fraction of the value of this post (maybe >50%) comes from the summary, so you might just want to read that and skip the rest!

## Summary

1. Expected surprise

2. Hypothesis Testing

3. MLEs

4. Suboptimal coding

5A. Gambling games - beating the house

5B. Gambling games - gaming the lottery

6. Bregman divergence

Common theme for most of these:

## 1. Expected Surprise

For a random variable X with probability distribution P(X=x)=px, the

surprise(orsurprisal) is defined as IP(x)=−lnpx. This is motivated by some simple intuitive constraints we would like to have on any notion of "surprise":In fact, it's possible to show that these three considerations fix the definition of surprise up to a constant multiple.

From this, we have another way of defining

H(X)=−∑xpxlnpx=EP[IP(X)]entropy- as theexpected surprisalof an event:Now, suppose we (erroneously) believed the true distribution of X to be Q, rather than P. Then the expected surprise of our model (taking into account that the true distribution is P) is:

EP[IQ(X)]=−∑xpxlnqxand we now find that:

DKL(P||Q)=∑xpx(lnpx−lnqx)=EP[IQ(X)−IP(X)]In other words, KL-divergence is the difference between the expected surprise of your model, and the expected surprise of the correct model (i.e. the model where you know the true distribution P). The further apart Q is from P, the worse the model Q is for P, i.e. the more surprised it should expect to get by reality.

Furthermore, this explains why DKL(P||Q) isn't symmetric, e.g. why it blows up when px≫qx≈0 but not when qx≫px≈0. In the former case, your model is assigning very low probability to an event which might happen quite often, hence your model is very surprised by this. The latter case doesn't have this property, and there's no equivalent story you can tell about how your model is frequently very surprised.

^{[1]}## 2. Hypothesis Testing

Suppose you have two hypotheses: a

R={x:px/qx≤λ}null hypothesisH0 which says that X∼P, and analternative hypothesisH1 which says that X∼Q. Suppose the null is actually true. A natural hypothesis test is thelikelihood ratio test, i.e. you reject H0 if the observation X is in the critical region:for some constant λ which determines the size of the test. Another way of writing this is:

R={x:lnpx−lnqx≤μ}We can interpret the value lnpx−lnqx as (a scalar multiple of

^{[2]}) thebits evidence we get forH0overH1.In other words, if x happens twice as often under distribution P than distribution Q, then the observation X=x is a single bit of evidence for H0 over H1.DKL is (a scalar multiple of) the

expected bits of evidence we get forH0overH1, where the expectation is over the null hypothesis X∼P. The closer P and Q are, the more we should expect it to be hard to distinguish between them - i.e. when P is true, we shouldn't expect reality to provide much evidence for P rather than Q being true.## 3. MLEs

This one is a bit more maths-heavy than the others, so ymmv on how enlightening it is!

Suppose ^Pn is the empirical distribution of data x1,...,xN, which are each iid with distribution P, and Qθ is a statistical model parameterised by θ. Our likelihood function is:

L(^Pn;Qθ)=1NN∑i=1lnQθ(xi)By the law of large numbers, 1N∑Ni=1lnQθ(xi)→∑xP(x)lnQθ(x) almost surely. This is the

cross entropyof P and Qθ. Also note that if we subtract this from the entropy of P, we get DKL(P||Qθ). So minimising the cross entropy over θ is equivalent to maximising DKL(P||Qθ).Our maximum likelihood estimator θ∗ is the parameter which maximises L(^Pn;Qθ), and we can use some statistical learning theory plus a lot of handwaving to argue that θ∗→argminDKL(P||Qθ) (i.e. we've swapped around the limit and argmin operators). In other words,

maximum likelihood estimation is equivalent to minimising KL-divergence. If DKL(P||Q) is large, this suggests that Q will not be a good model for data generated from the distribution P.## 4. Suboptimal Coding

Source coding is a huge branch of information theory, and I won't go through all of that in this post. There are several online resources that do a good job of explaining it. To recap the key idea that will be important here:

From this, the intuition for KL divergence pops neatly out. Suppose you erroneously believed that X∼Q, and you designed an encoding that would be optimal in this case. The expected number of bits you'll have to send per message is:

−∑xpxlog2qxand we can immediately see that KL-divergence is (up to a scale factor) the difference in expected number of bits per event you'll have to send with this suboptimal code, vs the number you'd expect to send if you knew the true distribution and could construct the optimal code. The further apart P and Q are, the more bits you're wasting on average by not sending the optimal code. In particular, if we have a situation like px≫qx≈0, this means our code (which is optimised for Q) will assign a very long codeword to outcome x since we don't expect it to occur often, and so we'll be wasting a lot of message space by frequently having to use this codeword.

## 5A. Gambling Games - Beating the House

Suppose you can bet on the outcome of some casino game, e.g. a version of a roulette wheel with nonuniform probabilities. First, imagine the house is fair, and pays you 1/px times your original bet if you bet on outcome x (this way, any bet has zero expected value: because betting cx on outcome x means you expect to get px×cx/px=cx returned to you). Because the house knows exactly what all the probabilities are, there's no way for you to win money in expectation.

Now imagine the house actually doesn't know the true probabilities P, but you do. The house's mistaken belief is Q, and so they pay people 1/qx for event x even though this actually has probability px. Since you know more than them, you should be able to profit from this state of affairs. But how much can you make?

Suppose you have $1 to bet. You bet cx on outcome x, so ∑xcx=1. Let W be your expected winnings. It is more natural to talk about log winnings, because this describes how your wealth grows proportionally over time. Your expected log winnings are:

E[lnW]=∑xpx×ln(cx/qx)It turns out that, once you perform a simple bit of optimisation using the Lagrangian:

L(λ;B)=E[lnW]+λ(1−∑xcx)then you find the optimal betting strategy is cx=px (this is left as an exercise to the reader!). Your corresponding expected winnings are:

E[lnW]=∑xpx×ln(px/qx)=D(P||Q)in other words, the KL divergence represents the amount you can win from the casino by exploiting the difference between the true probabilities P and the house's false beliefs Q. The closer P and Q are, the harder it is to profit from your extra knowledge.

Once again, this framing illustrates the lack of symmetry in the KL-divergence. If px≫qx, this means the house will massively overpay you when event x happens, so the obvious strategy to exploit this is to bet a lot of money on x (and D(P||Q) will correspondingly be very large). If qx≫px, there is no corresponding way to exploit this (except to the extent that this suggests we might have py≫qy for some different outcome y).

## 5B. Gambling Games - Gaming the Lottery

This is basically the same as (5A), but it offers a slightly different perspective. Suppose a lottery exists for which people can buy tickets, and the total amount people spend on tickets is split evenly between everyone who bought a ticket with the winning number (realistically the lottery organisers would take some spread, but we assume this amount is very small). If every ticket is bought the same number of times, then there's no way to make money in expectation. But suppose people have a predictable bias (e.g. buying round numbers, or numbers with repeated digits) - then you might be able to make money in expectation by buying the less-frequently-bought tickets, because when you win you generally won't have as many people you'll have to split the pot with.

If you interpret Q as the distribution of people buying each ticket (which is known to you), and P is the true underlying distribution of which ticket pays out (also known), then this example collapses back into the previous one - you can use optimisation to find that the best way to purchase tickets is in proportion to P, and the KL-divergence is equal to your expected log winnings.

To take this framing further, let's consider situations where Q is not known to you on a per-number basis, but the overall distribution of group-sizes-per-ticket-number is known to you. For instance, in the limit of a large number of players and of numbers you can approximate the group size as a Poisson distribution. If each ticket has the same probability of paying out, then you can make DKL(U||Q) profit in expectation by buying one of every ticket (where U is the uniform distribution, and Q is the Poisson distribution). Interestingly, this strategy of "buying the pot" is theoretically possible for certain lotteries, for instance in the Canadian 6/49 Lotto (see a paper analysing this flaw here). However, there are a few reasons this tends not to work in real life, such as:

## 6. Bregman Divergence

Bregman divergence is pretty complicated in itself, and I don't expect this section to be illuminating to many people (it's still not fully illuminating to me!). However, I thought I'd still leave it in because it does offer an interesting perspective.

If you wanted to quantify how much two probability distributions diverge, the first thing you might think of is taking a standard norm (e.g. l2) of the difference between them. This has some nice properties, but it's also unsatisfactory for a bunch of reasons. For instance, it intuitively seems like the distance between the Bernoulli distributions with p=0.2 and p=0 should be larger than that between p=0.4 and p=0.6.

^{[4]}It turns out that there's a natural way to associate any

convex functionϕ with a measure of divergence. Since tangents to convex functions always lie below them, we can defineBregman divergenceDϕ(x||y) asthe amount by whichϕ(x)is greater than the estimate for it you would get by fitting a tangent line toϕatyand using it to linearly extrapolate tox.To do some quick sanity checks for Bregman divergence - if your convex function is the l2 norm squared, then the divergence measure you get is just the squared l2 norm of the vector between your points:

D||⋅||22(x||y)=||x||2−||y||2−2yT(x−y)=||x−y||2This is basically what you'd expect - it shows you that when the l2 norm is the natural way to measure how far away something is from zero (i.e. how large it is), then the l2 norm of the vector between two points is the natural way to measure how far one point is from another.

Now, lets go back to the case of probability distributions. Is there any convex function which measures, in some sense,

D−H(P∥Q)=−H(P)+H(Q)+⟨∇H(Q),P−Q⟩=∑xpxlnpx−qxlnqx−∂∂qx(qxlnqx)(px−qx)=∑xpxlnpx−qxlnqx−(1+lnqx)(px−qx)=∑xpx(lnpx−lnqx)=DKL(P∥Q)how far away a probability distribution is from zero?Well, one thing that seems natural is to say that "zero" is any probability distribution where the outcome is certain - in other words, zero entropy. And it turns out entropy is concave, so if we just take the negative of entropy then we get a convex function. Slap that into the formula for Bregman divergence and we get:There's no lightning-bolt moment of illumination from this framing. But it's still interesting, because it shows that different ways of measuring the divergence between two points can be more natural than others, depending on the space that we're working in, and what it represents. Euclidean distance between two points is natural in probability space, when zero is just another point in that space. But when working on the probability simplex, with entropy being our chosen way to measure a probability distribution's "difference from zero", we find that DKL is in some sense the most natural choice.

## Final Thoughts

Recapping these, we find that DKL(P||Q) being large indicates:

Although (4) might be the most mathematically elegant, I think (1) cuts closest to a true intuition for D.

To summarise what all of these framings have in common:

To put this last point another way, D(P||Q) "doesn't care" when qx≫px (assuming both probabilities are small), because even though our model is wrong, reality doesn't frequently show us situations in which our model fails to match reality. But if px≫qx then the outcome x will occur more frequently than we expect, consistently surprising our model and thereby demonstrating the model's inadequacy.

^{^}Note that the latter case might imply the former case, e.g. if 1≈qx≫px≈0 then we are actually also in the former case, since p¬x≫q¬x≈0. But this doesn't always happen; it is possible to have asymmetry here. For instance, if P = (0.1, 0.9) and Q = (0.01, 0.99), then we are in the former case but not the latter. If P is true, then 10% of the time model Q is extremely surprised, because an event happens that it ascribes probability 1% to - which is why DKL(P||Q) is very large. But if Q is true, reality presents model P with no surprises as large as this - hence DKL(Q||P) is not as large.

^{^}The scalar multiple part is because we're working with natural log, rather than base 2.

^{^}Specifically, the optimal decodable code - in other words, your set of codewords needs to have the property that you could string together any combination of them and it's possible to decipher which codewords you used. For instance,

`(0, 10, 11)`

has this property, but`(0, 10, 01)`

doesn't, because the string`010`

could have been produced from`0 + 10`

or`01 + 0`

.^{^}One way you could argue that a distance measure should have this property is to observe that the former two distributions have much lower variance than the latter two. So if you observe a distribution which is either p=0 or p=0.2, you should expect it to take much less time to tell which of the two distributions you're looking at than if you were trying to distinguish between p=0.4 and p=0.6.