Week 3 beam search termination criteria

Hi I’ve just finished watching the 3rd lecture “beam search” in week 3. I have a quick question on when beam search algorithm should stop?

If we follow the example in the lecture and beam width is 3, every step we would have 3 most probable sentences. Suppose after some steps one of the sentence reaches an <EOS>, should we just stop the algorithm and output this sentence, or we should continue with the rest 2 sentences until all 3 sentences reaches <EOS>, and output the sentence with the highest probability?

Thanks for the help!

There are 2 stages in beam search:

  1. Candidate generation
  2. Selecting the most likely candidate.

During candidate generation phase, it’s alright to get sentences of varying lengths. Your model might predict <EOS> quite early on some paths.
A candidate path doesn’t impact other candidate paths.

For the 2nd step, to ensure that we don’t prefer shorter sentences over longer sentences, length normalization is done.

As far as termination conditions go, a path is stopped when one of the 2 conditions is met:

  1. Model outputs <EOS>
  2. The maximum timesteps for which you want to generate candidates for is exhausted.

Here’s a lecture you want to watch:

1 Like