A Universe of Sorts

This began life as me explaining entropy and KL divergence to friends on a group chat. All my logs are base 2.

§ Surprise

We wish to measure how "surprising" something is. We will measure this as $Surprise(q) = -\log(q)$ where $q$ is the probability of an event. This way, if an event is deterministic ( $q=1$ ) then its surprise is 0. If an event is impossible ( $q=0$ ), then its surprise is infinite. So the surprise of an event whose probability is $2^{-n}$ is going to be $n$ .

§ Entropy is expected surprise

The entropy of a random variable is the expected surprise we are going to get from it:

Entropy(X) = \sum_{x \in X} Surprise(p(x)) \cdot p(x)

For example, given a binary random variable which takes on heads with probability $q$ and tails with probability $(1 - q)$ , the entropy is going to be $-q\log(q) - (1-q)\log(1-q)$ . We can check that this is maximum when $q = 0.5$ . This ought to be intuitive, because when $q = 0.5$ , we can't predict anything about the coin toss. If it were slightly higher, then we could guess that it's more likely to be heads, so we "know more" about it.

Note that to define the entropy, all we needed was $p: X \rightarrow [0, 1]$ . So really, entropy is a property of a probability distribution. And if we think about it a little carefully (ie, stare at the equation and fiddle with it), we come to the intuition that entropy is high when $p(x)$ is spread out. One can show that the uniform distribution $p(x) = 1/|X|$ is the unique distribution that has the highest entropy over a set $X$ . The intuition is the same as the coin's: if the distribution is uniform, you can't really guess.

§ Entropy is bits you have to pay

OK, now we move to the coding theory perspective on all this, which is the one true way (and is, BTW, also the right way to understand KL divergence IMO). We have a sender who is sending elements $S = x_1, x_2, \dots, x_n$ , with each $x$ drawn IID from $X$ with distribution $p$ . Now, how many bits do we need to encode $S$ ?

We can design clever schemes and stupid schemes. Coding theory proves that on average, the best encoding scheme will need $Entropy(p)$ bits to encode each $x_i$ . It might spend more bits on some $x_0$ and fewer bits on some $x_{100}$ , but on average we will need $Entropy(p)$ bits, if the data $S$ is generated using the distribution $p$ . For an actual example of this, see Huffman coding : it achieves optimal encoding, choosing a different number of bits for different elements of $X$ , and it doesn't clash because it's prefix-free and blah.

Some questions, for intuition about this entropy-as-encoding-cost:

Q1: we have a coin that is biased such that it only outputs heads, and we're going to be sending the results of the coin flips. How many bits do we need? A1: zero, because we don't need to transmit anything: the receiver already knows what's going to be sent, since the sequence must be [heads, heads, heads, ... ]. There's no point in transmitting it. (This is actually somewhat of a failing of entropy: it only considers the unknown to be information. If you have some complex, deterministic thing, it's not information in this perspective. Other perspectives, such as descriptive complexity , remedy this.)
Q2: a coin that takes heads and tails in equal likelihood? A2: we are forced to use 1 bit, since $-\log_2(0.5) = 1$ . This is from Shannon's source coding theorem .
Q3: what is the "good" encoding of a coin where heads occurs with probability 0.9 and tails with 0.1? Entropy tells us that we ought to manage with $-0.9\log(0.9) - 0.1\log(0.1) \approx 0.47$ bits per flip. A3: batch flips together and encode runs.

§ KL divergence is extra bits you pay

KL divergence is a divergence (not a distance!) between two probability distributions $p, q: X \rightarrow [0, 1]$ , which tells us how many extra bits we pay on average if the data came from distribution $p$ , but we encoded it as if it came from distribution $q$ . That is:

I was given $S = x_1, \dots, x_n$ , sampled from $p$ .
$S$ is handed to an encoder $Enc_q$ which assumes the data was sampled from $q$ (notice, $q$ not $p$ ).
$Enc_q(S)$ uses more bits than $Enc_p(S)$ would, since it has inefficiencies. How much more? That's the KL divergence between $p$ and $q$ :

\begin{aligned} D_{KL}(P \| Q) &= \sum_{x \in X} (Surprise(q(x)) - Surprise(p(x))) \cdot p(x) \\ &= \sum_{x \in X} p(x) \cdot [\log(p(x)) - \log(q(x))] \end{aligned}

You can look at it from an adversarial perspective:

[data ~ p(x)] --> [encoder ~ p(x)] (optimal)     [baseline][data ~ p(x)] --> [encoder ~ q(x)] (adversarial) [how bad are you?]

§ The fair coin and the heads coin

We go back to the humble unfair coin, for we are gamblers. Assume we have two coins. One is fair, governed by a distribution $F: \{heads, tails\} \rightarrow [0,1]$ with $F(heads) = F(tails) = 0.5$ ( $F$ for fair). The other only tosses heads: $H(heads) = 1$ , $H(tails) = 0$ .

Before computing, let's talk intuitions. How do we encode the fair coin? We encode heads as 0 and tails as 1. How do we encode the heads coin? Well, coding theory says "don't". There's nothing to send, so don't bother sending information.

If I have the encoder $Enc_F$ and I hand it the sequence HHH generated from the heads coin, it'll spend 3 bits, encoding it as 000. $Enc_H$ will do fine (and not send anything), because it assumes anything it has to send is of the form HHHHH... So $Enc_F$ paid extra bits, assuming the underlying distribution was $H$ : $D_{KL}(H \| F)$ is finite (it's 1 bit per flip).
If I have the encoder $Enc_H$ and I hand it the sequence HTH generated from the fair coin, it's out of luck. How the fuck is it supposed to send T? It needs to spend infinitely more bits than $Enc_F$ to do anything: $D_{KL}(F \| H) = \infty$ .

So, well, clearly, this is not a symmetric concept. If there are things you literally cannot encode, you spend an infinite number of bits trying to encode them. If there are things you can encode but are bad at, you spend more bits trying. But you'll always spend more bits, on average.

This example is also how I remember the formula:

It has to be $D_{KL}(P\|Q) = \sum_{x \in X} p(x) \cdot \langle ??? \rangle$ , since we're riffing off of entropy.
It is either $\log(p(x)/q(x))$ or $\log(q(x)/p(x))$ .
It has to be $p(x)/q(x)$ , since if $q(x) = 0$ (ie, $q$ cannot represent something), it is infinitely far away from $p$ : $\log(p(x)/0) = \log(\infty) = \infty$ . Aka "out of band stuff costs infinite bits".
And it has to be $p(x)/q(x)$ because if $p(x) = 0$ (ie, the source never gives you this data), I don't care whether we can encode it or not, following the convention that $0 \log 0 = 0$ .

A friend ( Aditya Bharti ) offered a far less roundabout mnemonic: the expected bits to encode $X \sim p$ is $\sum_x p(x)(-\log p(x))$ , where the first $p$ is there because it's an expectation, and the second is there because the encoder uses the distribution to calculate the number of bits. If the encoder makes the wrong assumption (data from $p$ , encoder assuming $q$ ), the expectation stays $p$ but the encoder's term becomes $-\log q(x)$ . Subtract the honest cost from the wrong-assumption cost, and the formula falls out. I'm a little iffy with this one because you can write distributions where $\log p(x) - \log q(x)$ goes negative for some $x_0$ while the overall sum remains positive, which is why I refrain from the pointwise perspective. But it's a useful mnemonic.

§ KL divergence is non-negative: the Bregman divergence

We have not yet proved that KL divergence is always non-negative. So let's do that next. I'm going to define a weird geometric distance that's only valid for convex functions, into which when we plug in our surprisal, life is going to be dandy, and we regenerate the KL divergence. This gadget is called as the "Bregman divergence".

So, let us begin with the humble equation $d(x, y) = \lVert x-y \rVert^2 = \langle x - y | x - y \rangle$ , where I use $\langle a | b \rangle$ for the dot product (yay quantum notation). Now, we can algebraically manipulate it:

\begin{aligned} d(x, y) &= \langle x - y | x - y \rangle \\ &= \langle x|x \rangle + \langle y|y \rangle - 2\langle x|y \rangle \quad \text{(linearity)}\\ &= \langle x|x \rangle - \langle y|y \rangle - 2\langle y|x - y \rangle \quad \text{(add and subtract $2\langle y|y\rangle$)}\\ &= lensq(x) - lensq(y) - \langle lensq'(y)|x-y \rangle \end{aligned}

where $lensq(v) = \langle v|v \rangle$ , so $lensq'(y) = 2y$ . We can interpret the last line as

lensq(x) - [lensq(y) + \langle lensq'(y)|x-y \rangle]

and $lensq(y) + \langle lensq'(y)|x-y \rangle$ is the equation of a point on a line: start at $y$ , with slope $lensq'(y)$ , and move for a distance of $(x - y)$ . So the distance we are measuring is the gap between the value of the function at $x$ and the tangent drawn at $y$ , followed out to $x$ . Draw the parabola and a tangent line: for a convex function this gap is clearly always positive (for a formal proof, please, the convexity of $f$ ).

Now, we can choose to generalize this to any convex function $f$ , and it will give us an analogous "distance". Note that the same argument holds in $\mathbb R^n$ ; we used nothing special about $\mathbb R$ here. So define the divergence

D_f(x, y) = f(x) - [f(y) + \langle f'(y)|x-y \rangle] \geq 0.

Now plug in the convex function $f((p_1, \dots, p_n)) = \sum_i p_i \log p_i$ , whose derivative is $(\partial f/\partial p_i)(y) = 1 + \log y_i$ . On simplification (for $x, y$ probability vectors, the $\sum_i x_i - \sum_i y_i$ terms are zero since both sum to one):

D_f(x, y) = \sum_i x_i (\log x_i - \log y_i) = D_{KL}(x \| y) \geq 0.

Hence, KL divergence is the Bregman divergence of $F(x) = \sum_i x_i \log x_i$ , and is non-negative. Here is a great visualization link: Meet the Bregman divergences . Anyway, that's my preferred proof for KL divergence being non-negative.

§ Conclusion

Why $\log$ for surprise, and not some other function that is 0 when $p = 1$ (which other functions satisfy as well)? If you add the condition that $Entropy(XY) = Entropy(X) + Entropy(Y)$ for independent $X, Y$ , along with some other intuitive conditions, entropy is uniquely characterised .

I'm still somewhat dis-satisfied with my KL divergence explanation. I'll do the Fisher information based motivation someday.