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 and 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, 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 just try Beam Search using our running example of the French sentence,
"Jane, visite l'Afrique en Septembre".
Hopefully being translated into,
"Jane, visits Africa in September".
The first thing Beam search has to do is try to pick
the first words of the English translation,
that's going to operate.
So here I've listed,
say, 10,000 words into vocabulary.
And to simplify the problem a bit,
I'm going to ignore capitalization.
So I'm just listing all the words in lower case.
So, in the first step of Beam Search,
I use this network fragment with the coalition in green and decoalition in purple,
to try to evaluate what is the probability of that for a square.
So, what's the probability of the first output y,
given the input sentence x gives the French input.
So, whereas greedy search will pick only the one most likely words 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 with the three.
And what this means is Beam search will cause that
not just one possibility but consider three at the time.
So in particular, let's say evaluating
this probability over different choices the first words,
it finds that the choices in,
Jane and September are
the most likely three possibilities for the first words in the English outputs.
Then Beam search will stowaway in
computer memory that it wants to try all of three of these words,
and if the beam width parameter were said differently,
the beam width parameter was 10,
then we keep track of not just three but of the ten,
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 French sentence through
this encoder network and then this first step will then decode the network,
this is a softmax output overall 10,000 possibilities.
Then you would take those 10,000 possible
outputs and keep in memory which were the top three.
Let's go into the second step of Beam search.
Having picked in, Jane and September as the three most likely choice 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 a second word is "a" or maybe as Aaron,
I'm just listing words from the vocabulary,
from the dictionary or somewhere down the list will be September,
somewhere down the list there's visit and then all the way
to z and then the last word is zulu.
So, to evaluate the probability of second word,
it will use this new network fragments where is coder in
green and for the decoder portion when trying to decide what comes after in.
Remember the decoder first outputs, y hat one.
So, I'm going to set to this y hat one to the word "in" as it goes back in.
So there's the word "in" because it decided for now.
That's because It trying to figure out that the first word was "in",
what is the second word,
and then this will output I guess y hat two.
And so by hard wiring y hat one here,
really the inputs here to be the first words
"in" this time were fragment can be used to evaluate whether it's
the probability of the second word given
the input french sentence and that
the first words of the translation has been the word "in".
Now notice that what we also need help out in this second step would be
assertions to find the pair of the first and second words that is most
likely it's not just a second where is most
likely that the pair of the first and second whereas
the most likely and by the rules of conditional probability.
This can be expressed as P of the first words
times P of probability of the second words.
Which you are getting from
this network fragment and so if for each of the three words you've chosen "in",
"Jane," and "September" you save away this probability then you can multiply them by
this second probabilities to get the probability of the first and second words.
So now you've seen how if the first word was
"in" how you can evaluate the probability of the second word.
Now at first it 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 will use this in
your network fragments let me draw this in as well where here you will hardwire,
Y hat One to be Jane.
And so with the First word y one hat's hard wired
as Jane than just the network fragments
can tell you what's the probability of the second words to me.
And given that the first word is "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 do the same thing for
September although words from a down to Zulu and use this network fragment.
That just goes in as well to see if the first word was September.
What was the most likely options for the second words.
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
10000 or thirty thousand possibilities because there are 10,000 here,
10,000 here, 10,000 here as
the beam width times the number of words in the vocabulary and what you
do is you evaluate all of these 30000 options
according to the probably the first and second words and then pick the top three.
So with a cut down,
these 30,000 possibilities down to three again down
the beam width rounded again so let's say that 30,000 choices,
the most likely were in September and say Jane is,
and Jane visits sorry this bit messy but those are the most likely three out of the
30,000 choices then that's what Beam's search would memorize
away and take on to the next step being surge.
So notice one thing if beam search decides that
the most likely choices are 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 words of the output English translation
so we're now down to two possibilities for the first words but we still have a beam width
of three keeping track of three choices for pairs of Y1,
Y2 before going onto the third step of beam search.
Just want to notice that because of beam width is equal to three,
every step you instantiate three copies of
the network to evaluate these partial sentence fragments and the output.
And it's because of beam width is equal to three that you have
three copies of the network with different choices for the first words,
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 or 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 said that the most likely choices for first two words were in September, Jane is,
and Jane visits and for each of
these pairs of words which we should have saved the way 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 in September a?
In September Aaron?
All the way down to is in
September Zulu and to evaluate possible choices for the third word,
you use this network fragments 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 and 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 may be that things in September.
Jane is a likely outcome or Jane is visiting is likely or maybe Jane visits
Africa is likely for that first three words and then it keeps
going and then you go onto the fourth step of
beam search hat 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 visits Africa in September will be terminated by
the end of sentence symbol using that system is quite common.
They'll find that this is a likely output English sentence
and you'll see more details of this yourself.
In this week's exercise as well where you get to play with beam search yourself.
So with a beam of three being searched considers three possibilities at a time.
Notice that if the beam width was said to be equal to one,
say cause there's only one,
then this essentially becomes
the greedy search algorithm which we had discussed in the last video but by considering
multiple possibilities say three or ten 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 from our partners
that help you to make beam search work even better.
Let's go onto the next video to take a look.