Alexander V. Markov

Transcription

Hey there trendy 30-something Silicon Valley resident, what you working on? Oh, a new app idea for mobile. That's pretty cool. So you've got your venture capital ready? Good, good. Fancy designer and website? Great. Man, I can't wait to see how your collaborative intelligent algorithm helps users find-- oh, you're not, you're not doing any of that. Oh well, you know I bet you've got a really cool compression algorithm. I mean, reducing your data transfer sizes to third world country-- no? Not doing that either, huh? Well, I mean are you doing anything with data compression? I mean, that's kind of important today. No, nothing huh? Well, hey listen. Don't get down on yourself. Come on, it's not that bad. I mean you can still fix it. All you need to do is take your recipe and sprinkle on a little bit of Markov chains and you'll be compressing data in no time. Well, you know Markov chains. The mathematical system that undergoes transitions from one state to another state on a state space and is generally characterized as memory-less. Such that the state depends only on the current state and not that of the sequence of events preceding it, providing that applications follow statistical models of real world processes. No? Nothing still? You know what? Maybe we should start from the beginning. But fret not, young Silicon Valley hipster. I'm here to help. My name is Colt McAnlis and this is Compressor Head. [THEME MUSIC] Teleprompter activate. [LAUGHTER] Now one of my favorite pastimes is actually taking great American traditions and distilling them into their state graph counterparts. Take example, baseball. Although it may seem like a bunch of random actions to have one team win or the other one lose, there's actually a very simple graph. Let's just look at a batter coming up to base. So the batter comes up to hit here. And there's really only two states. Number one, he can actually be out by hitting the ball or striking out or some other force of it. Or he can actually get on base. Now what the interesting part about this is that once you've move to either the on-base state or the out state, you actually return back and another batter comes up to bat. The cool thing about this is that it's pretty self-explanatory, right? Only three states and a couple transitions between them. Now what if we actually want to transmit some movement through this graph to another individual? Say for example, we have batter up, batter out, up, and then they get on base. Get up again and then another batter out. Well the simplest thing to do that we've been doing so far is assume that each state is a finite symbol. And we can encode each one with about two bits. Which means here we've got one, two, three, four, five six, at two bits per-- means if we want to send this to somebody, it'll be about 12 bits for the entire stream. However when we look at this, there may be a better way to do it. Now what if instead of assigning a variable bit lengths to each of its states, we instead actually assign bit codes to the transition between the states. So for example, we put a zero here, one here, zero here, and a zero here. Effectively, this allows us to encode the transitions between the states very differently, as long as the encoder and decoder know the states and how we're moving between them. Now if you take this set up here, that means that we're actually encoding these green arrows in our state. And this allows us to encode the entire stream in five bits, which is pretty good. But I think we can do better. If you look at our graph here, there's some implicit rules about baseball that we know to be true, that we don't actually have to encode in our graph. For example, when a batter is either out or on base, we know that another batter is going to come up no matter what. So we actually don't need to encode this in our stream. So we can get rid of this and get rid of this. Which means that the only information we really need to encode is whether or not when a better comes up, if they end up out or on base. This information allows us to encode all of our symbol data here in actually only three bits. So moving from 12 bits to 3 bits is actually pretty important. And what we've described here-- the ability to encode transitions rather than the exact states and then having some of the transitions be implicit in the encoder and decoder is actually the basis of how Markov encoding works. But of course, this is a simple example and it gets a little bit more tricky than this. In 1913, A.A. Markov found a new branch of probability theory by combining mathematics and poetry. Effectively delving into the text of an Alexander Pushkin novel, Markov spend hours sifting through patterns of vowels and consonants. And on January 23, 1913 publishers were detailing a statistical model that given a letter, it was a finite and reproducible probability associated with what letter would follow. You see by most accounts, Markov was a pretty meddlesome character, constantly involved with political feuds, public protests. He was fiercely competitive with any rivals in his field and actually spend a lot of time in jail for massive rounds of fisticuffs. How fitting is that the inventor of the algorithm, which is powering most of modern Silicon Valley, was a rebel without a cause. You see, Markov's concept o of probabilistic events selection was massively contrary to the world of statistics at the time, which mostly involves modeling count flipping and dice rolling. You see at its core, Markov chains help us answer questions about associative probability. For example, if it's cloudy today what are the chances that it's going to rain two days from now? A concept, which in 1913, was as predictable with mathematics as casting chicken bones. Think about that. Today Markov chains power some of the biggest and most complex big data algorithms in Silicon Valley. They're seen everywhere from cancer research to weather prediction to modeling consumer behavior and even figuring out what the best pizza joint is in San Jose. The best part is, we can use the same exact base algorithm that powers all these big things and use it for compression. Let's take a look. Channeling Markov's work, we can encode a given string by looking at a letter and noting the transition to the following letter. Now for the sake of simplicity here, I'm going to redraw the symbol pair transitions as a tree with the first letter in each pair resides the head of tree and the second pair resides as the child node. To give us some better terminology in this topic, we denote each pair in the context as a zero based order. That is the first letter of the pairs context zero, well the subsequent letters are context one. Now some of you graph purist may be looking at this graph and asking why T and N don't both point to O node as a child of context one. It is true that for both of these context zero symbols, O does follow as context one. But it's actually wrong to do that. Here's why. To understand why, let's re-encode the string with three simple steps, also known as second-order context. And use your concept of sharing the context one state. Now while this tree may look visually stunning and very pleasing it's actually quite inaccurate with respect to how the string is constructed. You see for example, this graph will allow you to move from T through O in context one, and then to T in context two, introducing the string TOT, which of course doesn't exist in the input data. This is of course an incorrect to the proper thing to do. And the proper thing to do is only chart context transition as unshared links. Now let's extend the concept forward a bit and take a look at a longer string using first-order contexts, that is two symbol pairs. You can see that a more real life example changes our distribution and gives us a different sort of tree for encoding with slightly more complex state relationships, with letters like T, O, and E have multiple potential transitions to the next context. If we wanted to encode this example, we would need some way to assign bits to each of the transitions between the context. The question, of course, is how many bits to assign to a transition, which we can determine as the max number of transitions from a node in the entire set. In this case, the O node in context zero has three transitions, which means we can use 2 bits for everything. Of course, this is a bit wasteful. For example, states with only one transition shouldn't need 2 bits. Plus, we need to keep around some number per node to let the decoder know how many bits to read. And what happens if there's 16 transitions per node instead of just 2? The correct answer here is to use variable length codes to describe transitions. This way, code words used to describe these transition can be variable in size and it can scale based upon what's actually needed. But remember, VLCs only work if you assign the most probable symbol the smallest code word. So in order to get the most efficient compression possible, we need to take probability into account when assigning code words, which thankfully is easy to do given the way we actually construct our chains. Doing so allows us to properly use VLCs to encode our data. And note one of the trickier parts about our scheme is that each context transition-- that is to say zero to each of its children in context one-- manage its own probability table. And as such, has its own VLC set. To be clear, you're not creating a VLC distribution across the entire graph. No, no. That would be madness. Recent years have seen the construction of truly enormous Markov chains. For example, page rank algorithm devised by Larry Page and Sergey Brin, the founders of Google, is based on a Markov chain whose states are the pages of the world wide web, perhaps 40 billion of them. The transitions between the states are actually links between the pages. The aim of the algorithm is to calculate for each page the probability that a reader following a link will randomly arrive at some further page. Now in order to make Markov practical for compression, we need to take a more technical look at the problem. Now when it comes to Markov chains, theory and practical implementations are night and day different. Sadly though this isn't something I can just talk about. No, we're actually going to have to get our hands dirty and encode some things to figure out what's going on. As efficient as Markov is for compression, it comes with one huge flaw. Let's say you want to transmit this encoding to the decoder. Well for each context transition or a parent to child transition, you'll need to store a frequency table-- that is the symbol and its frequency of incurrence. This data, of course, would need to be listed in the compressed streams so the decoder could properly decode this information. But even for this simple example, the overhead of this process is extreme. Just as for all of this frequency data, such that the decoder can properly work, we would need 53 bytes to this stream. The original stream is only 22 bytes, so obviously this is not helping. And it gets even worse the larger our data set is or the more context we decide to keep. The point here is that we can't simply transmit our percentages from the encoder to the decoder using the data stream. Instead we need to make the whole thing work as the decoder will generate the same statistical properties that the encoder is using for the data, as it's decoding the stream. Let's say we wanted to decode this stream, dynamically generate our probabilities, and Markov chain encode it all at the same time. We start out with a completely empty Markov data set. When we read the first letter, A, from the input stream, we need to encode it. But we can't because there's no data so far to use. As such, we need to start creating our tree. Once the trees is created, we need to encode A with a variable length code but we can't yet because we first need to assign it a probability. Since this is the first character we've seen, we can give it a probability of 100%. Once we have our probability, we can generate a Huffman tree, which will let us assign a code word to the symbol A. Since we've got nothing else in the tree, it gets the code word 0. Once we go to read our second letter, B, we also haven't seen it before. So we need to add it as a symbol and its probability to our tree. We also at this point need to update our probability for all the symbols in this context. Note that we've seen a second B, which updates its probability in the table and swaps its code word with A, which is exactly what we wanted since we're updating probabilities dynamically and generating variable length codes based on that. The best part is that we don't need to transmit the probabilities to the stream, just the encoded bits. However when we try to decode this, we run into a large problem, namely that we have no information about the literals or the probability table that was used to construct this bit stream, which basically means the decoder can't actually decode the stream and this is an incorrect encoding. To fix this, we're actually going to have to revisit our encoder and figure out a proper way to output literals so the decoder can consume them and reconstruct the original stream. Once we add A to the tree for the first time, we need some way of providing it to the output encoded stream so that the decoder can get it. To do this, we add a second output stream called the literal stream, which only contains 8 bits per symbol characters that we haven't actually seen yet. We now need to tell the output stream when it should read the explicit symbol from the literal stream, rather than expecting a variable length code. To do this, we introduced the concept of an escape code. An escape code is a special symbol that we're going to use in our probability table that allows the decoder to know when to read a full literal from our literal stream. Now an escape code is not a symbol in the sense that A, B, or C is but it does have residency in our probability table. So it will get a variable length code in the encoding. Rather than starting off with a blank tree, any new context nodes that are instead initialized with an escape code and set to 100% probability. When we read the letter A from the symbol stream, we add it to the context, update our code words, output an escape code to the bit stream, and then the letter A to the literal stream. Reading the letter B is the same process. We haven't seen it before. So we output the code word for an escape code and then a literal value. This is where the fun really starts to happen, kids. Once we read the next B, it's not a new symbol. We've actually seen it before. As such, it's critically important to note that when we're encoding an existing symbol that we output the variable length code before updating our stats and table code words. Once we update the probabilities of the table with the second B, the weights change the code word assignment. As such, the decoder wouldn't be able to see this type of change and it would break things. Decoding works the exact same way. Except when we encounter an escape code, it tells us to go read a symbol off the literal stream and output it. First we employ the process of reading variable length code from the bit stream. If you're not familiar with that, go check out Episode One. Since the only value we have is an escape code, we simply need to read a single bit from the stream and find that we're using an escape code. This tells us to go ahead and read 8 bits from the literal stream, push it to the output stream, and update our probability tables. We read the next zero from the bit stream and seeing that it's a variable length code as well, we know to read the next literal, output it, and update the probability tables. At this point, we have enough table information that the next 2 bits read off the bit stream match with the letter B, which of course we happily output. We've read A from the input stream and realized it's in the table. We've output our codes to the output bit stream and updated our probabilities. But because we're supporting context we need to actually create a new branch in the tree. In the naive solution, each symbol at each context level would contain a pointer to its children in the next context. But in order to make things work right, we have to start all subsequent context with an escape code. So the good news is that's the basics. However, the bad news is that we actually need to support a multi-context chain in order to get proper and legitimate compression. And in order to support that, we're going to revisit the encoder again and change how a few things work. Since we've just seen a new symbol at this context level that we haven't seen before, we need to start our chain back over again at context zero. Each time we read a symbol in context zero that already exists in the context, we move forward to read the next symbol operating in the subsequent context. So if the first two symbols were A, C, we would find the letter A and then add C to the first-order context set for encoding. And to be clear we treat a new symbol at any context as a completely new symbol. So if we encounter the series A, B, C in this encoding it's the first time that we've seen the letter C in context to following B. So we treat it the same way as we would with context zero by outputting it to the literal stream and emitting an escape code. Once this is entirely encoded, we take our final bit stream and literal stream and pass it along to whatever person on the internet wants it, without having to keep a single probability table around at all. In this solution the original stream was 88 bits while the encoded stream is only 46 bits, almost 50% reduction which isn't bad. So it should be really obvious at this point that efficient encoding of Markov chains has to strike a unique balance between the length of the chains that you need for compression and the available memory that you have on the system itself that you're running the encoder on. If you run out of memory early then it's not necessarily a good thing. A real encoder strike this balance with all separate profiles of system analysis memory and also writing additional context to disk to find the optimal solution. Now hopefully one of the questions you're asking yourself here is how do we properly adjusted the probability of an escape code when new symbols are added? In our little examples we did here, we simply subtracted hundredth of a point from it. But in reality it's not that simple. Unfortunately that's an entirely separate show that we're not going to cover today. In the mean time, Google it. Now some people view Markov chains as a step in an inevitable future where artificial intelligence algorithms run the entire gamut of data compression. And that's pretty easy to see. You see, keeping a multi-level context is much like tuning a neural network algorithm for artificial intelligence. Of course, we know by now those most successful Markov chains are actually terabytes of relational data long with thousands of context in two. Now lighter weight versions of Markov chains are already available today in modern compressors like 7-zip L pack and ZPack. It's easy to see a future down the road where artificial intelligence and cloud computing come together in some weird hybrid to create a revolution of data compression that we haven't seen it over 40 years. But that is a topic for a different show. My name is Colt McAnlis and this is Compressor Head. [THEME MUSIC]