Reinventing Entropy | Compression is Intelligence Part 1

0:00 [Submit subtitle corrections at criblate.com] When you encode text into binary,

0:02 it's often nice to use as little data as possible,

0:04 so you might naturally wonder, is there some kind of fundamental limit

0:08 on how efficiently text can be compressed?

0:11 The default encoding with ASCII is pretty inefficient.

0:14 Each character is represented with eight full bits.

0:17 If you apply a little cleverness associating

0:19 more common characters with smaller bit strings,

0:21 you can get this down to an average of around four bits per character,

0:25 and then much smarter methods than

0:27 that, that leverage patterns among long sequences of text,

0:29 can get even better still.

0:32 But again, what's the limit?

0:34 I'm guessing many of you might have heard an estimate here,

0:37 I will share one at the end, but much more interesting than any single numerical

0:41 answer is how you would even approach answering it.

0:44 This question dates back at least to the 1940s,

0:46 with Claude Shannon's seminal work that kicked off information theory.

0:50 Now what's very interesting is how the math that he developed to answer

0:54 questions like this has turned out

0:56 to be surprisingly useful for modern machine learning.

0:59 To take the salient example of today, when large language models are trained,

1:03 the pre-training portion of that is usually

1:06 described as being about next token prediction,

1:08 specifically using something called cross-entropy loss.

1:12 Now that term, cross-entropy, has its roots in information theory.

1:15 But what's also interesting is that one of the conclusions

1:18 of information theory says that prediction

1:21 and compression are mathematically equivalent.

1:23 They turn out to be two sides of the same coin.

1:26 Which means, you can entirely reframe how you think about the pre-training

1:30 objective as not really being about next token prediction per se,

1:33 but instead as being about creating the most efficient possible text compressor.

1:38 Later I'll explain exactly how that works, but when you do,

1:41 I think it offers more clarity on what this notion of cross-entropy really is,

1:45 and why you're using it.

1:46 Also, I don't know about you, but to me at least,

1:49 there's just something very intriguing about using

1:51 compression as a fundamental objective while pursuing intelligence.

1:55 In fact, some people have gone so far as to say, compression is intelligence.

2:00 Now, as stated, that's a hard claim to judge rigorously,

2:03 since intelligence is such a squishy and ill-defined term.

2:06 The safer claim would be that the mathematical

2:09 theory of compression is bizarrely relevant to artificial intelligence.

2:14 Still, the pithy phrase is thought-provoking,

2:16 so this is the first in a trilogy of videos aimed at laying

2:20 down the mathematical fundamentals to assess

2:22 what this claim is really getting at.

2:24 For the next 30 minutes or so,

2:26 you and I will be focused on understanding the limits of compression,

2:29 and seeing if we can get you to feel like you

2:32 could have rediscovered the core idea behind Shannon's noiseless coding theorem.

2:36 Doing so involves rediscovering a few key definitions,

2:39 namely those of information and entropy.

2:42 And it might sound a little weird for me

2:44 to describe definitions as something to be discovered,

2:46 but great definitions are often the residue of some kind of insight.

2:51 See, these two specific terms are really not hard to define

2:53 in the sense of laying down a formula for you,

2:56 but doing so too early would spoil a good story.

2:58 It is much more fun to see how you are inexorably

3:01 drawn to them by asking about the limits of compressing language.

3:05 And what I want you to notice by the end

3:07 here is how we can't really answer this question, or at least Shannon couldn't,

3:12 without necessarily engaging with some notion of intelligence.

3:19 We will get to modelling language, which is wonderfully complicated,

3:22 but it helps to warm up with a simpler example

3:25 containing the same essential ideas needed for our path of rediscovery.

3:29 Imagine you have a robot that we have sent to a faraway moon,

3:32 whose job is to wander the surface and collect data.

3:36 From here on Earth, we send it instructions for how to move

3:38 that are going to be limited to four very simple possibilities.

3:42 Move up, down, left, or right, each one with a fixed step size.

3:47 The nuance will be that these instructions are not uniformly distributed.

3:51 Half of everything we send is up, one fourth of the instructions are down,

3:56 one eighth are left, and the other eighth are right.

4:00 It's a little contrived, it's meant to be a simple example,

4:02 and in that spirit of simplicity,

4:04 we're also going to assume that every instruction is independent.

4:08 They are sampled from this distribution regardless of the preceding context.

4:12 When we send data to this bot far away, we're doing it as a stream of bits,

4:16 ones and zeros, and it's very slow

4:18 and costly to do that, so the natural question,

4:21 the warm-up puzzle for you today, is to ask what is the most efficient possible

4:25 way to encode these instructions as a stream of bits.

4:29 And here, we might imagine three students who each attempt an answer,

4:33 one who's straightforward, one who is clever, and one who is very theoretical.

4:38 The straightforward student immediately raises their hand and says, well,

4:41 for each of these four instructions, we could just use two bits.

4:45 Maybe 00 encodes up, 01 encodes down, 10 encodes left, and 11 encodes right.

4:52 On the receiving end, this makes it very easy for the robot to decode.

4:55 It simply breaks up the bitstream into chunks of two,

4:58 and translates each chunk into the appropriate instruction.

5:02 Now, the clever student points out, well,

5:04 that does nothing to take advantage of the fact

5:07 that up comes up way more frequently than left or right.

5:10 They propose a method where we use

5:12 a different number of bits for each instruction.

5:14 I'll explain it in just a second,

5:16 but I do want to call out the fact that as soon

5:19 as you let different instructions get different numbers of bits,

5:21 it's certainly not obvious that the robot is going to know how to decode it.

5:25 After all, it needs to somehow know where to draw the dividing lines.

5:30 Now, being very clever, the second student has thought that through,

5:33 but it's easiest to explain if I just kind of lay it all out.

5:37 What they suggest is letting the single bit 0 represent up,

5:41 letting the two bits 10 represent down, using 110 for left and 111 for right.

5:47 You can calculate the average number of bits per

5:50 instruction that this would require with a simple weighted sum.

5:53 Half the time, only one bit is used, a quarter of the time,

5:56 two bits are needed, and the remaining times, you need three bits.

6:00 When you add this all up, as a weighted sum, you get 1.75 bits per instruction,

6:04 which is indeed better than the more naive

6:07 approach of a flat two bits per instruction.

6:10 The second student is spending more bits on those last two instructions,

6:13 but because they come up so much less frequently,

6:16 this is more than made up for by using

6:18 only one bit for that most common instruction.

6:20 And you can see this efficiency bear out empirically too.

6:24 This right here is a set of instructions sampled from that distribution.

6:28 You'll notice lots of ups, about half as many downs,

6:31 and even fewer lefts and rights.

6:34 When you turn each symbol

6:35 into the appropriate bit string following this encoding,

6:38 the resulting sequence of bits is indeed

6:40 shorter than what the naive method gave.

6:43 But I hear some of you asking, how does the robot know how to decode this?

6:47 Can we be sure that there's an unambiguous way to draw the dividing lines?

6:51 In the lingo of encodings, each of these four bit strings used

6:54 to encode the instructions is called a code word.

6:57 And as we step through things here,

6:58 see if you can figure out what rule the clever student was

7:01 following to make sure that their code words don't conflict with each other.

7:05 And really, you just need to look at an example

7:07 bit stream from the robot's perspective and think it through.

7:11 Let's say that that very first bit that it receives is a 1.

7:13 So far, this could be encoding any of the last three instructions,

7:17 down, left, or right.

7:19 If what follows is a 0, then it can only be down.

7:23 There is no other possibility.

7:25 So the robot can register that as a complete instruction.

7:28 From there, starting fresh, if what follows is a 0,

7:30 that must be encoding up, since there is no other possibility.

7:34 Nothing else starts with a 0.

7:36 After that, if they see a 1, this is so far ambiguous,

7:39 it's the prefix for any of the last three code words.

7:41 If the next bit is another 1,

7:44 it remains ambiguous, it's the prefix of the last two.

7:47 But that following 0 then makes clear

7:49 these three bits must have been encoding left.

7:52 In short, all the robot has to do is read in the next

7:55 sequence of bits until the moment that it forms a complete code word,

7:59 at which point it can register it as a complete instruction.

8:03 If you step back and think about it, the key constraint for this all to work is

8:08 that no code word can be a prefix of another one.

8:11 For example, let's say you tried to introduce

8:13 some fifth instruction that had the code word 100.

8:17 That would cause conflicts, because after reading 10,

8:20 it's not clear whether that's supposed to be down,

8:22 or if it's supposed to be the start of this new fifth instruction.

8:27 When you avoid this kind of conflict,

8:28 an encoding method like this has a special name.

8:31 It's known in the business as a prefix-free code,

8:34 or what is confusingly synonymous,

8:36 it's actually more commonly known as a prefix code.

8:38 And there's a really nice way to visualize choosing prefix-free

8:42 codes with a certain diagram that represents every possible binary string.

8:47 This diagram also has some helpful parallels with how

8:50 I want to show entropy in just a few minutes.

8:52 It's probably decently intuitive what's going on if you

8:55 just pause and stare at it for a bit, but I'll call out the important features.

8:59 Each layer shows every bit string of a given length,

9:02 and you'll notice everything that starts with a 0

9:05 lives on the left half of this diagram,

9:07 and everything that starts with a 1 lives on the right half of the diagram.

9:12 And that same idea continues recursively as you go up.

9:16 So everything starting with 00 is above this quarter of the diagram,

9:20 everything starting with 01 is above this quarter of the diagram, and so on.

9:25 In particular, the key property is that every binary string

9:28 in this diagram is a prefix for everything that sits above it.

9:32 So when our clever student chose to allocate

9:35 a single bit 0 to represent the instruction up,

9:38 they were effectively consuming half of the space

9:41 of all possible code words by doing so, since everything starting with a 0 is

9:47 now prohibited based on this prefix-free property.

9:50 Similarly, allocating one 0 to down eats up another fourth of this space,

9:54 and the remaining two instructions each eat up an eighth of the space.

9:59 You can just see how nothing is left over.

10:02 And at this point, I'm guessing that there's

10:04 some bell kind of resonating in your mind,

10:07 given that these proportions are all exactly the same

10:10 as the probability for each instruction coming up.

10:13 And in fact, that tickling sensation of a relationship between data

10:17 size and probabilities is exactly the founding insight for information theory.

10:23 When you stare at this pleasing alignment,

10:25 it might suggest that the clever student's solution is not just better,

10:29 maybe it's somehow perfect.

10:32 But at the moment, that feels like a bold claim to make.

10:34 How could you know that there's not some

10:36 ultra-clever method that does something fancy with really long

10:39 sequences of instructions that somehow makes it so

10:42 the average bits per instruction gets even lower than this?

10:46 This takes us to the third student, Head in the Clouds,

10:48 who has not really been thinking about actual codes that they can implement.

10:52 They have been pondering what properties a perfect,

10:55 optimally efficient code would have.

10:58 They have this really clever idea,

11:00 which is to argue that random noise should be incompressible,

11:03 and therefore, a perfect compression algorithm should

11:06 produce a bitstream that's indistinguishable from random noise.

11:10 What's neat is, even though that sounds kind of simple,

11:13 this can actually lead you to reinventing the idea of Shannon entropy.

11:17 Now when I say random noise, what I mean is that each bit is a 1 or a 0,

11:21 with 50% probability, and all of the bits act independent from one another.

11:26 It's not hard to show that our second

11:28 student's encoding for the robot genuinely follows this rule.

11:31 If you think about it,

11:32 there's a 50% chance that the message starts with the instruction up,

11:36 so that first bit has a 50% chance of being a 0, otherwise it's a 1.

11:41 And then if it is a 1, there's a 50% chance that the instruction is down,

11:45 meaning the next bit is 0, otherwise it's a 1.

11:48 And so on.

11:49 Each new bit really does act like an independent coin flip,

11:53 so to the receiver, that compressed

11:55 bitstream really is indistinguishable from random noise.

11:59 But why am I saying that random noise is incompressible?

12:02 Well, for that, let's really focus on things from the receiver's perspective.

12:06 And here, instead of thinking instruction by instruction,

12:09 it helps to zoom out and frame our discussion in terms

12:11 of entire messages and what the encoding for full messages looks like.

12:15 When that receiver sees a string of n bits representing some compressed message,

12:19 this is one out of 2 to the n possible

12:22 messages they could have received that would have the same size.

12:26 And then critically, because we're assuming this looks like random noise,

12:29 all 2 to the n of those messages must be equally likely.

12:33 Now to be clear, we're not just talking about the robot example anymore.

12:36 Our theoretical head-in-the-cloud student really wants to make an argument

12:40 for what perfect compression looks like for any data type,

12:43 like maybe we're compressing language or compressing images,

12:46 and they want an argument that works regardless

12:48 of the details of what specific compression algorithm you're using.

12:53 A loose intuition in your head is that maybe among

12:55 all of the messages that compress down to n bits,

12:58 some of them would contain a larger amount of predictable data,

13:01 while others would have started as a smaller amount of unpredictable data.

13:05 But the key point is that if

13:07 the compressed bitstream really does look like random noise,

13:10 meaning all of the bitstrings of size n are equally likely,

13:14 it must be the case that all the underlying

13:16 messages being compressed were equally likely to arise,

13:19 and even more specifically with probability 1 over 2 to the n.

13:23 So again, why am I claiming that this is incompressible?

13:27 Well, let's pull up that same diagram,

13:29 representing the space of all possible binary strings.

13:33 In this case, we can think of all the encodings for our 2

13:36 to the n equally likely messages as being

13:38 the bitstrings on one layer of this diagram.

13:42 If you tried to define an alternate scheme,

13:44 where you tried to become more efficient

13:46 by making one of these messages use fewer bits,

13:49 it would move lower on the diagram,

13:51 which means it then overlaps with some other message,

13:54 so you would have to put that other message somewhere else in this diagram.

13:59 At minimum, that means it's sharing a space with yet a third message,

14:02 and those last two have to kind of get bumped up one layer,

14:05 requiring that extra bit for each of them to disambiguate.

14:09 So saving one bit over here costs you two bits elsewhere.

14:13 You're basically pushing down a bump on the rug,

14:15 only to see it pop up even worse in another spot.

14:18 In general, any message encoded with a string lower on this diagram is

14:22 going to be eating up more than its fair share of the space,

14:26 which forces multiple other messages to occupy a smaller region,

14:29 bumping them higher up, meaning they're encoded less efficiently.

14:32 I'm going to guess that it's decently

14:34 intuitive for everyone watching that the most efficient

14:36 scheme here for equally likely messages is

14:38 to give them all the same number of bits,

14:40 but I do think the diagram gives a more concrete

14:43 way to see why you end up with unfavorable trade-offs otherwise.

14:47 Once you have this idea that perfect compression looks like random noise,

14:50 this is exactly the kind of thing I was referencing in the intro,

14:53 about how insights can lead you to definitions.

14:56 Notice how what we're basically saying is that a message that uses n bits

15:01 in a perfect scheme must have a probability of 1 over 2 to the n,

15:05 or 2 to the negative n.

15:07 If you take the log base 2 of both sides here and then negate,

15:11 this is equivalent to saying that the number of bits allocated to a message,

15:15 assuming perfect compression, is negative log base 2 of p,

15:18 where p is the probability of occurring.

15:22 This negative log expression is the fundamental

15:25 formula for all of information theory.

15:27 Everything up to this point is me trying to make this value

15:30 feel like something you are inevitably

15:32 drawn to by asking about perfect compression,

15:35 rather than it feeling like some arbitrary definition that we start with.

15:39 Some students do find this negative log takes a little getting used to.

15:43 You know, it looks like it should be a negative

15:45 value before you think about the fraction in the middle,

15:47 but really the intuitive way to read it is that it's asking how many times

15:51 do you chop your space of possibilities in half to get to a certain quantity.

15:55 Here, let me pull up some axes and show you the graph of negative log of p.

15:59 I've also seen some authors default to writing this as the log of 1 over p,

16:04 which maybe you find more intuitive.

16:06 You could also think of it as the log base 1 half of p,

16:09 which I've never really seen anyone lean into, but personally

16:11 I would be quite partial to that as a convention.

16:14 Now, however you write it, what Shannon realized is that this is a very

16:18 useful way to think about the information that a message

16:21 contains even when literal perfect compression is not possible

16:24 and p is no longer a clean power of 2,

16:27 which would mean that the output here is some fractional amount.

16:31 In fact, he defined this expression to be the information of an event.

16:36 The image I sometimes have in my head is to picture

16:39 the probability of an event with a little pie chart,

16:41 and the information is this bar above it that gets kind of pumped

16:45 up to be taller as the probability is squeezed closer to zero.

16:49 That is, unlikely messages contain a lot of information,

16:52 and the bar is relaxed to get shorter as the probability approaches 100%.

16:57 Highly expected messages contain very low information.

17:01 I want to be clear that there is content to this definition.

17:05 It's more than just rescaling probabilities,

17:07 as if converting to an alternate unit system.

17:10 You've already seen the core idea.

17:12 In a perfect compression scheme, the number of bits allocated to a full

17:16 message precisely equals this information content.

17:19 Now, of course, perfect compression is not always possible.

17:22 Your probability's messages are likely not perfect powers of 2.

17:26 So the more general way you would frame this is to say that the information

17:29 of a message gives you a lower bound on how much it can be compressed,

17:32 at least when you average overall possible messages.

17:35 It's perfectly possible to overfit a compression algorithm to one specific case.

17:40 And to really wrap your mind around information and fractional bits,

17:43 we need to step up our game beyond that warm-up example.

17:46 See, with the robot, the probabilities were overly clean.

17:49 They were all perfect powers of 2,

17:51 so that the information per symbol could precisely match a whole number of bits.

17:55 But Shannon was very interested in this question of limits

17:59 on compression for much more realistic and complicated cases,

18:02 like natural language.

18:04 For example, here I'll pull up the probabilities

18:06 for each new letter in an example phrase,

18:08 at least as determined by a little GPT that I'm running locally.

18:13 And, by the way, if the probabilities provided by a model

18:15 feel like those might be distinct from the probabilities of actual language,

18:19 you would be right to raise an eyebrow.

18:21 Hold on to that thought.

18:22 It becomes very relevant later.

18:24 One key difference with language is

18:26 how heavily dependent on context everything is.

18:29 The probability distribution for each new letter you see is highly,

18:33 highly contingent on everything that came before it.

18:36 The other big difference is that all

18:38 of these probabilities are obviously not going to be clean, perfect powers of 2.

18:42 So if you compute the Shannon information of each one

18:44 of these, meaning you take the negative log base 2,

18:47 all the numbers that you see are fractional amounts.

18:51 And again, giving a vague interpretation of what these mean is really not hard.

18:55 Information content is low for very predictable letters,

18:58 and it's high for very unpredictable letters.

19:01 But all of you watching this are

19:03 smart enough to demand a more exact interpretation,

19:06 one that justifies why these values deserve to be given the units of bits.

19:10 I mean, it's not like there's going to be some perfect encoding

19:14 where this letter i has a code word that is somehow 4.19 bits,

19:18 or where this highly predictable o is somehow

19:20 encoded with just a narrow sliver of a bit.

19:24 The real meaning is related to encoding entire messages

19:27 and coming up with a bound on their compression.

19:30 The probability for a full phrase, like the one I'm showing here,

19:33 looks like multiplying the probabilities for each successive new letter,

19:37 where again, I'll emphasize that these successive

19:40 letters' probabilities are conditioned on what came before.

19:44 This is essentially the chain rule from probability.

19:47 I want you to notice how nicely this plays with a logarithm.

19:50 If you ask for the information of that full message,

19:53 taking this negative log expression,

19:55 because logarithms turn multiplication into addition,

19:58 this breaks up really nicely as the sum

20:01 of the information for each individual letter.

20:04 In the final part of this trilogy,

20:05 I'm going to walk you through a very specific compression algorithm that would

20:09 actually compress this text to within one or two bits of this value.

20:13 It's no longer as simple as mapping each character to a predefined code word,

20:17 but you nevertheless get this very direct

20:19 sense of thinking about adding up the fractional

20:21 information content of each letter to determine

20:24 the length of the final encoding that you use.

20:27 So that's the key idea.

20:29 Even if, by the time you need to relate this to actual data sizes,

20:32 things will get rounded off to the nearest whole number,

20:35 what Shannon realized is just how useful it

20:37 is to work at this higher layer of abstraction,

20:39 where all your information is allowed to freely be

20:42 continuous and information of successive events really nicely adds together.

20:48 Still, if you step back and imagine yourself

20:50 very seriously assessing the fundamental compressibility of language,

20:53 all of this hinges on the question of how

20:56 you know the probabilities for each successive letter.

20:59 Here, for all these animations,

21:01 I've been illustrating things using a language model, but for one thing,

21:04 that doesn't necessarily feel the same

21:06 as the true probabilities underlying language, and for another,

21:09 it's not even clear what we would mean by the true probabilities of language.

21:14 So here, I actually think it's most enlightening

21:16 to take a step back in time and see

21:18 how Shannon himself thought about all of this long

21:21 before language models or modern data analysis.

21:23 Some of his earliest experiments on the information

21:26 of language involved looking at specific short sequences of characters,

21:30 what you often hear referred to as n-grams,

21:32 and then tracking the statistics of what tended to follow.

21:36 So, for example, if you scan through a few books,

21:38 and you notice every single time the two letters th

21:40 come up and you record what letters tend to follow,

21:43 you could build up a table of those letters and let

21:45 those statistics represent a sample for the probabilities you care about.

21:49 Now, the problem is that this just completely

21:52 breaks down for longer strings of letters, most notably,

21:54 any string of text that never shows up

21:56 in all of the books that you're analyzing.

21:58 Nevertheless, it's perfectly reasonable to talk about

22:01 what's expected to follow such a longer string.

22:04 In fact, if anything, it's more important to talk about those cases,

22:07 since longer context windows are when things are at their most predictable,

22:11 and that's where you stand to get

22:13 the most compression due to that predictability.

22:16 So instead of using raw statistics, a little bit later,

22:19 Shannon analyzed a different model of the English language

22:22 that he had available to him, his wife Betty.

22:25 As the story goes, Shannon pulled out a book

22:27 and began asking Betty to guess each next letter.

22:31 Shannon would then transcribe her guesses letter by letter.

22:34 Every time she guessed incorrectly, he wrote down the correct letter,

22:38 and then whenever she guessed correctly, he would just replace it with a dash.

22:43 The idea was that this transcribed version he

22:45 was creating has fewer actual letters than the original,

22:47 but his point was that it contained the same amount of information,

22:51 at least in the following sense.

22:53 If he could somehow obtain an exact replica

22:55 of his wife and conduct the guessing game again,

22:58 he would only need to supply her with this reduced text.

23:02 These letters by themselves would provide just the right

23:05 prompting for his duplicate wife to exactly reproduce the original.

23:09 Of course, in practice, a person wouldn't necessarily guess the same way twice,

23:13 and while this qualitatively conveyed

23:15 the idea of predictability allowing for compression,

23:17 it wasn't yet a measurement of information.

23:20 A bit later still, in his 1950 paper, Prediction and Entropy of Printed English,

23:24 Shannon updated the experimental design to get a more robust read

23:28 on this slippery question of the average information content in English.

23:33 This time interviewing more people,

23:34 instead of just logging whether each guess was right or wrong,

23:38 Shannon recorded how many guesses were necessary for a human

23:41 guesser to come up with the correct next letter.

23:44 And then separately, he had this whole method for associating

23:47 the number of guesses required with an implicit

23:50 probability that a person would have been assigning to the true next letter.

23:54 The details of that are a little bit in the weeds,

23:57 but the broader point I want to make is how, in analyzing language,

24:00 he wasn't just doing pure data analysis looking through books.

24:04 He was trying to probe at an underlying model of language,

24:08 namely the interviewee's brain.

24:10 These brains that he could talk to were effectively treated as black boxes,

24:14 ones with a sophisticated and yet indescribable understanding of language

24:18 and an ability to predict characters based on the context.

24:22 Now these days, in the 2020s, we have gone from merely interrogating black

24:26 boxes that process language to designing them.

24:29 The reason that you and I are here, revisiting the roots of information theory

24:34 and this study of how compressible language is,

24:36 is because of how much of the math in modern

24:39 machine learning leverages the formulas that emerged in this field.

24:43 Aside from the definition of information itself,

24:45 there are three more key expressions that I

24:47 want you to feel like you could have rediscovered,

24:50 not just because rediscovery makes them more memorable,

24:54 but because seeing how they naturally

24:56 arise from studying compression gives a more

24:58 solid ground from which you can assess

25:01 that thought-provoking interplay between compression and intelligence.

25:05 You already have everything you need to reinvent

25:07 the first of these, which is entropy.

25:10 Imagine you have any signal that can be thought of as a sequence of symbols,

25:13 whether that's the four robot instructions, the English language,

25:17 or really anything else you dream up.

25:19 Entropy asks about the average amount of information for each symbol,

25:23 and then based on everything we've been discussing,

25:25 where perfect compression looks like random noise, and how, in that case,

25:29 the number of bits used for a message is

25:32 the same as the information content of that message,

25:34 which again breaks down really nicely as the sum

25:36 of the information of all the symbols.

25:39 This question of measuring the average information per

25:42 symbol is basically asking about the limit of compression.

25:45 It would give you a lower bound

25:47 on how efficiently a given signal could be compressed.

25:51 And you and I already calculated this in one setting,

25:53 when we took that weighted sum to find the average

25:56 bits per instruction for the perfect encoding of the robot case.

26:00 Basically, because that encoding was perfect,

26:02 each symbol's code word length is exactly the same as its information content.

26:06 So, effectively, we're calculating the average information per symbol.

26:10 To generalize this, here's how that looks.

26:13 For any given probability distribution,

26:15 characterizing whatever symbols your messages are made out

26:19 of, the average information per symbol should look

26:22 like adding up p times the negative log

26:24 of p for each probability p in that distribution.

26:28 And take a moment to notice how we're visualizing this expression.

26:32 Throughout the video,

26:33 we've been picturing probability distributions with stacked horizontal bars,

26:37 where each bar's width is equal to its probability,

26:40 so altogether they add up to be 1.

26:43 Now, above each one of those, I've put a rectangle

26:46 whose height is locked to be the corresponding information value,

26:49 the negative log base 2 of that probability.

26:53 So the weighted sum up top, the average information per symbol,

26:57 can be thought of as the total area of all these rectangles together.

27:01 This is not yet fully general.

27:03 It only describes the compression limit in cases

27:05 where every new symbol follows some identical distribution.

27:09 That's true in the robot case, but it's not true in English, for example.

27:13 Nevertheless, it's important enough to deserve a name.

27:16 And there's a fun story about how John von Neumann

27:19 supposedly told Shannon that he should call this expression entropy,

27:22 since, for one thing, it resembles an expression already used for the idea

27:27 of entropy in statistical mechanics, and for another,

27:29 quote, nobody knows what entropy really is,

27:32 so in an argument, you'll always have the advantage.

27:35 I looked into it, it's probably apocryphal,

27:37 but there seems to be a grain of truth to this.

27:40 Now, whatever the true story is, Shannon did call this quantity entropy,

27:44 and he denoted it with the letter h.

27:47 And it's fun to take a moment to play

27:48 around with this graphic to build a little intuition.

27:51 The more evenly distributed a probability distribution,

27:54 the higher the total entropy, whereas if we squish things to become very uneven,

27:59 maybe with one event dominating the probability space,

28:02 this would have a very low entropy, since that one overwhelmingly probable

28:06 event carries correspondingly little information.

28:10 And then also, if you divide up the probability space even more,

28:13 meaning it's distributed over more total possible symbols,

28:17 each one has more information, so the total entropy is higher.

28:21 And once more, it's fun to kind of slosh everything around,

28:24 where a very skewed distribution gives lower total entropy,

28:27 whereas a more even spread gives us higher entropy.

28:31 The vague qualitative intuition here is that entropy

28:33 measures the amount of uncertainty in a distribution,

28:37 but the more precise understanding,

28:39 justifying why it deserves to be given in units of bits,

28:42 is that it describes the minimum number of bits

28:45 per symbol necessary to encode a message following this distribution.

28:50 That statement, and everything we just covered,

28:52 is more or less the content of a core

28:55 theorem in Shannon's 1948 paper that kicked off information theory,

28:58 the noiseless coding theorem.

29:00 It states that no encoding can ever be more efficient than this limit,

29:04 and even more strongly,

29:05 he showed that it's always possible to get arbitrarily close to this limit.

29:11 Now like I said, this expression only applies

29:13 in cases where every symbol follows the same distribution,

29:16 but Shannon was of course keenly interested in a more general setting,

29:19 where the probabilities for each new

29:22 symbol don't necessarily follow the same distribution.

29:24 In particular, he spent a ton

29:26 of time contemplating the compressibility of natural language.

29:30 This requires a more general notion of entropy,

29:32 something known as the entropy rate for a stochastic process.

29:36 But it's the same basic question.

29:38 What is the average information per symbol,

29:40 except in this case we're now averaging over all possible messages.

29:45 This is almost never a clean calculation that you can perform

29:47 with some clean visual like the one we were just playing with.

29:50 After all, what formula describes the probability distribution for language?

29:56 So if you hear reference to the entropy of language,

29:59 this is well beyond what any exact calculation can give you,

30:02 hence why Shannon turned to estimates based on observation.

30:06 And again, his methodology was not just data analysis.

30:10 It's not some function that you can perform on a corpus of text.

30:13 In order to get a satisfying estimate on compressibility,

30:16 he found himself inevitably needing to probe at intelligent models of language.

30:21 When his interviewees had at least 100 preceding letters of context,

30:25 he estimated the entropy of English to be about one bit per character.

30:29 This is a pretty wild number when you think about it,

30:32 because it suggests that English could be compressed down

30:34 to just a single yes or no answer for each character.

30:39 Wild as that sounds, in the third part here,

30:41 I will show you that algorithm I've referenced, where if you're allowed to use

30:44 a high-quality language model for encoding and decoding,

30:47 you can get surprisingly close to this limit in practice.

30:51 Before then, it helps to understand a variation on entropy,

30:54 known as cross-entropy,

30:55 asking both how and why it's used in training large language models.

31:00 If you want to learn that, as well as a few

31:02 fun related ideas like how large models are distilled into smaller ones,

31:06 and why on earth GZIP can recover the structure between distinct languages,

31:10 come join me in part 2.

31:14 Regular viewers will know that my new experiment for this year

31:17 is to have a virtual career fair, a page at 3b1b.co.

31:21 talent, where this audience can explore aligned career opportunities.

31:25 The meaningful update is just how much more content there is now,

31:28 mainly in the form of featured interviews between me and the relevant teams.

31:32 Here's my thinking.

31:33 I feel like when you're assessing potential jobs,

31:35 it's almost impossible to get a true sense of what it's

31:38 like to work at a place just by poking around online,

31:40 and you learn orders of magnitude more if you have

31:43 a chance to sit down for lunch with a couple team members.

31:46 My hope is to give you the vicarious version of that.

31:49 So, if you're curious what I mean when

31:51 I say these are all thoughtful and curious teams, go take a moment to explore.

31:55 I really think you'll enjoy it.