Six (and a half) intuitions for KL divergence

Link to LessWrong post here.

Six (and a half) intuitions for KL divergence

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

how much more surprised you expect to be when observing data with distribution , if you falsely believe the distribution is vs if you know the true distribution

2. Hypothesis Testing

the amount of evidence we expect to get for over in hypothesis testing, if is true.

3. MLEs

If is an empirical distribution of data, is minimised (over ) when is the maximum likelihood estimator for .

4. Suboptimal coding

the number of bits we're wasting, if we try and compress a data source with distribution using a code which is actually optimised for (i.e. a code which would have minimum expected message length if were the true data source distribution).

5A. Gambling games - beating the house

the amount (in log-space) we can win from a casino game, if we know the true game distribution is but the house incorrectly believes it to be .

5B. Gambling games - gaming the lottery

the amount (in log-space) we can win from a lottery if we know the winning ticket probabilities and the distribution of ticket purchases .

6. Bregman divergence

is in some sense a natural way of measuring of how far is from if we are using the entropy of a distribution to capture how far away it is from zero (analogous to how is a natural measure of the distance between vectors a