Beam search finds better translations and transcriptions than greedy search by tracking multiple candidate sequences at once. The lecture walks through a French-to-English example, showing how beam width affects speed and quality, and why copying the decoder is faster than running softmax thousands of times.
Chapters
In this video, you learn about the beam search algorithm. In the last video, you remember how for machine translation, given an input French sentence, you don't want to output a random English translation, you want to output the best, the most likely English translation. The same is also true for speech recognition, where given an input audio clip, you don't want to output a random text transcript. Of that audio, you want to output the best, maybe the most likely translation text transcript. Beam search is the most widely used algorithm to do this. And in this video you see how to get beam search to work for yourself. Let's describe Beam search using our running example of the French sentence. Jane visit Le Freak on Septem. Hopefully being translated into Jane visits Africa in September. The first thing beam search has to do is try to pick the first word of the English translation that it's going to output. So here I've listed all, say 10,000 words in the vocabulary. And to simplify the problem a bit, I'm going to ignore capitalization, so I'm just listing all the words in lowercase. So in the first step of beam search, I'll use this network fragment with the encoder shown in green and the decoder shown in purple to try to evaluate what is the probability of that first word. So what's the probability of the first output Y given the input sentence, X given the French Input? So whereas GreedySearch will pick only the one most likely word and move on, Beam search instead can consider multiple alternatives. So the beam search algorithm has a parameter called B which is called the beam width. And for this example, I'm going to set the beam width to be equal to three. And what this means is beam search will consider not just one possibility, but consider three at a time. So in particular, let's say evaluating this probability over different choices of the first word, it finds that the the choices in Jane and September are the most likely three possibilities for the first word in the English output. Then beam search will store away in computer memory that it wants to try out all three of these words. And if the beamwidth parameter was set differently, if the beamwidth parameter was say 10, then we keep track of not just three, but of the 10 most likely possible choices for the first word. So to be clear, in order to perform this first step of beam search, what you need to do is run the input fringe sentence through this encoder network and then this first step of the decoder network. If this is a softmax output over all 10,000 possibilities, then you would take those 10,000 possible outputs and keep in memory which were the top three. Let's go on to the second step of Beam search. Having picked in Jane and September as the three most likely choices of the first word, what Beam search will do now is for each of these three choices, consider what should be the second word. So after in, maybe the second word is A, or maybe it's Aaron. I'm just listing words from the vocabulary from the dictionary. Or somewhere down the list will be September, somewhere down the list is Visit, and then all the way to Z. Maybe the last word is Zulu. So to evaluate the probability of second word, it will use this neural network fragment where there's the encoder in green and for the decoder portion, when trying to decide what comes after in, remember, the decoder first outputs Y hat one. So we're going to set this Y hat one to the word in and feed this back in. So this is the word in because we decided for now that because you're trying to figure out that the first word was in, what is the second word? And then this will output, I guess, y hat 2. And so by hardwiring y hat 1 here, really the input here to be the first word in this network fragment can be used to evaluate what is the probability of the second word given the input French sentence, and that the first word of the translation has been the word it. Now, notice that what we ultimately care about in this second step of Beam search is to find the pair of the first and second words that is most likely. So not just the second word that's most likely, but the pair of the first and second words are most likely. And by the rules of conditional probability, this can be expressed as P of the first word times P of probability of the second word which you are getting from this neural network fragment. And so if for each of the three words you've chosen in Jane in September, you save away this probability, then you can multiply them by this second probability to get the probability of the first and second word. So now you've seen how if the first word was in, how you can evaluate the probability of the second word. Now, if the first word was Jane, you do the same thing. The sentence could be Jane, a Jane Aaron, and so on down to Jane is Jane visits, and so on. And you would use this neural network fragment and let me draw this in as well, where here you would hardwire Y hat one to be Jane. And so with the first word y one hat wired as Jane, then this neural network fragment can tell you what's the probability of the second word given the input X and given that the first word was Jane? And then, same as above, you can multiply with p of y1 to get the probability of y1 and y2 for each of these 10,000 different possible choices for the second word. And then finally you do the same thing for September, all the words from A down to Zulu, and use this network fragment. I just draw this in as well to see if the first word was September. What are the most likely options for the second word? So for this second step of beam search, because we're continuing to use a beam width of three, and because there are 10,000 words in the vocabulary, you'd end up considering three times 10,000 or 30,000 possibilities, because there are 10,000 here, 10,000 here, 10,001 here. So it's a beam width. So it's a beam width times the number of words in the vocabulary. And what you do is you evaluate all of these 30,000 options according to the probability of the first and second words and then pick the top three. So we're gonna cut down these 30,000 possibilities down to three again, down to the beamworth parameter again. And so let's say that of these 30,000 choices, the most likely were in September. And say Jane is and Jane visits. Sorry, this is a bit messy, but if those are the most likely three out of the 30,000 choices, then the that's what beam search would memorize away and take on to the next step of beam search. So notice one thing. If beam search decides that the three most likely choices for the first and second words are in September or Jane is or Jane visits, then what that means is that it is now rejecting September as a candidate for the first word of the output. English translation. So we're now down to two possibilities for the first word, but we still have a beam width of 3. Keeping track of three choices for pairs of y1, y2. Before going on to the third step of beam search, just want to notice that because the beam width is equal to three at every step, you instantiate three copies of the network to evaluate these partial sentence fragments in the output. And it's because the beam width is equal to three that you have three copies of the network with different choices for the first word. But these three copies of the network can be very efficiently used to evaluate all 30,000 options for the second word. So just don't instantiate 30,000 copies of the network. You need only three copies of the network to very quickly evaluate all 10,000 possible outputs. At that Softmax output, say for Y2. Let's just quickly illustrate one more step of Beam Search. So we said that the most likely choices of first two words were in September, Jane is and Jane visits. And for each of these pairs of words, we should have saved away in computer memory the probability of y1 and y2 given the input X given the French sentence X. So, similar to before, we now want to consider what is the third word? So is it in September A in September, Aaron all the way down to in September Zulu. And to evaluate possible choices for the third word, you use this network fragment where you hardwire the first word here to be in the second word to be September. And so this network fragment allows you to evaluate what's the probability of the third word given the input French sentence X and given that the first two words are in September in the English output. And then you do the same thing for the second fragment. So like so and same thing for Jane visits. And so Beam Search will then once again pick the top three possibilities. Maybe it thinks in September Jane is a likely outcome, or Jane is visiting is likely, or maybe Jane visits Africa is likely for the first three words. And then it keeps going. And then you go on to the fourth step of Beam Search to add one more word. And on it goes. And the outcome of this process, hopefully will be that adding one word at a time, that Beam Search will decide that Jane versus Africa in September may be terminated by the end of sentence symbol. If you're using that in your system, which is quite common, they'll find that this is a likely output English sentence. And you see more details of this for yourself in this week's drawing exercise as well, where you get to play with Beam Search yourself. So, with a beam width of 3, Beam Search considers three possibilities at a time. Notice that if the beam width was set to be equal to one, so it considers only one, then this essentially becomes the ReadySearch algorithm, which we had discussed in the last video. But by considering multiple possibilities, say 3 or 10 or some other number at the same time, Beam Search will usually find a much better output sentence than Greedy Search. You've now seen how Beam Search works, but it turns out there's some additional tips and tricks and refinements that help you to make Beam Search work even better. Let's go on to the next video to take a look.
