Typical Decoding for Natural Language Generation (Get more human-like outputs from language models!)
#deeplearning #nlp #sampling

Modern language models like T5 or GPT-3 achieve remarkably low perplexities on both training and validation data, yet when sampling from their output distributions, the generated text often seems dull and uninteresting. Various workarounds have been proposed, such as top-k sampling and nucleus sampling, but while these manage to somewhat improve the generated samples, they are hacky and unfounded. This paper introduces typical sampling, a new decoding method that is principled, effective, and can be implemented efficiently. Typical sampling turns away from sampling purely based on likelihood and explicitly finds a trade-off between generating high-probability samples and generating high-information samples. The paper connects typical sampling to psycholinguistic theories on human speech generation, and shows experimentally that typical sampling achieves much more diverse and interesting results than any of the current methods.

Sponsor: Fully Connected by Weights & Biases
https://wandb.ai/fully-connected

OUTLINE:
0:00 - Intro
1:50 - Sponsor: Fully Connected by Weights & Biases
4:10 - Paper Overview
7:40 - What's the problem with sampling?
11:45 - Beam Search: The good and the bad
14:10 - Top-k and Nucleus Sampling
16:20 - Why the most likely things might not be the best
21:30 - The expected information content of the next word
25:00 - How to trade off information and likelihood
31:25 - Connections to information theory and psycholinguistics
36:40 - Introducing Typical Sampling
43:00 - Experimental Evaluation
44:40 - My thoughts on this paper

Paper: https://arxiv.org/abs/2202.00666
Code: https://github.com/cimeister/typical-sampling/blob/3e676cfd88fa2e6a24f2bdc6f9f07fddb87827c2/src/transformers/generation_logits_process.py#L242-L272

Abstract:
Despite achieving incredibly low perplexities on myriad natural language corpora, today's language models still often underperform when used to generate text. This dichotomy has puzzled the language generation community for the last few years. In this work, we posit that the abstraction of natural language as a communication channel (à la Shannon, 1948) can provide new insights into the behaviors of probabilistic language generators, e.g., why high-probability texts can be dull or repetitive. Humans use language as a means of communicating information, and do so in a simultaneously efficient and error-minimizing manner; they choose each word in a string with this (perhaps subconscious) goal in mind. We propose that generation from probabilistic models should mimic this behavior. Rather than always choosing words from the high-probability region of the distribution--which have a low Shannon information content--we sample from the set of words with information content close to the conditional entropy of our model, i.e., close to the expected information content. This decision criterion can be realized through a simple and efficient implementation, which we call typical sampling. Automatic and human evaluations show that, in comparison to nucleus and top-k sampling, typical sampling offers competitive performance in terms of quality while consistently reducing the number of degenerate repetitions.

Authors: Clara Meister, Tiago Pimentel, Gian Wiher, Ryan Cotterell

Links:
Merch: http://store.ykilcher.com
TabNine Code Completion (Referral): http://bit.ly/tabnine-yannick
YouTube: https://www.youtube.com/c/yannickilcher
Twitter: https://twitter.com/ykilcher
Discord: https://ykilcher.com/discord
BitChute: https://www.bitchute.com/channel/yannic-kilcher
LinkedIn: https://www.linkedin.com/in/ykilcher
BiliBili: https://space.bilibili.com/2017636191

If you want to support me, the best thing to do is to share out the content :)

If you want to support me financially (completely optional and voluntary, but a lot of people have asked for this):
SubscribeStar: https://www.subscribestar.com/yannickilcher
Patreon: https://www.patreon.com/yannickilcher
Bitcoin (BTC): bc1q49lsw3q325tr58ygf8sudx2dqfguclvngvy2cq
Ethereum (ETH): 0x7ad3513E3B8f66799f507Aa7874b1B0eBC7F85e2
Litecoin (LTC): LQW2TRyKYetVC8WjFkhpPhtpbDM4Vw7r9m
Monero (XMR): 4ACL8AGrEo5hAir8A9CeVrW8pEauWvnp1WnSDZxW7tziCDLhZAGsgzhRQABDnFy8yuM9fWJDviJPHKRjV4FWt19CJZN9D4n
 Pay special attention to this paper. It is not a paper by Google or DeepMind or Meta or anything like this, yet I believe it is a really important paper. It discusses typical sampling, which is a new decoding strategy of how we sample from language models. We usually train language models with a maximum likelihood objective that put a lot of weight on very likely words. And when we use these models to produce language, we either explicitly or implicitly reproduce that we make these models sample very highly likely strings, which are boring and not human like, it's not what we do. I don't say things that are just highly likely, because I actually want to say something interesting. And that means that every now and then, I should utter something that's less likely, I should speak a word or a sentence that you didn't expect, because that's what transmits information. Typical sampling does exactly that and does it in a principled fashion. This video right here is a description, a review of the paper. And the next video is going to be an interview with Clara Meister, the first author of the paper. Both videos, but especially the interview, are super duper interesting. I would definitely invite you to check them both out. And I would definitely invite you to try out typical sampling. It is in hogging phase. And whenever your objective is to sample something that is very high quality, but also diverse and interesting, and not just bland high likelihood text, then that is your method for you. I believe that we do need new sampling strategies. And this one is very promising. Check it out, leave a like and see ya. Hi, let me quickly tell you about Fully Connected, which is curated space for the Applied ML community. It features articles, project reports, news events, and anything you could want, especially the projects page acts as a little bit of a product hunt for ML. So feel free to add your own project right here. It's curated by Weights and Biases, but I know what you're thinking. Yeah, another company, blog, whatever about their products. But this is not at all about Weights and Biases. It features some of their stuff, of course, but it is generally a really good resource to get good information on what's currently happening in deep learning. They have great articles and tutorials, like there's one on solving Wordle with reinforcement learning, which is pretty cool. There's one explaining group normalization in PyTorch. And there's one that explains to you how to run YOLOv5 object detection on Windows. So as you can see, they have all kinds of stuff. And the list of already existing articles is long. If you still don't believe me that it's not all Weights and Biases, in fact, you can submit a post there, you can click the button, write a post, it will be reviewed by them and then published. So one of the coolest ML startups currently is going to push your content. How great is that? Now, if you are just a lurker like me, then you know, head over there and subscribe because it's user submitted but curated so you get the best of both worlds. Besides articles, they also have events, which usually means their webinars about various topics, you can look at old webinars, but you can also subscribe to get updates on new ones. They also host their podcast, their gradient descent. And the current episode is actually with Jensen Huang, the CEO of Nvidia. So pretty big hitter. And lastly, it includes the good old Weights and Biases community forums where you can get all kinds of help on Weights and Biases products and beyond Weights and Biases to all kinds of things machine learning related. So again, fully connected, it just got a major redesign. Please check it out. Go over there, subscribe for awesome articles and news. There's new stuff all the time. Thank you so much to Weights and Biases for sponsoring this video. They've been a great sponsor. So please check them out. That's one db.ai slash fully dash connected. Now let's get into the video. See ya. Hello there today we'll look at typical decoding for natural language generation by Clara Meister, Tiago Pimentel, john Weaver and Ryan Cotterall. This paper suggests a new way of decoding of producing text from a large language model or a small language model. It doesn't matter. We don't discriminate here. In any case, usually currently you might have heard of things like beam search, you might have heard of things like nuclear sampling and top case sampling. These things are all right. And interestingly enough, the stochastic methods like nucleus and top case sampling are better than the methods that try to find the most likely things such as beam search or greedy decoding. However, it's still not satisfactory large language and small language models. They often produce text that is boring, just kind of bland when you actually use them, even though they have amazing perplexities on text. This paper tackles this. It proposes that when humans generate text, they don't just produce the most likely text, they will actually trade off likelihood with information content or the transmission of information to another human. And that trade off can be captured in the frameworks of information theory. And we can generate or we can suppose a decoding scheme, which they call typical decoding, typical sampling, which exactly encapsulates that notion of balancing interestingness or information with likelihood. And when they test it, that actually results in better results. This could be really crucial because it doesn't require any change to how we train language models. In fact, we can take off the shelf trained language models and simply use this new decoding strategy out of the box. And it applies across, you know, across domains. Now I have long said that we need that probably our decoding methods, our sampling methods may be inadequate depending on what we do with those language models. For example, alpha code samples a whole bunch of programs in order to solve a problem. Now we, again, we don't like there is value in diversity if you sample a whole bunch, and then after that use like a filter to narrow it down. So I think depending on what you want to do, maximum likelihood sampling is very appropriate. This paper, for example, mentions natural or machine translation, because in machine translation, you really want kind of the best translation for a given input. However, in other frameworks, such as alpha code, but also such as storytelling, this paper mentions summarization maybe as well, you want to, we want to trade off some of this maximum likelihood for some more diversity or for some more interestingness or for some more information content. And that's what this paper does. So we'll dive into it. If you like content like this, as always, leave a like, and don't be shy to let me know in the comments what you think. I'm not exactly I'm not entirely sold on what this paper does. I do agree we need better or we need a different decoding strategies. But I do have my, you know, reservations about this exact one. So let's dive into the paper. The paper first complains about the exact thing I complain about, namely saying that language models currently they have extremely low perplexities on on corpora for many domains, yet when used to generate text, their performance is far from perfect. And by that they mean, yeah, they they produce text that is undesirable, eg, generic or degenerate weight. Yes. So either generic or degenerate, or just as we said, boring, bland, you know, and that comes from the fact that a lot of these things, they try to find the maximal probability string. So they think, you know, I'm going to sample from the probability distribution, and I want to sample what is the most likely because that's how we train these models, right? So let's do a short excursion. If you are unaware of how language models are trained, they're usually trained. You have a sentence like the cat is in something the house. And it goes on. So what you can do is you input a part of the text, and then you let the model predict the next token, and then you input that part, and you let the model predict the next token. Now, in training, this is all good and fine. But at inference time, what you do is you provide a prefix, for example, the cat. And then you have to decode here, you have to decode a word, what's next, and then you feed that whatever you decoded into the language model, and you decode the next word. And I think that's where part of the problem comes from. Because during training, naturally, what is here is given by the data set. So every new step that you take, if there is something unlikely, if there is a certain diversity to the input, that's captured by the training data. However, in decoding, you sort of make your own data as you go along here. And if you just always focus on finding very likely next tokens, you'll never get into kind of a less likely environment, which could also be correct, right? So that is one of the problems. However, obviously, in these language models, the way they work is, for example, you input all of this into a big model, there is a little bit of a big model, there is some sort of a model, which usually is a transformer nowadays, and out comes a probability distribution. And the probability distribution is over your vocabulary. For example, there is the vocabulary, this cat, dog. I don't know another word. What's another word? House, something like this. And it will give you a distribution of probabilities over these words. And you can now choose what to do. Either you can take the maximum one, which often runs into these problems of being boring or even repetitive, you can take you can sample from this distribution, which is also not super appropriate, because, and the paper touches on this a little bit, because sometimes the long, what's called the long tail here, there are many, many words, of course, and they all have their some probability. And you don't want to get into these super low probability words, because they might just be artifacts of the model. The model doesn't represent these low probabilities really well. It's really good at the sort of high probability words, because, well, it's essentially trained as a classifier. And the classifier is trained to give you the correct label as the highest class. And it doesn't really care about the rest of the words, especially not the ones that have really low probability. So what people do is they came up with, first of all, Beam search, what beam search does is it considers multiple futures. So if it's here, that cat, like that cat, it considers multiple futures, and it looks a few steps ahead. So it looks a few steps ahead, and it keeps a list of things that are possible to complete. So for example, in the beginning, it goes all these three routes, and it keeps those in mind, along with the probabilities that you go along that tree. And then, you know, you go ahead, and maybe the buffer is five large, right? So now we can still fit it because there's one, two, three, four, five paths currently, but as soon as we expand the sixth one, this one here, we have to drop someone. So we consider all the paths, and we consider only the ones with the highest likelihood so far, this we can simply do by multiplying the probabilities of consecutive decoding steps, we consider the most likely five, let's say, paths so far, and we delete some of them. Let's say that this one here is really low probability. And then once we add this one here, and this one, we have to drop another few, so let's say this one, these two here are really low probability, and so on. And we only continue the paths that have good probabilities, or high enough probabilities to be the highest possible. That's beam search. And the reason why people do it is because there might, so there might be a very high likelihood sentence that you could produce, but the next word just happens to be low in probability, right? Maybe here, house will lead to a sentence that down the road is very likely, has a very good score, but just this word right now, in this case, is low probability, because the immediate best word would be dog for all the possible continuations, or for this particular prefix, for all the possible expected continuations. So beam search is a very, very, very, very high probability. So beam search is even worse than greedy decoding in the sense that it really finds the high probability stuff. It doesn't, and it looks ahead to be even more accurate. If you go to the opposite end of the spectrum, you can say, okay, can we sample, but can we fix the sampling issues that arise from this tail? And that's why people do two things. So there's top K, sampling, and there is nuclear sampling, and they both work pretty much the same. So top K, sampling, what it does is you have, again, your probability distribution, and top K sampling simply says, well, can we only consider the K largest entries in that distribution, and then just sample from that? So let's say K equals three, then we only consider the three largest entries here, and we just forget about the rest, and we only sample from that. We have to renormalize, but that's fine. And then nucleus sampling is very much the same, except it says, well, I'm going to afford myself a probability, a cumulative probability of, let's say, 0.7. What does it mean? It means that this distribution right now has a cumulative probability of one. I am simply going to take the largest ones, like, okay, this one, and this one, and this one, until the cumulative probability reaches my maximum threshold. Maybe I'm going to take this one as well. You can see the advantage here is that you don't always pick the same amount, but you always pick sort of the top entries that make up, let's say, in this case, 70% of the mass. And that is useful because you have to consider multiple scenarios. One scenario is where the distribution is very peaky, like, there, you only want to consider very few entries. So you only want to consider few entries because everything else is just really unlikely. However, if you think of a distribution that is more spread out, like this one, and then you want to consider more entries, because all of them are kind of likely, and nucleus sampling affords you that, whereas top case sampling would just disregard the shape of the distribution and pick the top ones. Right, so these are the decoding strategies, but still, you can see they always go to the top or the most likely things. And this paper says, well, that's kind of dumb. And it shapes this as a information theoretic problem. We already said that humans probably want to trade off the likelihood of a string. So like how likely it is to appear, meaning essentially how much it is expected, because if I just say things that other humans expect, right, then I'm essentially not transmitting much information at all. So we can say that every string has a form or a content of information. Actually, I'm going to skip here, skip here to the theory section directly. And forgive me, I've pretty much explained all of what's highlighted already. So what we can say is that a why, why is the message that you want to pass? So let's say it's a sentence, the information content can be quantified as its negative log probability. Essentially, the less likely a given message is, you can see here that's negative, negative log probability, the less likely a message is, the more information it carries. You have to think of it like exactly as I said, if I say something that's very likely, the other person could have expected it because it's so likely. It's like if you meet the stereotypical boring person, or if you see a movie where it's like a really stereotype of a boring person, they will always say exactly what you know what you'd expect them to say. However, if you say, let's say you communicate with someone, and they all of a sudden say something that you really didn't expect. Now that's a lot of information right there. In fact, you can buy simple application of the chain rule, you can see you can also define a information content for every single word in the sentence. And that is going to be just the conditional log probability, the log conditional probability of that word, given the prefix, and that's the prefix, those are the previous words in the sentence. So akin to the information in a sentence, a word carries a lot of information, if you really didn't expect to see that word as the next word in the current sentence that you begun or that your conversation partner has begun to say. So we carry this through. And the assumption here is that the goal of an agent is to transmit information efficiently, while also minimizing the risk of miscommunication. So that's the fundamental trade off that humans do when they communicate, at least that's the hypothesis. If you transmit a lot of information, you're going to have to utter some words that are very not likely, because that transmits a lot of information. However, if you overdo that, and if you, for example, don't follow the rules of grammar anymore, and just send around low information messages or high information, low likely messages, your receiver will be confused, because they don't know what to make of it, because they really didn't expect to see something like this. And therefore, there is a chance of miscommunication. You can also, you can imagine that if you want to transmit a message to someone, right, if you want to explain something to someone, you always have to adjust to what they already know. Like if I want to explain the chain rule to someone, and I expect them to already know a little bit of math, I'm going to transmit a lot, I'm going to have to adjust my message to that. And if I assume too much of what they already know, and then I'll just end up saying something like, oh, yeah, if you derive f of, you know, of g of x, with respect to x, then you have to, you know, you just derive g and then you kind of multiply by the derivation of f. And it's all good, right? It's all good. So sorry for this butchering of the chain rule. But you can imagine that someone who has little grasp of math in the first place would be very, very hard. Because I only utter the words that carry so much information that are so not likely in their framework, that there's a chance of miscommunication. I don't know if actually that captures it the best, maybe there's a better example. That's sort of how I think of it. What they do define, and now we get into the decoding strategy is the expected information, the expected information that a specific symbol in the message will contain. So this formula right here, you might recognize as the conditional entropy of a given word in the sentence, namely, and this, I think the notation here is a bit out of place. I think this should be something like the expectation of the information content of just that t-th word, not necessarily y of t, because y of t, we sum over y of t right here. So yeah, but so we ask ourselves, if we have already produced the sentence up to time step t, and we consider the distribution of words conditioned on this sentence, so we ask our language model, what's the distribution of words that could come next? And we ask ourselves for each of these one, what's the information content? And since we have the information content is the negative log probability, that's this, and here is the minus sign, we ask ourselves, so what is the expected information content of the next word, you know, whatever the next word is, what's the expectation of its information content, if we were to just sample from this probability distribution, and then this here is the formula, right, we simply multiply whatever we're interested in, which is the information content with the probability, and we sum that up across the set that we're interested in. That is, it's just the definition of the expected value. And by happenstance, it is also the definition of the entropy or the conditional entropy. So the expected information content of any given position in a sentence is the entropy of is the conditional entropy of the distribution at that point. So what does that mean? That means if my distribution is very peaked, so if it's very likely that one of these three words here is uttered next is, so if I find a text somewhere, right, and the sentence up to here was something, and then there's only like three words that could potentially be there, none else, it's very peak to distribution, that essentially means the entropy is very, very low. And therefore, the information content of that of whatever word comes next is probably going to be very low, because all these words are super likely. However, if the distribution is very shallow, or very broad, then the entropy is high. And you can also see, since any of the words that could come next, first of all, there are many more that could be considered, and all of them have less of a likelihood. Therefore, the negative log probability will be higher. So any of those words will have more information content, and especially the expectation over those words, it will the information content will be higher. So that is just the definition of the expected information content. Now, here's the hypothesis of this paper, and they base this on some psychologists, psychology theories, or linguistic theories. But here's the hypothesis. Any given word should have an information content close to the expected information content, i.e. the conditional entropy given prior context. In other words, we expect the difference between the expected information content and the true information content to be small in human-like text. So the hypothesis here is that the way humans balance this trade-off between interestingness and likelihood, and so in between information transmission and not being misunderstood, is that they implicitly calculate the expected information content of the next word, and then they try to choose the next word in accordance so that it is as close as possible to that expected information content. So when I talk, I model sort of the transmission channel to my receiver, and I figure out, okay, in the language right now, what would be the expected information content of the next word, and then I try to match that as closely as possible. And that gives me a way of determining this trade-off. Again, this is a hypothesis. It's backed up by a few theories from linguistics. This is also known in information theory as typicality. So a typical message is one that has the information content that is close to the expected information content, but we'll investigate. So they say figure one shows for human-generated text, the distribution of this epsilon. So this epsilon is the distance between these two quantities, the expectation and the actual thing that's uttered. Remember, the expectation considers all possible next words and calculates the expected information content of them. And then this thing right here, this thing is just the information content of the next word that is actually uttered or actually written. So what would we actually do? We would actually analyze the human-generated text. So what would we expect this or what do we see if we analyze human-generated text? And these here, these are obviously language models that estimate the probabilities of these words, but these are evaluated on human-generated text, so not on language model-generated text, because remember, this paper is all about how do we do that in the human-generated text. So let's take a look at what humans do, and you can see the distribution is very peaked. Now, this isn't the distribution of words, this is the distribution of this epsilon. So that essentially means this distance, this difference right here is very, very peaky, and it's peaky around a very small value. You can see here the scale goes from whatever, and the peak is at a value that's quite close to zero. Now, it's not exactly zero, but this is empirical data. So this paper says this is evidence for the fact that humans do, as much as they can, try to match the information content to the expected information content. Now, it'd be interesting to see what you would actually, let's say humans would just sample from the distribution itself, right? What kind of distance between the entropy and the information content would you expect to see? Maybe a Gaussian or a log Gaussian? I'm not entirely sure. Also, what is peaky? How do you characterize peaky? I can see peaky, but it's proof by picture, almost. And then we see a very interesting imbalance, namely, there seems to be sort of a mass going higher up, always on the left side of this, rather than on the right side. There seems to be a bit of a longer tail on the right side, but a bit more heavy mass on the left side. Now, what does that mean? This is, well, I can't really make sense of it, because the epsilon is characterized as an absolute value, whereas this right here is not an absolute value. And so I'm going to guess they left away the absolute value. Therefore, I don't know which, I don't know the distribution of the deviation of information content from the conditional entropy per token. Okay. Again, I do not know what came first, if they do h minus i, or if they do i minus h. And that determines how we interpret these plots. So I'd rather not interpret them in the wrong way right here. They further, so that's what they say, the peaked nature of the distribution reveals that humans indeed tend to form language with per word information content quite close to their expected information content. And the centering of these distributions around the value close to zero reveals that our probabilistic language generators are learning what this rate is. Well, I'm not sure I agree with that statement, because being peaked doesn't mean, doesn't mean, like you need both to be true at the same time. If you assume that the language models are really good at what they do, then you can claim that humans peak around zero and therefore they match the expected information content. If you assume that humans match the expected information content, then you can conclude that language models are really good at what they do, because the peak seems to be rather around zero. But you can't draw both conclusions at the same time from this plot, because you need one to justify the other. In any case, this is a minor point. What is interesting is that here, they go into information theory, as I said, this notion of typicality, which is exactly what we're describing right here. They say, it says typical messages are the ones that we would expect from its probability distribution. Their average per symbol information content is close to the entropy rate of their source distribution. Now, the interesting observation right here is that the definition implies that the highest probability message is often not a member of this set. Its average information content is too low. So if we consider any distribution and we consider what's the expected information content, which is the way we defined it, and we only consider messages, let's say these are the messages, we only consider messages that are close to that expected information content. But those are going to be messages that are kind of somewhere in the middle of the likelihood. So they're not super duper unlikely, because the expected information content is again the expectation over all of these messages, which is going to be not super duper high, which rules out these unlikely messages. These are prone to misunderstanding, but it also rules out the very likely messages, because those are going to be prone to being boring and not transmitting any information at all. And that is something interesting. That is exactly the property we want in a new decoding method, leave away the really low likelihood stuff and leave away the really high likelihood stuff, because that's boring. Yeah, tip, the typicality is a property. Okay, now they go into why we can't, why we have to go for a local, a local notion of typicality, whereas information theory usually defines it as a property of the of the entire sentence or of the entire message, don't necessarily want to go into that. The next chapter, they try to justify this with psycholinguistic concepts. There are two they consider. There's the uniform information density hypothesis, which proposes that speakers construct their utterances such that information is distributed uniformly across them. And the the the speakers choose words such that their information count, their information rate is closer to a target channel capacity, which is essentially what we're doing right here. Then there's the rational speech act, and the rational speech act, sort of, it casts the speaker's behavior as the maximization of a utility function. And the utility function is a set of sentences usefulness to its listener. So the way it constructs this, again, this is sort of hypothesis, it imagines this literal speaker. So this is a hypothetical speaker that just samples from the probability distribution, it just looks at the probability distribution, and just samples from that. And it just orders the words as, you know, as they come out. And that means, you know, with the typical problems like, it's going to utter the words, it's going to use the words, it's going to utter kind of low, low information stuff a lot of the times. Then it says, well, a smart, the pragmatic speaker, and that's what the humans would be at the pragmatic speaker produces sentences to maximize the utility function, as opposed to following its expected literal behavior. If you define the utility function to be this thing right here, then the hypothesis kind of matches, the hypothesis matches the this rational speech act. However, I find this also to be a little bit shady, because if I have a different decoding method in mind, I can apply the same argument, I can simply say, well, my, my utility function is now my new decoding method. So, yeah, I'm not super convinced by this. However, it's interesting to see that people think in this way that they say, well, there is going to be this literal imaginary agent that just speaks according to the distribution. And then there is the upgraded version of that. And probably the humans are a form of an upgraded version, this pragmatic speaker that changes something that sort of uses this distribution, but changes something about it. And that's exactly what we do. So how do we do it? And we've already alluded to most of it. So what we do is we introduce this typical sampling. Much like nucleus sampling, we define a threshold, in this case, this is called tau of probability mass that we're going to allow in our in our subset of words. So again, maybe we have a distribution of a couple of words, and they have different likelihoods under our language model output. And we assume our language model output models these probabilities, especially the non negligible ones. Well, then what we're going to do is we're going to calculate the expected information content, which is the expected negative log probability, which is also the conditional entropy. So we're going to estimate this property by simply calculating it. We can do this. This is simply again, this is p of x given y times log p of x given y. The log probability is usually already output by our model in the form of logits. We just need to normalize it. And if we apply some sort of a softmax operation, we get the p of x given y. So then we have the conditional entropy, and then we simply choose the words that are most close to this. So maybe the expected the entropy, let's say this is the let's say these are the log probabilities right here. Let's say the expected one is here, we simply choose in order the words that are most close to that one. So it would be this one right here. This is really close. Then this one is really close. Then what's a tough choice, maybe this one's really close. And then maybe this one's really close. And that we do that until again, we reach our target probability mass. Again, if the distribution is very peaked, so if the distribution is very peaked, that means the the typical information content is going to be lower, which means the words that have low information are going to be chosen more, which and these are also going to be less words. And that gives us our original case back where we're simply going to choose the highest likelihood words into our bucket to sample from. Yeah. And and that sort of regresses to the old case, if the distribution is very peaky. However, if the distribution is flatter or more broadly more broad support, then we the expected information content is going to be lower, which means that probably these highest likelihood ones are not going to be in it. And we opt for more interesting ones that are also likely, but not as likely. So this kicks in mostly when there's a lot of possibilities, which you can see in let's say machine translation, there is not in machine translation is often very clear or there's only a few possibilities on how there's only a few possibilities on how to translate something. However, in storytelling, there's lots of possibilities how things could continue. And there are distribution are much more shallow. And this method would exploit that by saying, well, I'm just not going to consider the most likely things right here. The computational complexity is the same as nucleus or top case sampling, we also have to determine the set we're going to consider by somehow calculating across it, we have to aggregate it, we have to renormalize it, and we have to sample from it, except here, well, I guess we always have to sort right. Yeah, here we also have to calculate this conditional entropy part, it's the same in complexity, but it does add a constant overhead or like a multiplicative constant factor overhead to the whole thing. So the last thing I want to go in here is the choice of hyper parameters in this one. They say we found k equals 30, and n equals point nine to perform best. So these parameters perform best for top k and nucleus sampling respectively. So this is for their experiments. So one is for top case sampling, and one is for nucleus sampling. For typical sampling, we found the tau equals point two and tau equals point nine five to provide the best results for story generation and abstractive summarization respectively. So while they allow for a single parameter for each of the baselines, they go with a separate parameter for different tasks for their method, which is a bit shady. Now, there's two possibilities. First possibility is they sort of stifled the baseline by only sort of giving it not exploring well enough the possibilities, or what I think happened most likely is that the same parameter performs pretty well for all the different tasks, which is a good property in itself right here. Here we consider 20% of the probability mass, and here we consider 95% of the probability mass. Now that's a huge difference in how our set looks. And that by itself makes it, in my opinion, a bit of a weaker choice for using this as a decoding method, because for every thing that I want to achieve, I need to essentially tune this parameter, whereas with top case sampling, I could just leave it be. So it'd be interesting to see if in the future there might be, because I'm a fan of this technique in principle. So maybe in the future, we can find more of an adaptive way, much like nucleus sampling is an adaptive way of top case sampling, maybe we can come up with an adaptive way of determining the number here or the parameter of how many things to consider. So I don't want to go too much into the evaluation. There is a difference. Sometimes it's stark, sometimes it's not as stark. It is different in different regimes. You can see that depending on the regime that you are at, it's sometimes the different methods are really different. Sometimes they're quite close, sometimes they switch places. Yeah, that's, I don't want to go too much into the results because we can maybe discuss them in an interview. But qualitatively, say for example, for the summarization task, we see that typical sampling provides a comprehensive and coherent summary of the article under consideration. In comparison, nucleus sampling leads to hallucinated facts, for example, getting drugs from under, okay, I haven't read the article, but nucleus sampling hallucinate facts, which is one property. If you sample only from high likelihood things, right, you're just going to continue with things that are very likely in the language itself, rather than transmitting the necessary information. While top case sampling misses some of the important information in the article, e.g. the charges of burglary and arson. And that might be because top case sampling simply has this fixed bucket of words to consider. And as soon as one word is not in that bucket, it simply is forbidden from uttering it, even if the distribution is shallow and that word is kind of likely. So I want to stop here and just give a few thoughts on this. In my opinion, I already said it is quite needed that we have different decoding strategies to achieve different tasks. This one right here, it seems really interesting. It is a way to trade off sort of not considering the most likely things, but also not considering the least likely things. However, I'm not sure if the notion of the matching the expected information content is appropriate. I can't tell. It's a good hypothesis. I don't know if this quantity here, the absolute distance is a good quantity. Like, why would it be the absolute distance? And the other issue I have right here, but this might be my ignorance of information theory is. So if I change, let's if I assume the humans talk like this, they choose their words according to the expected information content, right? And I use this particular construction right here. That is going to everything that comes out of this. Whatever comes out of this will have a different expected information content than the original language. If I wanted to actually match, like if I wanted to keep the expectation, I probably couldn't do this just in absolute difference. That's probably going to change the expected information content, let alone the distribution of it itself. But just the expectation is going to change. Now, if you're telling me that humans do it like this, and that our language models are trained on text that is written and uttered by humans, like wouldn't that text already have that property and therefore sampling from it would be the original distribution? Or in other words, if I produce text like this, like, shouldn't I get the same, shouldn't I get the same distribution out that my language model predicts, because my language model is trained on human text, and your claim is that humans sample text like this. So why would that be any different from sampling from the language model itself? And especially, shouldn't it be that the expected information content remains constant if I apply this sampling technique? Just out of principle, because by definition, if it doesn't, then it doesn't match human generated text, because that's already the input. That's the training data. All right, but maybe I'm sort of ignorant of information theory right here. Yeah, my other concerns are with the hyperparameter choice. And yeah, I'd be interested to dive a little bit more into this, like what would we expect to see with the different sampling methods or with different hypotheses? This is also really interesting, but I'm going to leave it at that. All I can say is that we should probably try this out. And maybe, you know, for certain tasks where diversity and actually transmitting information is more important than being, you know, uttering the most likely thing, this might really be a cool application. And maybe we'll figure out an automatic way to adjust the hyperparameters. Let me know what you think. Maybe you've already tried it out. You can give a little bit of a report on how that went. And I'll see you next time. Bye bye.
 Pay special attention to this paper. It is not a paper by Google or DeepMind or Meta or anything
 like this, yet I believe it is a really important paper. It discusses typical sampling, which is a
 new decoding strategy of how we sample from language models. We usually train language models
 with a maximum likelihood objective that put a lot of weight on very likely words. And when we use
 these models to produce language, we either explicitly or implicitly reproduce that we make
 these models sample very highly likely strings, which are boring and not human like, it's not
 what we do. I don't say things that are just highly likely, because I actually want to say
 something interesting. And that means that every now and then, I should utter something that's less
 likely, I should speak a word or a sentence that you didn't expect, because that's what transmits
 information. Typical sampling does exactly that and does it in a principled fashion. This video
 right here is a description, a review of the paper. And the next video is going to be an interview
 with Clara Meister, the first author of the paper. Both videos, but especially the interview, are
 super duper interesting. I would definitely invite you to check them both out. And I would definitely
 invite you to try out typical sampling. It is in hogging phase. And whenever your objective is
 to sample something that is very high quality, but also diverse and interesting, and not just
 bland high likelihood text, then that is your method for you. I believe that we do need new
 sampling strategies. And this one is very promising. Check it out, leave a like and see ya.
 Hi, let me quickly tell you about Fully Connected, which is curated space for the Applied ML community.
 It features articles, project reports, news events, and anything you could want, especially the
 projects page acts as a little bit of a product hunt for ML. So feel free to add your own project
 right here. It's curated by Weights and Biases, but I know what you're thinking. Yeah, another company,
 blog, whatever about their products. But this is not at all about Weights and Biases. It features
 some of their stuff, of course, but it is generally a really good resource to get good information on
 what's currently happening in deep learning. They have great articles and tutorials, like there's
 one on solving Wordle with reinforcement learning, which is pretty cool. There's one explaining
 group normalization in PyTorch. And there's one that explains to you how to run YOLOv5 object
 detection on Windows. So as you can see, they have all kinds of stuff. And the list of already
 existing articles is long. If you still don't believe me that it's not all Weights and Biases,
 in fact, you can submit a post there, you can click the button, write a post, it will be reviewed by
 them and then published. So one of the coolest ML startups currently is going to push your content.
 How great is that? Now, if you are just a lurker like me, then you know, head over there and
 subscribe because it's user submitted but curated so you get the best of both worlds. Besides
 articles, they also have events, which usually means their webinars about various topics,
 you can look at old webinars, but you can also subscribe to get updates on new ones. They also
 host their podcast, their gradient descent. And the current episode is actually with Jensen Huang,
 the CEO of Nvidia. So pretty big hitter. And lastly, it includes the good old Weights and
 Biases community forums where you can get all kinds of help on Weights and Biases products
 and beyond Weights and Biases to all kinds of things machine learning related. So again,
 fully connected, it just got a major redesign. Please check it out. Go over there, subscribe
 for awesome articles and news. There's new stuff all the time. Thank you so much to Weights and
 Biases for sponsoring this video. They've been a great sponsor. So please check them out. That's
 one db.ai slash fully dash connected. Now let's get into the video. See ya.
 Hello there today we'll look at typical decoding for natural language generation
 by Clara Meister, Tiago Pimentel, john Weaver and Ryan Cotterall. This paper suggests a new
 way of decoding of producing text from a large language model or a small language model. It
 doesn't matter. We don't discriminate here. In any case, usually currently you might have heard of
 things like beam search, you might have heard of things like nuclear sampling and top case sampling.
 These things are all right. And interestingly enough, the stochastic methods like nucleus and
 top case sampling are better than the methods that try to find the most likely things such as
 beam search or greedy decoding. However, it's still not satisfactory large language and small
 language models. They often produce text that is boring, just kind of bland when you actually use
 them, even though they have amazing perplexities on text. This paper tackles this. It proposes that
 when humans generate text, they don't just produce the most likely text, they will actually trade off
 likelihood with information content or the transmission of information to another human.
 And that trade off can be captured in the frameworks of information theory. And we can
 generate or we can suppose a decoding scheme, which they call typical decoding, typical sampling,
 which exactly encapsulates that notion of balancing interestingness or information
 with likelihood. And when they test it, that actually results in better results. This could be
 really crucial because it doesn't require any change to how we train language models. In fact,
 we can take off the shelf trained language models and simply use this new decoding strategy out of
 the box. And it applies across, you know, across domains. Now I have long said that we need that
 probably our decoding methods, our sampling methods may be inadequate depending on what we do with
 those language models. For example, alpha code samples a whole bunch of programs in order to solve
 a problem. Now we, again, we don't like there is value in diversity if you sample a whole bunch,
 and then after that use like a filter to narrow it down. So I think depending on what you want to do,
 maximum likelihood sampling is very appropriate. This paper, for example, mentions natural or
 machine translation, because in machine translation, you really want kind of the best translation for
 a given input. However, in other frameworks, such as alpha code, but also such as storytelling,
 this paper mentions summarization maybe as well, you want to, we want to trade off some of this
 maximum likelihood for some more diversity or for some more interestingness or for some more
 information content. And that's what this paper does. So we'll dive into it. If you like content
 like this, as always, leave a like, and don't be shy to let me know in the comments what you think.
 I'm not exactly I'm not entirely sold on what this paper does. I do agree we need better or we need
 a different decoding strategies. But I do have my, you know, reservations about this exact one. So
 let's dive into the paper. The paper first complains about the exact thing I complain about,
 namely saying that language models currently they have extremely low perplexities on on corpora
 for many domains, yet when used to generate text, their performance is far from perfect. And by that
 they mean, yeah, they they produce text that is undesirable, eg, generic or degenerate weight.
 Yes. So either generic or degenerate, or just as we said, boring, bland, you know, and that comes
 from the fact that a lot of these things, they try to find the maximal probability string. So
 they think, you know, I'm going to sample from the probability distribution, and I want to sample
 what is the most likely because that's how we train these models, right? So let's do a short
 excursion. If you are unaware of how language models are trained, they're usually trained.
 You have a sentence like the cat is in something the house. And it goes on. So what you can do is
 you input a part of the text, and then you let the model predict the next token, and then you
 input that part, and you let the model predict the next token. Now, in training, this is all good and
 fine. But at inference time, what you do is you provide a prefix, for example, the cat. And then
 you have to decode here, you have to decode a word, what's next, and then you feed that whatever
 you decoded into the language model, and you decode the next word. And I think that's where
 part of the problem comes from. Because during training, naturally, what is here is given by
 the data set. So every new step that you take, if there is something unlikely, if there is a certain
 diversity to the input, that's captured by the training data. However, in decoding, you sort of
 make your own data as you go along here. And if you just always focus on finding very likely next
 tokens, you'll never get into kind of a less likely environment, which could also be correct,
 right? So that is one of the problems. However, obviously, in these language models, the way
 they work is, for example, you input all of this into a big model, there is a little bit of a
 big model, there is some sort of a model, which usually is a transformer nowadays, and out comes
 a probability distribution. And the probability distribution is over your vocabulary. For example,
 there is the vocabulary, this cat, dog. I don't know another word. What's another word? House,
 something like this. And it will give you a distribution of probabilities over these words.
 And you can now choose what to do. Either you can take the maximum one, which often runs into these
 problems of being boring or even repetitive, you can take you can sample from this distribution,
 which is also not super appropriate, because, and the paper touches on this a little bit,
 because sometimes the long, what's called the long tail here, there are many, many words, of course,
 and they all have their some probability. And you don't want to get into these super low probability
 words, because they might just be artifacts of the model. The model doesn't represent these low
 probabilities really well. It's really good at the sort of high probability words, because, well,
 it's essentially trained as a classifier. And the classifier is trained to give you the correct
 label as the highest class. And it doesn't really care about the rest of the words, especially not
 the ones that have really low probability. So what people do is they came up with, first of all,
 Beam search, what beam search does is it considers multiple futures. So if it's here, that cat,
 like that cat, it considers multiple futures, and it looks a few steps ahead. So it looks a few steps
 ahead, and it keeps a list of things that are possible to complete. So for example, in the
 beginning, it goes all these three routes, and it keeps those in mind, along with the probabilities
 that you go along that tree. And then, you know, you go ahead, and maybe the buffer is five large,
 right? So now we can still fit it because there's one, two, three, four, five paths currently, but
 as soon as we expand the sixth one, this one here, we have to drop someone. So we consider all the
 paths, and we consider only the ones with the highest likelihood so far, this we can simply do
 by multiplying the probabilities of consecutive decoding steps, we consider the most likely five,
 let's say, paths so far, and we delete some of them. Let's say that this one here is really low
 probability. And then once we add this one here, and this one, we have to drop another few,
 so let's say this one, these two here are really low probability, and so on. And we only continue
 the paths that have good probabilities, or high enough probabilities to be the highest possible.
 That's beam search. And the reason why people do it is because there might, so there might be a very
 high likelihood sentence that you could produce, but the next word just happens to be low in
 probability, right? Maybe here, house will lead to a sentence that down the road is very likely,
 has a very good score, but just this word right now, in this case, is low probability, because
 the immediate best word would be dog for all the possible continuations, or for this particular
 prefix, for all the possible expected continuations. So beam search is a very, very, very, very
 high probability. So beam search is even worse than greedy decoding in the sense that it
 really finds the high probability stuff. It doesn't, and it looks ahead to be even more accurate.
 If you go to the opposite end of the spectrum, you can say, okay, can we sample, but can we fix
 the sampling issues that arise from this tail? And that's why people do two things. So there's top K,
 sampling, and there is nuclear sampling, and they both work pretty much the same. So top K, sampling,
 what it does is you have, again, your probability distribution, and top K sampling simply says,
 well, can we only consider the K largest entries in that distribution, and then just sample from
 that? So let's say K equals three, then we only consider the three largest entries here, and we
 just forget about the rest, and we only sample from that. We have to renormalize, but that's fine.
 And then nucleus sampling is very much the same, except it says, well, I'm going to afford myself
 a probability, a cumulative probability of, let's say, 0.7. What does it mean? It means that this
 distribution right now has a cumulative probability of one. I am simply going to take the largest ones,
 like, okay, this one, and this one, and this one, until the cumulative probability reaches my maximum
 threshold. Maybe I'm going to take this one as well. You can see the advantage here is that you
 don't always pick the same amount, but you always pick sort of the top entries that make up, let's
 say, in this case, 70% of the mass. And that is useful because you have to consider multiple
 scenarios. One scenario is where the distribution is very peaky, like, there, you only want to
 consider very few entries. So you only want to consider few entries because everything else is
 just really unlikely. However, if you think of a distribution that is more spread out, like this one,
 and then you want to consider more entries, because all of them are kind of likely,
 and nucleus sampling affords you that, whereas top case sampling would just disregard the shape of
 the distribution and pick the top ones. Right, so these are the decoding strategies, but still,
 you can see they always go to the top or the most likely things. And this paper says, well,
 that's kind of dumb. And it shapes this as a information theoretic problem. We already said
 that humans probably want to trade off the likelihood of a string. So like how likely it
 is to appear, meaning essentially how much it is expected, because if I just say things that other
 humans expect, right, then I'm essentially not transmitting much information at all. So we can
 say that every string has a form or a content of information. Actually, I'm going to skip here,
 skip here to the theory section directly. And forgive me, I've pretty much explained all of
 what's highlighted already. So what we can say is that a why, why is the message that you want to
 pass? So let's say it's a sentence, the information content can be quantified as its negative log
 probability. Essentially, the less likely a given message is, you can see here that's negative,
 negative log probability, the less likely a message is, the more information it carries.
 You have to think of it like exactly as I said, if I say something that's very likely, the other
 person could have expected it because it's so likely. It's like if you meet the stereotypical
 boring person, or if you see a movie where it's like a really stereotype of a boring person,
 they will always say exactly what you know what you'd expect them to say. However, if you say,
 let's say you communicate with someone, and they all of a sudden say something that you really
 didn't expect. Now that's a lot of information right there. In fact, you can buy simple application
 of the chain rule, you can see you can also define a information content for every single word in
 the sentence. And that is going to be just the conditional log probability, the log conditional
 probability of that word, given the prefix, and that's the prefix, those are the previous words
 in the sentence. So akin to the information in a sentence, a word carries a lot of information,
 if you really didn't expect to see that word as the next word in the current sentence that you
 begun or that your conversation partner has begun to say. So we carry this through. And the
 assumption here is that the goal of an agent is to transmit information efficiently, while also
 minimizing the risk of miscommunication. So that's the fundamental trade off that humans do when
 they communicate, at least that's the hypothesis. If you transmit a lot of information, you're going
 to have to utter some words that are very not likely, because that transmits a lot of information.
 However, if you overdo that, and if you, for example, don't follow the rules of grammar anymore,
 and just send around low information messages or high information, low likely messages, your
 receiver will be confused, because they don't know what to make of it, because they really didn't
 expect to see something like this. And therefore, there is a chance of miscommunication. You can also,
 you can imagine that if you want to transmit a message to someone, right, if you want to
 explain something to someone, you always have to adjust to what they already know. Like if I want
 to explain the chain rule to someone, and I expect them to already know a little bit of math, I'm going
 to transmit a lot, I'm going to have to adjust my message to that. And if I assume too much of what
 they already know, and then I'll just end up saying something like, oh, yeah, if you derive f of, you
 know, of g of x, with respect to x, then you have to, you know, you just derive g and then you kind
 of multiply by the derivation of f. And it's all good, right? It's all good. So sorry for this
 butchering of the chain rule. But you can imagine that someone who has little grasp of math in the
 first place would be very, very hard. Because I only utter the words that carry so much information
 that are so not likely in their framework, that there's a chance of miscommunication.
 I don't know if actually that captures it the best, maybe there's a better example.
 That's sort of how I think of it. What they do define, and now we get into the decoding strategy
 is the expected information, the expected information that a specific symbol in the
 message will contain. So this formula right here, you might recognize as the conditional entropy
 of a given word in the sentence, namely, and this, I think the notation here is a bit
 out of place. I think this should be something like the expectation of the information content
 of just that t-th word, not necessarily y of t, because y of t, we sum over y of t right here.
 So yeah, but so we ask ourselves, if we have already produced the sentence up to time step t,
 and we consider the distribution of words conditioned on this sentence, so we ask our
 language model, what's the distribution of words that could come next? And we ask ourselves for
 each of these one, what's the information content? And since we have the information content is the
 negative log probability, that's this, and here is the minus sign, we ask ourselves, so what is the
 expected information content of the next word, you know, whatever the next word is, what's the
 expectation of its information content, if we were to just sample from this probability distribution,
 and then this here is the formula, right, we simply multiply whatever we're interested in,
 which is the information content with the probability, and we sum that up across the set
 that we're interested in. That is, it's just the definition of the expected value. And by
 happenstance, it is also the definition of the entropy or the conditional entropy. So the
 expected information content of any given position in a sentence is the entropy of is the conditional
 entropy of the distribution at that point. So what does that mean? That means if my distribution is
 very peaked, so if it's very likely that one of these three words here is uttered next is, so if
 I find a text somewhere, right, and the sentence up to here was something, and then there's only
 like three words that could potentially be there, none else, it's very peak to distribution, that
 essentially means the entropy is very, very low. And therefore, the information content of that of
 whatever word comes next is probably going to be very low, because all these words are super likely.
 However, if the distribution is very shallow, or very broad, then the entropy is high. And you can
 also see, since any of the words that could come next, first of all, there are many more that could
 be considered, and all of them have less of a likelihood. Therefore, the negative log probability
 will be higher. So any of those words will have more information content, and especially the
 expectation over those words, it will the information content will be higher. So that is
 just the definition of the expected information content. Now, here's the hypothesis of this paper,
 and they base this on some psychologists, psychology theories, or linguistic theories.
 But here's the hypothesis. Any given word should have an information content close to the expected
 information content, i.e. the conditional entropy given prior context. In other words, we expect
 the difference between the expected information content and the true information content to be
 small in human-like text. So the hypothesis here is that the way humans balance this trade-off
 between interestingness and likelihood, and so in between information transmission and not being
 misunderstood, is that they implicitly calculate the expected information content of the next word,
 and then they try to choose the next word in accordance so that it is as close as possible
 to that expected information content. So when I talk, I model sort of the transmission channel
 to my receiver, and I figure out, okay, in the language right now, what would be the expected
 information content of the next word, and then I try to match that as closely as possible.
 And that gives me a way of determining this trade-off. Again, this is a hypothesis. It's
 backed up by a few theories from linguistics. This is also known in information theory as
 typicality. So a typical message is one that has the information content that is close to
 the expected information content, but we'll investigate. So they say figure one shows for
 human-generated text, the distribution of this epsilon. So this epsilon is the distance between
 these two quantities, the expectation and the actual thing that's uttered. Remember, the
 expectation considers all possible next words and calculates the expected information content of
 them. And then this thing right here, this thing is just the information content of the next word
 that is actually uttered or actually written. So what would we actually do? We would actually
 analyze the human-generated text. So what would we expect this or what do we see if we analyze
 human-generated text? And these here, these are obviously language models that estimate
 the probabilities of these words, but these are evaluated on human-generated text, so not on
 language model-generated text, because remember, this paper is all about how do we do that in
 the human-generated text. So let's take a look at what humans do, and you can see the distribution
 is very peaked. Now, this isn't the distribution of words, this is the distribution of this
 epsilon. So that essentially means this distance, this difference right here is very, very peaky,
 and it's peaky around a very small value. You can see here the scale goes from whatever,
 and the peak is at a value that's quite close to zero. Now, it's not exactly zero, but this is
 empirical data. So this paper says this is evidence for the fact that humans do, as much as they can,
 try to match the information content to the expected information content. Now, it'd be
 interesting to see what you would actually, let's say humans would just sample from the
 distribution itself, right? What kind of distance between the entropy and the information content
 would you expect to see? Maybe a Gaussian or a log Gaussian? I'm not entirely sure. Also,
 what is peaky? How do you characterize peaky? I can see peaky, but it's proof by picture, almost.
 And then we see a very interesting imbalance, namely, there seems to be sort of a mass going
 higher up, always on the left side of this, rather than on the right side. There seems to be a bit of
 a longer tail on the right side, but a bit more heavy mass on the left side. Now, what does that
 mean? This is, well, I can't really make sense of it, because the epsilon is characterized as an
 absolute value, whereas this right here is not an absolute value. And so I'm going to guess they
 left away the absolute value. Therefore, I don't know which, I don't know the distribution of the
 deviation of information content from the conditional entropy per token. Okay. Again,
 I do not know what came first, if they do h minus i, or if they do i minus h. And that determines
 how we interpret these plots. So I'd rather not interpret them in the wrong way right here.
 They further, so that's what they say, the peaked nature of the distribution reveals that humans
 indeed tend to form language with per word information content quite close to their expected
 information content. And the centering of these distributions around the value close to zero
 reveals that our probabilistic language generators are learning what this rate is.
 Well, I'm not sure I agree with that statement, because being peaked doesn't mean, doesn't mean,
 like you need both to be true at the same time. If you assume that the language models are really
 good at what they do, then you can claim that humans peak around zero and therefore they match
 the expected information content. If you assume that humans match the expected information content,
 then you can conclude that language models are really good at what they do, because the peak
 seems to be rather around zero. But you can't draw both conclusions at the same time from this plot,
 because you need one to justify the other. In any case, this is a minor point. What is interesting
 is that here, they go into information theory, as I said, this notion of typicality, which is exactly
 what we're describing right here. They say, it says typical messages are the ones that we would
 expect from its probability distribution. Their average per symbol information content is close
 to the entropy rate of their source distribution. Now, the interesting observation right here is
 that the definition implies that the highest probability message is often not a member of
 this set. Its average information content is too low. So if we consider any distribution and
 we consider what's the expected information content, which is the way we defined it,
 and we only consider messages, let's say these are the messages, we only consider messages that are
 close to that expected information content. But those are going to be messages that are
 kind of somewhere in the middle of the likelihood. So they're not super duper unlikely,
 because the expected information content is again the expectation over all of these messages,
 which is going to be not super duper high, which rules out these unlikely messages. These are prone
 to misunderstanding, but it also rules out the very likely messages, because those are going to be
 prone to being boring and not transmitting any information at all. And that is something
 interesting. That is exactly the property we want in a new decoding method, leave away the really
 low likelihood stuff and leave away the really high likelihood stuff, because that's boring.
 Yeah, tip, the typicality is a property. Okay, now they go into why we can't, why we have to go
 for a local, a local notion of typicality, whereas information theory usually defines it as a property
 of the of the entire sentence or of the entire message, don't necessarily want to go into that.
 The next chapter, they try to justify this with psycholinguistic concepts. There are two they
 consider. There's the uniform information density hypothesis, which proposes that speakers construct
 their utterances such that information is distributed uniformly across them. And
 the the the speakers choose words such that their information count, their information rate is
 closer to a target channel capacity, which is essentially what we're doing right here.
 Then there's the rational speech act, and the rational speech act, sort of, it casts the
 speaker's behavior as the maximization of a utility function. And the utility function is a set of
 sentences usefulness to its listener. So the way it constructs this, again, this is sort of hypothesis,
 it imagines this literal speaker. So this is a hypothetical speaker that just samples from the
 probability distribution, it just looks at the probability distribution, and just samples from
 that. And it just orders the words as, you know, as they come out. And that means, you know, with
 the typical problems like, it's going to utter the words, it's going to use the words, it's going to
 utter kind of low, low information stuff a lot of the times. Then it says, well, a smart, the pragmatic
 speaker, and that's what the humans would be at the pragmatic speaker produces sentences to maximize
 the utility function, as opposed to following its expected literal behavior. If you define the
 utility function to be this thing right here, then the hypothesis kind of matches, the hypothesis
 matches the this rational speech act. However, I find this also to be a little bit shady, because
 if I have a different decoding method in mind, I can apply the same argument, I can simply say, well,
 my, my utility function is now my new decoding method. So, yeah, I'm not super convinced by this.
 However, it's interesting to see that people think in this way that they say, well, there is going
 to be this literal imaginary agent that just speaks according to the distribution. And then
 there is the upgraded version of that. And probably the humans are a form of an upgraded version,
 this pragmatic speaker that changes something that sort of uses this distribution, but changes
 something about it. And that's exactly what we do. So how do we do it? And we've already alluded to
 most of it. So what we do is we introduce this typical sampling. Much like nucleus sampling,
 we define a threshold, in this case, this is called tau of probability mass that we're going to allow
 in our in our subset of words. So again, maybe we have a distribution of a couple of words, and they
 have different likelihoods under our language model output. And we assume our language model output
 models these probabilities, especially the non negligible ones. Well, then what we're going to
 do is we're going to calculate the expected information content, which is the expected
 negative log probability, which is also the conditional entropy. So we're going to estimate
 this property by simply calculating it. We can do this. This is simply again, this is p of x given y
 times log p of x given y. The log probability is usually already output by our model in the form
 of logits. We just need to normalize it. And if we apply some sort of a softmax operation,
 we get the p of x given y. So then we have the conditional entropy, and then we simply
 choose the words that are most close to this. So maybe the expected the entropy, let's say this is
 the let's say these are the log probabilities right here. Let's say the expected one is here,
 we simply choose in order the words that are most close to that one. So it would be this one right
 here. This is really close. Then this one is really close. Then what's a tough choice, maybe this one's
 really close. And then maybe this one's really close. And that we do that until again, we reach
 our target probability mass. Again, if the distribution is very peaked, so if the distribution
 is very peaked, that means the the typical information content is going to be lower,
 which means the words that have low information are going to be chosen more, which and these are
 also going to be less words. And that gives us our original case back where we're simply going
 to choose the highest likelihood words into our bucket to sample from. Yeah. And and that sort of
 regresses to the old case, if the distribution is very peaky. However, if the distribution is flatter
 or more broadly more broad support, then we the expected information content is going to be lower,
 which means that probably these highest likelihood ones are not going to be in it.
 And we opt for more interesting ones that are also likely, but not as likely. So this kicks in
 mostly when there's a lot of possibilities, which you can see in let's say machine translation,
 there is not in machine translation is often very clear or there's only a few possibilities on how
 there's only a few possibilities on how to translate something. However, in storytelling,
 there's lots of possibilities how things could continue. And there are distribution are much
 more shallow. And this method would exploit that by saying, well, I'm just not going to consider
 the most likely things right here. The computational complexity is the same as
 nucleus or top case sampling, we also have to determine the set we're going to consider
 by somehow calculating across it, we have to aggregate it, we have to renormalize it,
 and we have to sample from it, except here, well, I guess we always have to sort right.
 Yeah, here we also have to calculate this conditional entropy part, it's the same in
 complexity, but it does add a constant overhead or like a multiplicative constant factor overhead
 to the whole thing. So the last thing I want to go in here is the choice of hyper parameters
 in this one. They say we found k equals 30, and n equals point nine to perform best. So these
 parameters perform best for top k and nucleus sampling respectively. So this is for their
 experiments. So one is for top case sampling, and one is for nucleus sampling. For typical sampling,
 we found the tau equals point two and tau equals point nine five to provide the best results for
 story generation and abstractive summarization respectively. So while they allow for a single
 parameter for each of the baselines, they go with a separate parameter for different tasks for their
 method, which is a bit shady. Now, there's two possibilities. First possibility is they sort of
 stifled the baseline by only sort of giving it not exploring well enough the possibilities, or what I
 think happened most likely is that the same parameter performs pretty well for all the
 different tasks, which is a good property in itself right here. Here we consider 20% of the
 probability mass, and here we consider 95% of the probability mass. Now that's a huge difference
 in how our set looks. And that by itself makes it, in my opinion, a bit of a weaker choice for
 using this as a decoding method, because for every thing that I want to achieve, I need to essentially
 tune this parameter, whereas with top case sampling, I could just leave it be. So it'd be interesting
 to see if in the future there might be, because I'm a fan of this technique in principle. So maybe in
 the future, we can find more of an adaptive way, much like nucleus sampling is an adaptive way of
 top case sampling, maybe we can come up with an adaptive way of determining the number here or
 the parameter of how many things to consider. So I don't want to go too much into the evaluation.
 There is a difference. Sometimes it's stark, sometimes it's not as stark. It is different
 in different regimes. You can see that depending on the regime that you are at, it's sometimes
 the different methods are really different. Sometimes they're quite close, sometimes they
 switch places. Yeah, that's, I don't want to go too much into the results because we can maybe
 discuss them in an interview. But qualitatively, say for example, for the summarization task,
 we see that typical sampling provides a comprehensive and coherent summary of the
 article under consideration. In comparison, nucleus sampling leads to hallucinated facts,
 for example, getting drugs from under, okay, I haven't read the article, but nucleus sampling
 hallucinate facts, which is one property. If you sample only from high likelihood things,
 right, you're just going to continue with things that are very likely in the language itself,
 rather than transmitting the necessary information. While top case sampling misses some of the
 important information in the article, e.g. the charges of burglary and arson. And that might be
 because top case sampling simply has this fixed bucket of words to consider. And as soon as one
 word is not in that bucket, it simply is forbidden from uttering it, even if the distribution is
 shallow and that word is kind of likely. So I want to stop here and just give a few thoughts
 on this. In my opinion, I already said it is quite needed that we have different decoding strategies
 to achieve different tasks. This one right here, it seems really interesting. It is a way to trade
 off sort of not considering the most likely things, but also not considering the least likely things.
 However, I'm not sure if the notion of the matching the expected information content
 is appropriate. I can't tell. It's a good hypothesis. I don't know if this quantity here,
 the absolute distance is a good quantity. Like, why would it be the absolute distance? And the
 other issue I have right here, but this might be my ignorance of information theory is. So if I
 change, let's if I assume the humans talk like this, they choose their words according to the
 expected information content, right? And I use this particular construction right here. That
 is going to everything that comes out of this. Whatever comes out of this will have a different
 expected information content than the original language. If I wanted to actually match,
 like if I wanted to keep the expectation, I probably couldn't do this just in absolute
 difference. That's probably going to change the expected information content, let alone the
 distribution of it itself. But just the expectation is going to change. Now, if you're telling me that
 humans do it like this, and that our language models are trained on text that is written and
 uttered by humans, like wouldn't that text already have that property and therefore sampling from it
 would be the original distribution? Or in other words, if I produce text like this, like,
 shouldn't I get the same, shouldn't I get the same distribution out that my language model predicts,
 because my language model is trained on human text, and your claim is that humans sample text
 like this. So why would that be any different from sampling from the language model itself?
 And especially, shouldn't it be that the expected information content remains constant if I apply
 this sampling technique? Just out of principle, because by definition, if it doesn't, then it
 doesn't match human generated text, because that's already the input. That's the training data.
 All right, but maybe I'm sort of ignorant of information theory right here. Yeah, my other
 concerns are with the hyperparameter choice. And yeah, I'd be interested to dive a little bit more
 into this, like what would we expect to see with the different
 sampling methods or with different hypotheses? This is also really interesting, but I'm going
 to leave it at that. All I can say is that we should probably try this out. And maybe, you know,
 for certain tasks where diversity and actually transmitting information is more important than
 being, you know, uttering the most likely thing, this might really be a cool application. And maybe
 we'll figure out an automatic way to adjust the hyperparameters. Let me know what you think. Maybe
 you've already tried it out. You can give a little bit of a report on how that went. And I'll see you
 next time. Bye bye.