Video 7-4: §7.3 Entropy

0:00 Intro

0:03 we talked about huffman coding and that it always constructs uh a code a prefix free code for a given alphabet with given weights so that it minimizes this sum the expected codeword length but how good that is remains to be seen and luckily in the case of huffman codes and in in this case of prefix free codes we have a fairly complete understanding of what what happens and this is where entropy comes in that's why i asked before how many people have have seen this so maybe let me just show the answers here one more time also in the main video so i asked you if you know what entropy in this information theoretic sense is and how it relates to huffman coding and uh quite a few people do know but some others have never heard it so i'll try to give somewhat a brief introduction without spending a heck a lot of time so what is entropy simply speaking it's this definition that you see on the slide it's it's defined for a set of probabilities so we assume we have a random outcome here numbers 1 up to n but it could be other objects the important thing is that we have a finite number of these or a discrete number of outcomes

1:07 What is entropy

1:32 and the probabilities are given like this as always the probabilities are between 0 and 1 and they sum to 1 that goes without saying whenever we say probabilities and then the entropy is defined as this sum we take the sum of all possible outcomes the probability for that and then log of 1 over the probability

1:59 another way to write this is saying that it is an expected value over log of 1 over the probability for the outcome that's that's just another way of writing this sum because uh it's a sum that weighs things with the probability that is an expectation by uh definition uh but we'll not not really dwell on this uh interpretation much that's just the definition

2:27 so maybe before we continue with this we might want a small tiny example so say you have a fair die with a usual one not the um not the dungeons and dragons version with whatever many faces with just six faces the usual one and fair means so all of the outcomes one to six happens with probability one over six so what is the entropy of of this distribution of this random variable of uh the faces of of a die well just look at the um

3:14 definition so if i write write it like this i would have to copy uh one over six six times but i'm relying on your intuition on your ability to guess that from the context what it is is the sum over well six times the same thing so we can write it like that but it's really a constant term inside the sum and then we have one over one over six all right just do it in slow-mo it's six times the same thing and weight by one over six so that is a one times and then log of one over of one over that's log of six right

4:00 and uh well whatever that is um can we get log off okay this uh maybe i should have prepared it it's some number between zero and three uh between two and three and uh well whatever whatever it is maybe someone wants to uh compute it and send it in the chat or so but it doesn't really matter much so uh entropy has this feature that it sometimes has fractional values not always though

4:31 let's do another another small example a fair coin so we have heads and tails each with probability one-half if we do the same calculation everything's remain everything remains the same except that this is a one over one-half so it's log of two and my log is always base 2 right so that's just 1. so here the entropy is exactly 1.

5:12 okay uh those are two simple examples in the general case if the probabilities are not all the same then the sum doesn't simplify yes as easily but you can still compute this for any uh given set of probabilities

5:25 What is entropy for

5:30 what we need entropy for is as a measure of information content of a distribution so how is that to be understood in a sense uh people often say it's the surprise the amount of surprise that you get when you learn the outcome of such a random experiment so say you throw a random die and you learn it came up with five uh how surprised are you to find five well entropy says you you should be surprised two point something bits whatever log of two is a log of sixes okay that's not very intuitive um more intuitive is using something like this 20 questions game and i want to uh introduce this here in a very specific setting namely the one that we use that we will need for huffman coding later on so the game is as follows you start with the unit intervals zero to one

6:33 then i think about an interval this little red one it's somewhere in this unit interval it's a subset of the unit interval some interval somewhere and then you start guessing and your first question before you start you know nothing except that it's somewhere in the unit interval and now you can guess you can ask questions is your interval contained left of a certain point or right of a certain point and a moment's reflection shows that uh the best you can do is um to always ask is it left or right of the middle point okay and we'll um we'll make our life simple here by assuming that um you never hit the interval you would have to define this a little different it works cleanest if the intervals have uh specific numbers only as their endpoints so let's let's just see how this this game goes in the cleanest version before you ask uh the first question you know nothing it could be anywhere then you ask is it left or right off the point one half and in this case i answer it's above one half and so you have learned something and you have spent one question you have narrowed down the interval to this uh this range one half up to one then

7:59 you continue doing this uh you ask is it above or below three quarters and i say oh it's below so you've learned a bit more and you've spent two questions and that's two bits of information two yes no questions and you keep going uh you ask one more question i again say it's in the upper half okay you learned that and one more time and then i say well yep um i'm i'm spanning the range that you have i extend over the entire thing and so with four questions you have learned what my interval is in this clean way that's what it works like what it works out like and the observation to make here is that if you look at the length of this interval and you take log of 1 over the length that's log of 1 over the probability for a random point on the unit interval to randomly fall inside my interval

9:07 then you get exactly 4. if you want to think about this game um again maybe a cleaner way is to think about not this interval as as an interval but you throw a random point somewhere and you're asking is it inside this red interval or no and you know which intervals are possible up front this will come back to this in this context of huffman coding

9:44 Intuition

9:48 okay so intuitively what happens is we need to cut our interval in half that many times before we can reach uh the conclusion potentially if we're lucky in our you know how the numbers work out we need at least that many halving steps before we can reach something that's small enough to be covered by this interval that you're looking for and that's that's the way to think about entropy it's a lower bound it's what you definitely have to spend it's not necessarily always attainable so another way of saying the same thing is the entropy expresses the expected number of bits of yes no questions you have to ask that are needed to nail down a random value when the um when what you know about the random value is uh some discrete outcome like it lies in the red interval i hope this gives you some some intuition for why this term makes sense

10:57 in in simple terms it is how often you have to cut things in half before you reach the size of this interval what is the connection with huffman codes this entropy was just the definition that came out of nowhere and there's a theory behind there's it's called shannon entropy because claude shannon introduced this uh well 70 over 70 years ago and it was very successful in in many different fields but the connection to huffman codes is actually very intimate and also long known

11:06 Entropy Formula

11:39 the entropy formula essentially is a guidance to design good codes because if you look at this again this formula is essentially looking like our formula for the expected codeword length for the quality of a prefix free code except that here we had this term stating uh the length of the of the code word we assigned to an outcome and now it's it's this term and it and we say this is uh what we definitely need so um if we could encode the outcome i with log of 1 over p of i p4i bits we would be very happy that's essentially the ideal codeword length unfortunately we cannot really do this in many cases say that this log of 1 over pi works out to be 1.5 how should we assign one and a half bits this sounds um it's definitely not possible to assign a code word of length one and a half bits not if you use um binary encoding but it it is not as weird as it may sound at first you can actually do something like this where you achieve this on average or you achieve this using using different

12:57 elementary units than bits but we will not cover this here and definitely in a huffman code the code words you assign have to be binary strings and they can have one bit or two bits but not 1.5

13:17 so this is this is not generally possible to achieve the entropy with huffman codes but we can at least show something very close to that and the statement here is if we have a an optimal code a huffman code and it's it's expected codeword length then it is it is never better than the entropy this is what i tried to convince you of from from before the entropy is in a sense a much more general lower bound you cannot possibly get by with fewer bits just because you have to learn the information you have to cut down this interval often enough but more importantly huffman codes are also never much worse if you add one to the entropy that's an upper bound for the for the quality of the code that you get from huffman's algorithm and what is the entropy in this case just to be uh be clear because we allow um the weights in in huffman coding are arbitrary they don't necessarily sum to one so you just have to renormalize those divide by the total of all the weights and then you get a probability distribution so there's nothing magic in this in this formula for h is uh just normalizing the weights

14:34 Proof

14:37 let's see how we can prove this and the proof has two parts because we have to prove two statements we have this inequality and this inequality and we will look at the first one first because it's a little simpler because it people have seen this maybe i don't spend too much time on this proof or some people have seen this um it relies on two other results that are simple um simple results from mathematics but i don't want to prove them in detail here but i think the um the main message here is that uh entropy and huffman codes might seem not so much related at first but there is an intimate relationship and that's what is in in this definition we start building a huffman code with certain probabilities so i will i will essentially call this

15:36 p1 and up to p sigma just the the normalized weights give us probabilities we'd like to build a code where we build a code in huffman's algorithm based on these probabilities once we have that code or any code really um we can assign different probabilities

15:57 based on the outcome by based on the codeword lengths and these are essentially given like this so if you take negative powers of 2 so say if if your code is like this let's do a tiny example a b c maybe a is just a one b is zero zero and c is zero one then you would assign a a probability of one half maybe let's add that into the table instead

16:35 well let's write it q c so you would assign one half one quarter and one quarter to these each uh so you might not have had these probabilities when you started but probably something in a sense close to it approximate to it otherwise huffman wouldn't have built this code but you could do this for any prefix free code it doesn't have to have have doesn't have to be a huffman code now uh there's a first inequality crafts inequality it basically just says that if you sum up these qi it's it's at most one and in the way huffman codes are built it's actually equal to one and that one just says if you if you draw the code try for this code let's do that in our tiny example so we have b c and a

17:34 Krafts Inequality

17:38 what kraft's inequality says is suppose each node splits probability in one half to each side then i can always project this onto the unit interval and then every node splits this interval in half and a leaf covers all the range that is at this point so this one covers the entire let's make this a little nicer covers the entire range so a has one half weight in this code similarly if you go one further down then this node splits that here at a at a quarter and then b and c each span this range and so they get one quarter each okay that's a that's a general mapping um how we can assign that's essentially what the qi does and now kraft's inequality says that if i add these up they're at most one and that's obvious because i started with the unit interval and whenever i went down to an internal node i just cut things in half how could i ever have overlaps so that the sums get bigger than one that can never happen if i just split things here with one half one half each okay so that's that's craft's inequality

19:12 uh and if we have any set of numbers between zero and one that sum to at most one we can use the second inequality which is called gibbs inequality and that is basically this um which is true for any um qi in zero one so that uh they sum up to at most one uh that's another another inequality that you can can prove analytically using properties of the logarithm so i don't want to do that here

19:47 Gibbs Inequality

19:51 my message here is if you've shown kraft's inequality you can use gibbs inequality so you can use this middle statement which means you start with the entropy but now you replace p i in the log by this other probability q i or this other number and you get only bigger by doing that intuitively it says if you've built a code for pi with the up with the best possible codeword lengths and you substitute the code built for some different probabilities q i you only get worse that's what gibbs inequality intuitively says and that's of course also how we can interpret it for huffman codes because this here is just the entropy whereas this here is the codeword length for our huffman code or for our code e no matter what code it is so the codeword length for any prefix free code is at least as long as h that's the statement that we can prove here and it's indeed true for any prefix recode e this lower this lower bound it doesn't have to be a huffman code

21:03 Huffman Code

21:07 the second part of the proof is is this upper bound so we now want to show that we can always have at most h plus one as the codeword length in a huffman code this statement needs a huffman code and i'm aware that this looks a little scary but the argument is is not that tough um i just wanted to spell it out on the slides but let's go through this a bit briefly we start with the same trick we define q i's that will correspond to codeword lengths but we don't have a code yet that is convenient for this instead we do something slightly different we take the ideal codeword length so our log

21:53 1 over pi that was the ideal codeword length now we know we cannot usually achieve this because it might be a fractional number so we round up we cannot round down that would be the entropy bound but we can round up and try if we can achieve that and uh the the thing is yes the answer is yes we can do this so we take the ideal chord length round it up and then define a set of q i's as if we had this code already so two to the minus of this rounded up codeword length so all the q i are powers of two negative powers of two can be one half one quarter one eighth one sixteenth and so forth now uh before we continue let's observe that if i sum up this sum p i here but q i there by definition that is just this if you just insert that and notice that the 1 over and the log just cancel the minus and the power 2 to the power then this is the same as this and now because this term is always at most one bigger than the not rounded one you can pull the one out of the sum and then you're left with the entropy okay so that's the first step if we can

23:31 achieve a code that has qi as the induced probabilities we're good or if we have the rounded up ideal codeword lengths we're good and now we will construct such a codeword length

23:52 so again this this here is nothing but log of one over p i rounded up it's just a fancy way of writing it but it's um it's convenient to to use it that way so we construct a code e prime so that all the code words are at most that long and just by renaming the alphabet we can assume that the alphabet is sorted so that the the first character is the least frequent one now we construct this code very similar to how huffman works but with a very slight twist if we just have two symbols in our alphabet then there's not much we can do we can assign the zero bit to one and then one bit two with the other outcome and we observe that then here uh the two probabilities have to be at most one each and almost one half each well the uh the qi don't have to sum to ones i shouldn't call them probabilities but the weights q i or most one half because uh you start with something um the pi are less than one so that means um this one over p i is is bigger than one so log is at least one and if you round up that's at least two and then uh you know uh two to the

25:13 minus two is already one uh to the minus one is already one half so there you go so that part's fine um the code the code word with one bit is uh not too long if we have more than two letters then we do the same step as in huffman we take the two with the least frequency merge them into a super character but now the key step that's different from huffman's algorithm is this we don't assign the sum of the weights we assign twice the bigger weight and uh

25:51 then we recurse and uh compute um based on on the the new weights the rest of the tree okay so the the rest of the construction is the same but why is this um why is this allowed here why can we do this uh if the two weights are actually the same then we're this is just a fancy way of saying we sum up but uh otherwise if the two are different that means that q1 is the unique smallest value in in this collection because things are sorted and it also means because of these powers of two you can actually replace q1 by q2 let's do an example say we have 1 16 then 1 8 maybe i'll just draw it on the line instead

26:49 so here's a half a quarter an 8 a 16. so here's a 16th now um suppose we have a couple of eights like um maybe four things and another

27:17 okay and you notice i already left gaps here because the the thing is if this is our 1 over 16 and it's the only one the next figure is a 1 over 8. so we necessarily have a gap of 1 over 16 because all the other bigger numbers are multiples of 1 8 1 8 because they're powers of negative powers of 2. so there's no way anyone can take up this slack of 1 over 16 but we know that uh these numbers sum to at most one that's from kraft's inequality again

27:57 and uh because the p sum to at most one so because the the queue um it's maybe something uh to note here the q i is sum two at most one so uh there's no way how anyone could eat up this slack so we might as well treat the uh one over sixteen as another 1 over 8. and nothing else really changes now we only make a stronger requirement for this character we want to have it higher in the tree but it turns out this is fine it just works out uh recursively if you

28:34 if you look at what you get from the inductive hypothesis for the super character then it's the same statement with a new weight and that's twice the the big weight that works out as this minus one and um so because q1 is at most q2 that's good enough to bound the codeword length for both of these characters

29:04 so we've constructed this way a code that has the ideal codeword length rounded up it's not the exact ideal codeword length that the entropy has but it's the best the closest you can imagine to get to it if you take every individual code word and just round it up as this proof shows this sometimes even leaves a little bit of slack by rounding every code word up you actually are stricter than necessary it is potentially possible to round some of them down but only some of them um it won't work if you round everything down and you can't really rely on it uh if in the worst case you will have to round everything up um

29:53 well maybe not in the worst case um not sure if you know if you uh if there if you can find an example where you can never round down that seems counterintuitive uh but the construction works if you round everything up and it gives you the bound of h plus one and you can construct examples that come very close to this now the final step that's missing is because huffman constructs an optimal code for given weights it is for the weights pi it can't be worse than the code we just constructed it's one other code for the same characters so we might as well use it but our huffman code is never worse than this code and the lengths of that code we've just found it that each of these codewords is at most that long so i just inserted that into the definition of l and that again is at most h plus one as we've just um shown at the beginning of this proof so in total uh we've proven this second statement as well uh and in a constructive way if you want um we can construct something that is like a huffman code it just is a slight twist in that we add this slack in the weight to make the

31:13 construction cleaner it's not obvious if you actually have to do this and huffman codes will never be worse so you might not care you can always construct your huffman code with the same algorithm and you will obviously you can immediately get the guarantee that it's expected code where length is the most h plus one

31:35 Question

31:40 let's see if you're still with me and i'll ask this little nitty question that asks to relate huffman codes with some fixed length coding i'm i'm not saying what this fixed length encoding looks like uh you're just supposed to compare this in the most general setting you can think of so please have a go at this when is huffman coding more efficient than a fixed length encoding

32:13 and by more efficient i think more precisely i would say more or at least as efficient as a fixed length coding and as always we've had some 23 or so in the first question so i'd love to see at least 20 better 25 people um and the question well youtube claims i only have 20 viewers right now so maybe 20 is already the limit for for today

33:05 but we can do a few more 13 is not quite 20. shall we leave it at oh 17 okay 18. thanks guys good um okay maybe let's uh lock it in now then and here's the results um so people have voted for very different things um i decided to mark these two correct uh in the strictest way of interpreting it first of all if you define more efficient as i said as uh never worse then uh huffman coding is oops i wanted to lock this really uh huffman coding is never worse than any other code in particular a fixed length code so it's always fine to use huffman instead you can never really um pay more in the sense of codeword length the other statement here is also true if you want to have a guarantee that you're strictly improving over a fixed length encoding these statements here are not really enough you need this because uh remember what we've just shown l of e is at most h plus one and it can be very it can be arbitrarily close to that um even though we don't know how h relates in general to log of sigma the the uniform distribution that would be optimal for the fixed length code if this is less than log sigma minus one

35:04 then that eats up the plus one so you would have log sigma and that is the length of your uh fixed code and here we have a strictly less sign so in in this if you can show this then your huffman code is is definitely better than a fixed length code

35:29 Recap

35:31 okay thanks for participating with this um that brings me to the end of the huffman code section uh i just want to recap how the actual encoding algorithm works um

35:45 so uh there's there's two phases of course um there's two uh algorithms of course uh one for encoding and one for decoding encoding is slightly more complicated there's two passes and the first one is we count all the characters in the text in the source text and count how often they occur we need these frequency counts as weights for our huffman code in the previous construction i always said well the weights are given they're part of the input but for encoding you really rely on them to come from the text so you start reading the text and you keep counting all the characters and that's the weights you use for the huffman codes that construction is as you've seen in detail above now for for encoding the source text we actually have to store the huffman code in one way or another there's smarter and less smart ways to do it um i'll i'll skip that part for this module um you can see the you can check the textbook from cetric and wayne

37:01 there's other options that are a little more space efficient potentially so you have to store the code itself and then in the second pass only you use the code to encode all the characters in the source text okay now um you will you will practice this in the tutorials in more detail at least this second pass will omit the encoding of the code but the rest you will you will do to decode you uh first decode the code

37:34 from well using using a fixed encoding of the code you have to decide on this but again we'll skip this so we assume we already have the code red and then you decode bit by bit from the coded text using the code try you just walk down the try and whenever you reach a leaf you can output the next character and that's it as you notice decoding is is much simpler and and also faster to execute and that's not atypical in compression you will see this happening again and again

38:09 so what have we seen about huffman coding the running time to construct the code is is essentially sigma log sigma that comes from the time to sort the characters by weights now if if the weights are smaller numbers you know we can potentially sort faster than this but if the text is very big then the frequency counts will be way bigger than the alphabet size so it's a it's questionable what the complexity is then you have to look at the parameters but sigma log sigma is always possible with a comparison based sorting method then um well you can you can either sort up front or you build the priority queue which is another way of sorting um so you you get the sigma log sigma from the delete min steps and the inserts

39:03 and yeah as an aside there's a different algorithm that doesn't rely on a priority queue if you have the the characters already sorted by weight you can do it in linear time but we'll not discuss the details about this the encoding itself is very fast n is for the number of characters in the text and c is the length of the code so you have to n is the number of characters in the source text i should be explicit so you you read every character in the source text obviously but you also have to write the output so this is this is the best you can hope for there's no way to beat this apart from constant factors

39:47 um huffman codes in isolation might not be a very widespread because well they they tend to have some overheads um coming from the fact that they uh that they have to fix an alphabet and have to fix weights etc but it is a vital component in all sorts of um more advanced coding methods so there's many variations that are in use and you will find it as a building block in many more complicated encoding methods we'll discuss that a bit later in this mod in this unit so again the the good thing is it is a very clean theoretically well understood method it gives you the optimal prefix free code the optimal prefix free character encoding so it's the best possible you can do if you insist on encoding every character by itself it's very fast for decoding a slight downside is this two-pass approach for encoding it means that you cannot use it in a in a streaming mode where you have just data flowing by and you have to process it as it comes the two passes seem to work against this there's hacks in practice to avoid this you can restart after a certain block or you can use adaptive variants so there's a variant of huffman coding that always maintains the best code for the

41:15 prefix scene so far but we'll not discuss these advanced topics and another downside that's hard to overcome is you have to store the code alongside with the coded text and that might lead to expansion it might make the text bigger than what you started with if you're unlucky but remember we'll have to live with this fact there's no free lunch in compression and in many cases huffman does achieve significant compression