Entropy in Compression - Computerphile

Key Takeaways

San Francisco weather why don't you draw us a Golden Gate Bridge I can't draw come on give us a Golden Gate Bridge Lord I don't know like that there I'm running out of space look for the sake of argument we'll say there's only four possibilities it's sunny cloudy rainy or it's foggy and all you got to say is okay what's the probability of these are they equally prob or is one more likely than the other and for the sake of argument let's say that in San Francisco you do get all of these it's amazing every single one in about an equal proportion roughly so let's say it's a quarter and a quarter and a quarter and a quarter and all those of you whove been through High School statistics know if these are probabilities ad them all together it's got to add up to one one is certainty 100% so four quarters is one let's say therefore that here am I in San Francisco and here is my friend in Reno in Reno and we have got an electronic buzzer you know one of those old fashion things that you see in Wartime movies where you tap out a morse code or whatever but this is going to be very very simple at an agreed time in the day I've got to transmit the state of the weather in San Francisco from my weather station to the the guy in Reno as compactly as possible because this is the early days of electronic transmission and each bit cost me $1,000 to send Okay okay so what's the minimum number of bits I need because going to encode it in norts and Wands well you look at this you say well there's four states there equally probable how about something like this 0 0 for sunny 01 for cloud one Zer for rainy and 1 one for foggy four completely separate distinguishable possibilities right right so if it's sunny guy here just goes tap tap two short dots for two zeros and the guy at Reno knows for only $2,000 that it's sunny out the m San Francisco can you do any better than that no you can't you've got four equally probable things there's no way in the world that losslessly you can get better than that yeah however that sounds very defeatist well it is but you ask is there a limit and there is right so long as you want it lossless there is a limit and you can't get below it it's the entropy limit and those who' have done chemistry and physics will know you can't beat it right however if only things were more pred predictable this is not quite true but it's virtually true Sahara Desert I'm not going to ask you to draw a picture for that cuz there no no probability the probability here is one it is always sunny in the Sahara Desert so if I'm got my Sahara Desert key pad here and I've got a transatlantic line to Reno Nevada where they gather all of this data how many bits of information do I need to send to get that message to Reno the answer is if the weather never changes you don't need to send any information at all it's always sunny why ask but if you want to be absolutely sure let's just say send a zero to be sure okay so send a zero if it's sunny send a zero if it's sunny you didn't really need to because it always is that's cost you well probably cost you at least $1,000 to send it again but yeah one bit one bit will be more than ample actually the information um Theory answer is zero bits because if it's certain you don't need to tell anybody this will kill you you can you can edit this out but you do the math ones don't you we we edit nothing out here we I do the MTH ones I do the M okay so what we number five what we remember of course is that one4 is the same as 1 / 2^ 2 which is the same as 2 to the^ - 2 number of bits you need equals probability of it happening Times log of the probability of it happening minus if you take log to the base 2 of 2us 2 the answer is min-2 turn it positive two what the log of that probability is telling you is the number of bits you need minimum so there is so for any piece of information there's a minimum number of bits can be so if one of these was an eigh how many bits would you need to encode if there were all why don't you tell me well right if if there were eight things right yeah then what you could say is that uh 2 to the^ minus 3 is 1/8 so it will be a three bit code are you auditioning for a place on number file here aren you I can tell that's what's happening we've got this minimum for a piece of information is that only on the playing field of the system we use at the moment this zeros and ones I mean is it possible if we you came up with a new way of storing and transmitting information it would be a game changer or is or is zeros and ones you know no if we leaving aside weird Quantum effects who knows what might come out of that as of the real world that we have it this is just it's a it's a showstopper you can't get Beyond this entropy limit when when I was taught about entropy this irreversible sort of minimum that you can get when you do it from the point of view of physics and chemistry they love saying things like this and it sort of works is um you've got a diamond close to absolute zero yeah that is a very low entropy system low entropy means it's Ultra predictable there's the crystal it's vibrating but only just you know where it is it's not moving High entropy is when the probabilities are smeared out you don't know where it is so by the time you get a gas with millions of molecules zooming Here There and Everywhere that's a very mixed random High entropy system now I can see how I take the view that it's a lot easier instead of starting with 10 to the 23 molecules in a gas start with four weather States in San Francisco and you get the idea and then you can transfer it to physics and chemistry Al well in physics and chemistry unfortunately we've got to use natural logs and you've got to take a summation not over four states right but over 10^ the 24 because you see here I definitely can't figure that one out no here you can say average number of bits I need is the sum over all these P log PS so it's a quarter time 2 bits for that one plus a quarter * 2 bits plus A4 * 2 bits plus A4 * 2 two bits wow isn't that amazing the answer is that the average message length is 2 bits but if those were skewed a bit you can kind of instinctively see what you would do if one of these became a half you want to give it a short code right yeah because it because if it so if it was sunny more often I would say well let's make our code for sunny short and some obscure weather like a tornado I'll make a b exact so like if it was a half your theory here would say that's 2 to Theus one hey let's try a one bit code there and let's use two bit codes for the others so you could end up with something if it's like Los Angeles is reputed to be that's smoggy and that's Sunny that's rain that's Cloud what you could then start saying oh well how about devoting the Code Zero to noting smoggy yeah because it's more common because it's more common anybody who's watched World War II movies and people tapping out Morse codes and a lot of people I'm sure will know that the most common letter e has got the shortest code it's a single dot in most code in most code whereas Zed is quite long and so on so it applies you know all the way through this so what you could say therefore is if I'm going to start with a zero for smoggy then I better not confuse use Matters by starting a longer code for any of these with zero right let's start them all with one so let's say something like one Z sunny but then you say well I better not start either of these with one zero otherwise things will get confused so let's start them with one one yeah but the trouble is if I use one one I've then running out of what I can use for cloud can you see it'd have to say 110 and 111 okay because you've got to be able to uniquely decode it and if you're not very careful you will end up with something that can't be uniquely unscrambled suppose to save telephone cost you sent a week's weather all at once seven things one after another how can you uniquely unscramble it into being these yeah it happens with telephone numbers it happens to me at home this this and my telephone number has to have the prefix property I live in a village where my telephone number is a five-digit code unfortunately some people in the village have got six-digit codes yes telephone codes have the prefix property they connect the moment they've been unambiguously satisfied so if you have a legal five digigit telephone code it cannot be the prefix of of a longer code because the telephone exchange goes bang and connects you the moment you've given something sensible yeah okay the trouble then is that the Ardo delivery system doesn't understand this and thinks everybody's got to have six digits so do you know what I do so when you're ordering groceries you deliberately put a wrong number in yes at the very end thinking that's actually a good tip for new players if if someone won't accept your phone number add any digits to theend just add any digits to the end if a weather condition was more common like sunny weather inali you that aor code to save information did the people that invented the jpeg format or do other people that are doing compression use probabilities in the same but do they so do they know that blue is more common in pictures or how do they use no it doesn't quite come down to that it's more in the jpeg standard it's more as it were spatially aware as well as color aware in terms of what it's doing but yeah in one respect or another probabilities is is the root of all of this and like I say that's particularly true if you want lossless compression because you run up against Unstoppable entropy limits about how far you can compress and not lose anything in in the compression well I'm glad it's not my job to compress this video oh God yeah that's Sean's job it's 1880 me gabes and let me say again 80 megabytes not 80 gabes and it's in this huge package start at the bottom we take the pivot everything on the left goes behind it