There's a kind of wild paper from 2002 called *Language Trees and Zipping*, which shows how you can find structure between languages just by using very general file compression. For example, let's say I give you a bunch of text documents in many different languages, and your goal is to automatically cluster them by language. And actually, you can aim even higher than that. Suppose you also want to recover which languages are most closely related to each other in a way that lets you rediscover the tree of shared lineage between them, and all you can do is write a function that processes the text in each one. There's no pre-baked knowledge of linguistics.

Now keep in mind, this is almost a quarter century ago, so nothing like modern language models is available. What's crazy is how the authors showed that you can do this just by using gzip, basically the same operation that you might use on your computer to make files a bit smaller.

Here's the basic idea: given two documents, $A$ and $B$, append a small snippet of $B$ to the end of $A$, and compress the result. Now compare that file size to what you get just by compressing $A$ on its own. One way to think about this difference is it's telling you how well a little snippet of $B$ gets compressed when the compressor is mostly optimized for $A$. You'd expect that result to be small when the linguistic patterns of $B$ are similar to those in $A$, but larger when $B$ is more different from $A$.

The authors used this general idea to define a specific metric for how far away two documents are, based exclusively on how well they compress together. And then, evidently, this co-compression-based distance was enough to recover the tree of language lineage. And it doesn't stop there—the same trick can be used for other natural language tasks, like identifying who authored a given document.

What I like about this paper is what a pure example it is of when the theory and the engineering behind compression can be surprisingly useful to tasks which would seem to fall in the domain of machine learning and artificial intelligence. The specific concept underlying this example is something known as cross-entropy. And what's interesting is that cross-entropy is also a very core part of how modern language models are trained, which gives a whisper of an unexpected connection between that training and compression.

Most of what I want to do with this video is provide a lesson that goes back to the basics. We're going to spend the first half on the fundamentals of what cross-entropy is, how it naturally arises in the study of compression, and how you can visualize it. Then after that, we're going to go through the fundamentals on pre-training and distilling language models.

And what's interesting is how, in that second half, the way that cross-entropy arises initially looks completely different. It seems unrelated to compression. But whenever you see the same formula pop up in two separate contexts, it's math's way of kind of winking at you and hinting at a connection. So at the end, armed with an understanding of where cross-entropy really comes from, combined with an understanding of pre-training, I want to show you how you can reframe the way you think about training large language models to not be about next-token prediction, but instead to be about compression.

It's easiest to motivate cross-entropy in the context of encoding messages into sequences of bits. This is a topic we began discussing in part one, where the framing is that we treat messages as sequences of symbols, something like characters of text. If you treat each new symbol like it's being sampled from some probability distribution, those probabilities tell you something about the fundamental limits on compression.

Now, the case of natural language is incredibly complicated; those distributions would be very difficult to describe, so we centered a lot of our discussion on a very simplified toy example. And I want to pick up from that thread here, since that example also helps motivate cross-entropy.

The setup was that we're sending sequences of four possible instructions to some faraway robot: move up, down, left, or right. Each symbol we send is sampled from a distribution that gives a 50% chance to sending the instruction "up", a 1-in-4 chance of sending "down", and a 1-in-8 chance for each of the remaining symbols, "left" and "right". It's as if we want the robot to do some specific biased random walk.

One of the conclusions we came to in part one was how the best possible encoding here turns the symbol "up" into just a single bit, turns that symbol "down" into two bits, and turns "left" and "right" each into three bits. The whole point of this toy example is that it's a concrete illustration of a much more general fact, which is that for an optimal code, the number of bits that you allocate to a given symbol looks like the negative log base 2 of the probability for that symbol showing up: $-\log_2(p)$.

This negative log expression takes a little getting used to. I mentioned how I kind of wish that history had unfolded in such a way that we call it the log base $1/2$ of the probability, since it's really just asking: how many times do you chop things in half to get down to a certain amount? Claude Shannon defined this expression to be the information content of an event.

Now, of course, usually the numbers aren't so clean, so this information value is typically not a whole number, meaning your optimal codes can't look so simple as associating a symbol with some specific string of bits. The more general way to think about it is that to encode a full message, the information content of the full message looks like the sum of the information contents of all the individual symbols, and the number of bits in an optimal encoding of the message is approximately that full information content. So fractional information really does have a very real meaning here.

Now for part two, imagine your space agency has decided to change the plan, effectively rotating things to encourage an overall more rightward journey, where from now on the symbols "up" and "down" each have a 1-in-8 chance, the symbol "left" has a 1-in-4 chance, and "right" is sampled fully half of the time. Supposing all of your encoding and decoding systems are hard-coded to use the previous encoding scheme, optimized for the old distribution, this is obviously now inefficient—but how inefficient exactly?

And this is not that hard to calculate. Now the single-bit instruction for "up" comes up only one-eighth of the time, the two bits for "down" also come up only one-eighth of the time, and the other two instructions each require three bits, which together happens 75% of the time. Adding this up as a weighted sum, you get an average of 2.625 bits per message. You would say that this number represents the cross-entropy of the original distribution relative to the new one. If you've optimized a compression scheme around one context, how does it perform in another context?

Even just as I've stated things so far, perhaps this already rings a few bells in your mind as you think back to that zipping and language tree example. Before spelling that out, it is worth our time to take a few minutes generalizing this and packaging it into a couple formulas. Let's label all the probabilities from our new distribution with the letter $P$, and then all of those from the original distribution with the letter $Q$. And instead of limiting ourselves to four robot instructions, let's consider the general case of messages that look like any sequence of symbols. Those symbols could be the four robot instructions, they could be the characters of English text, or they could be anything else you dream up.

An encoding optimized for this first distribution, $Q$, allocates $-\log_2(q_i)$ bits to each symbol. So the average bits used per instruction looks like this weighted sum. Basically, you go through each symbol, and for each one you take the proportion of times that it comes up, which is its probability, multiplied by the information content, the negative log base 2 of its probability: $$\sum_i q_i (-\log_2(q_i))$$ This sum was the other key term we had in the last lesson, the entropy of $Q$, and we visualized it as the area of this diagram. Each bar represents one part of the weighted sum; its width is $q_i$, and its height is $-\log_2(q_i)$.

But if the distribution that arises in practice is something else, $P$, and we keep using an encoding optimized for $Q$, then the average number of bits used per instruction would still look like a weighted sum, but now the weights are these new probabilities, $P$: $$\sum_i p_i (-\log_2(q_i))$$ So this general expression is, by definition, the cross-entropy of the distribution $Q$ relative to the distribution $P$. The specific notation that you'll see out in the wild is a little bit of a mess—there's a lot of different conventions. For you and me, we'll just think about the sum itself, visualized with this diagram where the width of each bar is $p_i$, while the height is $-\log_2(q_i)$.

With any new formula, it helps to build some intuition with very simple examples. So in this case, instead of having distributions with many possible events, consider a distribution with only two events. And let's say $Q$ is an even distribution that assigns a 50% chance to each event, while $P$ is more skewed, assigning 90% to one and 10% to the other.

This would mean, from $Q$'s perspective, each event has one bit of information, and an optimal code for symbols following this distribution would spend only one bit on each such symbol, so the total entropy of $Q$ is one bit. And what about cross-entropy? If this code was used when a new distribution of symbols applies, what would the average number of bits per symbol be in that case? Well, in this example, actually, because each symbol has the same amount of information (one bit), the weights in the weighted sum don't actually make any difference, so cross-entropy is also one bit.

But now think about flipping this around. Suppose that $Q$ was the very skewed distribution with the 90-10 split, while $P$ was an even distribution with the 50-50 split. Now, from $Q$'s perspective, that one much more likely event has very little information, and the other one has a lot of information. So as far as $Q$ is concerned, a perfect code for symbols following this distribution should spend much less than one bit, again averaged over all messages, for that one common symbol, trading off spending multiple bits on average for that second symbol.

When you calculate it, the total entropy of $Q$ is now smaller than one bit. But now what about cross-entropy? If a code optimized for this skewed distribution was faced against a new reality where both events are equally likely, now you really do see a disadvantage, and that weighted sum is around 1.74 bits. So stepping back, notice how much order matters here. When we swapped the roles of $P$ and $Q$, the value of this cross-entropy changed, which makes sense: in the formula, the roles of $P$ and $Q$ are pretty different.

While we're here, by the way, just showing simple distributions over only two possible outcomes, we can have some more fun. Notice how this distribution $Q$ depends on only one free variable, $q_1$, and the complementary value has to be locked at $1 - q_1$. And same deal for $P$—it really depends on just one parameter, $p_1$. The reason we can have some fun is that with so few free parameters, we can build more intuition by graphing things, which lets me highlight one critical property here.

I want you to imagine fixing $P$ in place and then plotting this cross-entropy expression as a function of $Q$. What you'll notice is this graph reaches a very clear minimum, and more specifically, the value where it achieves that minimum is the one where $P$ and $Q$ are identical. And hopefully, based on how we motivated it, this should make abundant sense. Always remember that question cross-entropy is asking: how well does a code optimized for one setting, $Q$, perform in a different setting, $P$? That compression efficiency will obviously be at its best when both settings align.

There's something very fun we can do with this plot that helps to highlight a key point. What I'm going to do is move around that value $P$, which changes the entire shape of the graph, and as I do, you'll notice I'm tracing out where that minimum value of the graph goes. That traced-out shape is a new curve that I'm drawing in green, and let me take a moment to ask you: what does this new curve represent?

Well, that minimum value for cross-entropy is the most efficient possible compression when reality follows the distribution $P$, and that's exactly what the entropy of $P$ is supposed to represent. And indeed, in this very simplified setting where we're dealing with a distribution over only two possible outcomes, this green curve is what the entropy of $P$ would look like as a function of $p_1$.

This graph emphasizes the one key point about cross-entropy that I want you to remember from this video, which is that if you think of $P$ as fixed and $Q$ as the variable, it takes on its smallest possible value when $Q$ is equal to $P$, and more specifically, that smallest value is the entropy of $P$.

It's a little harder to visualize in general, because usually these are distributions over many more than just two possible outcomes, but here's one way that you might hold that same fact in your head. We'll take that core diagram that we built up; I'm going to keep $P$, the width of all the bars, fixed, and the distribution $Q$ is going to be variable. Remember, $Q$ is what determines the height of all of these bars, those negative log base 2 values. And again, that key fact is that this value is bounded by a certain minimum, that it achieves that minimum when $Q$ is equal to $P$, and that the minimal value is the entropy of $P$.

Before explaining why this key property makes cross-entropy such a good fit for training large language models, I want you to take a moment to think about how that opening example of zipping and language trees is basically an application of cross-entropy. Remember what the key idea there was: where if you want to measure how different two different text documents are (we'll call them $A$ and $B$), you take a little snippet of $B$, tack it onto $A$, and then compress the result. You then compare the size of that compressed file to the size of what you get just compressing $A$ on its own.

Again, because the zipping in that first context is mostly optimized for the patterns of document $A$, computing this difference is basically asking the same question cross-entropy does: how well does a compression scheme optimized for one context perform when faced with another context? I am glossing over a couple details where the specific distance metric that the authors defined was a little more complicated than this, but the core of it really is this difference that I've been showing.

Now, this is not exactly cross-entropy for a number of reasons. One, it's not comparing two different probability distributions. Instead, it's kind of like treating a text document from one language as a sample from some distribution, and hence this difference is kind of like an empirical estimate of cross-entropy. And even then, it can't be a very good estimate because gzip is not perfect compression achieving the Shannon limit—very far from it. The algorithm underlying it is a much more straightforward way to find repetitions of a given text sequence and replace later instances with pointers to earlier instances. But the authors' idea was that, insofar as this approximates cross-entropy, you can still get a useful distance measure, letting you do a legitimately interesting natural language processing task.

This is a common theme for how cross-entropy gets used in practice. It comes up whenever you have a feeling of wanting to quantify how different the patterns in one setting are from those in another. Here, that means the patterns of one language compared to that of another, but this transitions nicely to our primary application for today, which is training language models. Here, what you want to quantify is how different a model's understanding of language is from the true patterns of language, at least as represented by a bunch of training data.

This animation I've been flashing, by the way, shows the underlying architecture of a transformer. It's something a friend of mine made. But moving forward, I'm going to switch to something a little bit more schematic, simply representing a black box controlled by some large number of tunable parameters.

I'm assuming most viewers will have some familiarity with language models and neural networks; these are topics that we have hit on on the channel before. But here's a very quick recap of the basics for what you need to know. Modern language models divide text into tokens, which are typically words or pieces of words. And you think of a language model as a function—a function that takes as an input any possible piece of text, thought of as a sequence of tokens, and it produces as an output a probability distribution over all possible tokens. And you think of that output as its prediction for what might come next.

To train one of these models, what you need is a loss function, a way to quantify whether the predictions that it makes are generally good or generally bad. A loose intuition you might imagine is the graph of a loss function as something like this—some surface where you're hunting for the minimum. But you have to take any image like this with a heavy grain of salt, because this is a graph of a function with two inputs, the variables $x$ and $y$, whereas a true loss function takes as its input the many billions of parameters characterizing the language model. So the real image we want to look at here would have to live in billions of dimensions.

Still, it's enough to reference the core idea, which is how training looks like tweaking and tuning these models in a somewhat automatic way to take steps down this hill, decreasing the value of that loss. The automatic process for this tweaking and tuning comes down to gradient descent and backpropagation. I have done videos on these if you want the details, but the point I want to emphasize is that for you, the engineer trying to train a model, once you define a good loss function, you're essentially done. The standard machinery of deep learning takes it from there.

The loss you define is with respect to some big pile of training data, which in the language model context would look like many, many samples of text typically drawn from the Internet. So the key design question for you is: what mathematical function can you write down describing how well the model performs on all of this data, such that the act of minimizing that function is the same thing as improving model performance?

A very nice way to think about the loss function we use in this case is that you measure the average information per token from the model's perspective. Here's what I mean by that. For a given example snippet of text in that data, you would compute the probability that the model gives to each new token in there. That is, for every initial subsequence of tokens, like this one, you have the model predict what would come next, and then you look at the true next token, the one that actually showed up in this training example, and you consider: what probability did the model give to that one, that true next token?

That probability is what I'm representing with the little pie charts below each one of these tokens. The models are actually specifically designed to give you all of these probabilities on a single pass. When I say the loss is the average information from the model's perspective, what I mean is we take the negative log of all these probabilities: $-\log(P(\text{token}))$.

As we've discussed multiple times by now, you can think of that as measuring how surprising an event is. You would expect a smarter model that's really following what's going on to generally be unsurprised by what it sees, meaning it gives the true next tokens higher probabilities, so all these information values would be lower, while a randomized or poorly trained model would just be very confused. It would give everything a low probability and be surprised all the time.

Pulling up that graph of the negative log that we were playing with last time, this is hopefully very intuitive as a choice for the loss function. It's effectively telling you the model is punished, and punished very steeply, if it assigns a very low probability to the true next token, whereas if that probability is high, that prediction would contribute only a tiny amount to the total loss.

But the thing is, a lot of functions have this same general qualitative shape, so a question that I want to be hanging in your mind right now is why information specifically would be the best choice here. What is it that makes logs special among all the functions with this shape?

One small nuance is that in machine learning, you almost always use the natural log instead of a log base 2. This doesn't really matter—the two expressions differ by a constant factor, so it's all getting absorbed in something called the learning rate anyway. The motive is just that natural logs are a lot cleaner whenever you're taking derivatives, and derivatives are the core part of the gradient descent algorithm used to concretely decrease the value of this loss function.

And in some sense, that's it. That's really all there is to pre-training. All you're doing is looking through each token, taking the negative log of the probability the model gives to it, and averaging that over every token you see. And of course, it's not every token in just one example; it's every token in the entirety of the vast, vast training set, which you hope represents a significant sample of the language you're trying to model.

Of course, there really is more to it. I've glossed over things like batching or specific optimizers, and getting this to run at the mind-boggling scales used in practice is a complete engineering feat. But at the level of abstraction of just thinking of loss functions, it really is remarkably simple. It really is just the average information per token, assuming all the machinery of deep learning can do its job to minimize this loss, hopefully getting it to approach something like the entropy of language; what you'd be left with would be a powerful general predictor.

You might think this loss function would go by a name like "information loss" or "log loss", but in fact, people call it cross-entropy loss, which at first might sound really strange, given that nowhere in the explanation have we actually used the cross-entropy formula.

Now there is one very unsatisfying way that this is commonly described, where you say: we are calculating cross-entropy, but it's between the model's output on a given token and a fully skewed distribution with all the probability mass concentrated on just the one true next token. If you pull up the formula we had earlier, where we're taking a weighted sum using all these quantities on the right as weights, all of the zeros cancel most of the things out, and all you're left with is the negative log of the probability the model gives to the true next token.

But if that's all there was to it, this would be very lame, at least in my opinion. This does nothing to explain why you're using cross-entropy in the first place, and if it all just evaporates away anyway, why not just be straightforward? Why not just call it log loss or information loss? Let me show you what I find more satisfying, which is to start by explaining why the choice of logarithms here is not really a choice at all. Your hand is almost forced into it, and when you see how, the formula for cross-entropy just naturally pops right out in front of you.

So far we've only focused on one example at a time—one specific token prediction from one snippet of text—and in our framing, we want to turn the probability that the model gives to that token into some kind of loss, some value telling the model how bad it should feel and how aggressively it should correct itself. Now at first, it looks like the only real constraint is that this should be a decreasing function: you want to assign high loss to low probabilities, and low loss to probabilities closer to 1. So given the infinite abundance of functions with this rough shape, what makes one of them better than the others?

Let's say we don't know right now, so whatever choice we make, we're going to label it as $f$, and see if we can find some other property that we want $f$ to have, something that might force our hand. And for this, imagine an example like: `"My name is _____."` This is a small enough and common enough pattern that you would be likely to see many different instances of it show up in your pre-training data. What you might imagine is very common names show up multiple times in the data, while rare names show up less frequently.

When you feed in these tokens, `"My name is"`, into the model, it produces some distribution over all possible next tokens, and so let's label the probabilities in the model's distribution of outputs with the letter $Q$. Now let me ask you: what is the total loss associated with this prediction? If you were just focused on one instance where this pattern shows up in the training data, that loss looks like $f(q)$ for whatever your choice of the function $f$ is, whether that's a negative log or something else.

But the key is that this is only one part of the total loss associated with the example. Every other instance of this name also contributes that same amount, and each instance of every other name also contributes an analogous amount, except where you input the probabilities that the model gives to those other names. Here, I'll use the letter $P$ to represent the proportion of times that a given name shows up in the training data. The average value for the loss of the model's output over all of the examples that have this pattern looks like a weighted average, weighted by these values $p_i$: $$\sum_i p_i f(q_i)$$

From here, maybe you can start to anticipate the role of cross-entropy. If you choose to make this function $f$ the negative log of $q_i$, then this full expression for the total average loss associated with the input text really is exactly the definition of cross-entropy. Specifically, it's the cross-entropy of our model's output relative to the statistics represented within the data.

And remember the one key property of this formula I want you to remember: it's something that takes on a minimum exactly when all these $p$ and $q$ values are equal to each other. So in this setting, that would mean it's minimized exactly when the distribution your model outputs is the same as the statistical distribution represented in your data.

But the real key point is that this implication goes the other way around. If we switch back to writing this per-example loss with some generic function $f$, and you say you would like it to be the case that the full average loss over all of the examples is minimized only when the model's output matches the statistics that show up in the data, there's actually a really nice mathematical argument for why $f$ has to be a logarithm.

I'm hesitant to derail us too much by delving into the details, which involves something called a Lagrange multiplier, since there's a risk of losing the forest for the trees. I know many of you are curious, so I will pull up the details on the screen for any multivariable calculus enthusiasts interested in pausing and pondering.

The high-level idea really is very pretty: it's that to minimize our key expression, subject to the condition that the sum of all the $q$ values is equal to 1, you end up with a problem that looks like finding values where two different contours are tangent to each other. You compute where that happens by setting a pair of gradient values equal to each other, and this, for our specific expressions, will boil down to the condition that the derivative of our function $f$ with respect to $q$ has to look like some constant over $q$ ($f'(q) = -c/q$), and only logarithms have that property.

Again, I pull this up just for the extra curious; the details are not too important. The main thing I want you to know is that if you want a loss function with the property that it's minimized only when the model matches the statistics of the data, your hand is forced: you actually have to use the negative log. And in this case, the average loss associated with any given input text looks exactly like the cross-entropy formula. And while I'm here throwing up notes for the extra curious, here's another one about overfitting and how magical it is that this actually works when you stop and think about the sparsity of the data that we have.

The last topic I want to hit on in this section is an interesting variant on training language models where this cross-entropy formula is used more explicitly. And it's a case where each training example gives a much softer tug on the model's distributions, one that is not so over-weighted to one specific next token. It's something called distillation.

The setup here is that you might want to train a relatively small model where its goal is to approximate the performance of some larger, presumably much smarter model. This comes up all the time, because very often after getting some desired performance by scaling up all of your parameters, what you would love is to be able to approximate that performance with something much smaller and much more efficient to run at inference time. The idea is that with a bigger model in hand, you have the ability to do something much, much more efficient than normal pre-training with that small model.

What you do is look through a bunch of data, and as before, at each new token, you consider the small model's prediction of what will follow—that full distribution. But now, instead of just comparing it to the true next token in the data, you compare it to the larger model's prediction, its full distribution across all the tokens at that same point. You define the loss at this token to be the cross-entropy of the small model's distribution relative to the big model's.

When you think about it, this gives you something much, much richer than ordinary pre-training, since pre-training is just giving full weight to only one true next token, the one that happens to be there. As an analogy, it's the difference between trying to learn chess just by watching a game versus having someone better than you talk through all the possible good moves and how heavily they would weight them at each new turn. Looking back at that `"My name is _____"` example, instead of having to see many thousands or many millions of examples in the data before your loss represents the cross-entropy against a reasonable distribution of possible names, you can get that same effect just on a single example, comparing it against the good model's prediction.

I think now is a good time to zoom out and look over everything we've built up. In the first half, in the context of compression, cross-entropy arose very naturally just by asking how well a compression scheme optimized for one setting performs in another. The mild surprise is that this idea turns out to be much more generally useful, as a way to measure how different patterns in one setting are from those in another. This is what makes it such a common tool for loss functions in modern machine learning.

All that said, as stated so far, the way that the formula showed up in the second half, for us, feels pretty different from the way that it showed up in the first half. It was essentially unrelated to compression. The logic actually came from a completely different part of math: constrained optimization. But I wouldn't be putting these two topics in the same video if they didn't have a tighter connection than that.

In the same way that whenever you see $\pi$ show up in math, even when it seems unrelated to circles, there's always going to be some connection to circles hiding there, I think whenever you see cross-entropy pop up, there will be a way to connect it to compression. And in the case of language models, we've already teed things up for how to make that connection a little bit more tight by describing the loss function as the average information per token, from the model's perspective.

The next step from here is to explain how it's possible to turn a general predictor into a compressor. For instance, turning a language model, this prediction machine, into a language compressor. More specifically, one where the number of bits that you use to represent a piece of text will approximately match the information content of that text, from the model's perspective. It's actually very surprising this is even possible.

There's one very visual and very beautiful compression algorithm showing how to do exactly this that you and I are going to dig into in the next part. And once you understand this, it makes clear how using cross-entropy loss is actually equivalent to training the model to be the best possible text compressor. This, in turn, gives us a nice hill to stand on where we can look over the landscape and assess that thought-provoking phrase, "compression is intelligence", head-on.

I do want to add one final footnote to this video, because it would be a shame not to at least quickly explain a related concept called KL divergence, which you also see all the time littered throughout machine learning papers. Before I jump into that, I want to make a very quick plug for 3b1b talent, because there's actually a puzzle on that page that is directly related to KL divergence.

For context, this is something like a virtual career fair that I've put together this year, where the premise is to have a set of partnered organizations that are interesting places to work, who are also keen to hire the kinds of people like you, people who watch videos about things like the relationship between compression and intelligence. One of the main features of that page is a set of interviews that I did with the various teams, which I think is just a much better way to let you get to know the culture of a company than trying to just read a generic jobs page.

But another thing you'll find is that many companies there have featured challenges specifically for this audience, where you are often invited to mention your solution in an application. Now, this was not at all planned, but by happenstance, the challenge that one of the companies, Dopple, put up there happens to use the formula for KL divergence. They didn't know I was planning this video, so you can take this as a nice bit of evidence that the math I'm teaching you here really does show up out in the real world. This is just one example, but you can find a number of other interesting places to work with nice puzzles and challenges for you to try out at [3b1b.co/talent](https://3b1b.co/talent).

Okay, so what is KL divergence? Remember that key property of cross-entropy that I want you to come away remembering: the fact that it takes on a minimal value when $P$ and $Q$ are the same, and that that minimum is equal to the entropy of $P$. This makes it very natural to want to give a name to describe the difference between these two values. And indeed, this difference has the special name: it is the Kullback-Leibler divergence, commonly abbreviated to KL divergence: $$D_{\text{KL}}(P \parallel Q) = H(P, Q) - H(P)$$

In the language of compression, you would think of it as describing: how many bits per symbol are you wasting by using a poorly optimized code? For example, in our robot case, if you take the bits per symbol in the unoptimized case minus the bits per symbol in the optimized case, that difference gives you the KL divergence between the two distributions. It's specifically telling you how wasteful you are.

In the machine learning setting, KL divergence acts as a kind of distance measure between distributions. It's zero when both of them are the same, but it grows as they differ. It's not exactly a distance, though, because it's asymmetric: the KL divergence of $Q$ relative to $P$ is not the same as that of $P$ relative to $Q$.

To cap off today, I want to leave you with three things to ponder related to this expression: The first one is easy, which is how when you see it in practice, it often comes up in this more compact form: $$D_{\text{KL}}(P \parallel Q) = \sum_i p_i \log\left(\frac{p_i}{q_i}\right)$$ I just want you to convince yourself that these two expressions really are the same. The compact form hides the fact that it's really just a difference between cross-entropy and entropy, but it is more succinct. Secondly, I've been showing this diagram, a variant on our cross-entropy diagram. I want to see if you can take a moment to convince yourself in what sense this is representing our expression. And third, I mentioned that when you distill a large model into a smaller one, you use the cross-entropy between their distributions as a loss function. I want you to ask yourself: what would happen if instead you used the KL divergence? After all, if the KL divergence is like a distance measure, wouldn't this be a more natural choice?