機械翻訳などで文章を自動的に翻訳するためのモデルとして有効なものの一つとして, Encoder-decoderモデルというものがあります。
Encoder-decoderモデルでは, decoderの各ステップで出力された各語彙に対する確率から有力な単語を選んでいくことで訳文を生成することができます。
https://web.stanford.edu/~jurafsky/slp3/10.pdf
しかしながら, この選び方だといくつか問題点があるので, 1~n段階目で出力されたベクトルからもっともらしい単語の組み合わせを訳文として選ぶことを考えてみます。
つまり訳文の候補を全探索していくことになるのですが, 文の長さを\(L\), 語彙(モデルが知っている単語の集合)を\(V\)とすると, 計算量が\(|V|^L\)と指数関数的に増加してしまいます。
これを回避しながら探索を行うためのアルゴリズムがビームサーチと呼ばれるものです。
ビームサーチは幅優先探索を改良したヒューリスティックな探索アルゴリズムです。
下の図で表されるように, ビームサーチはビーム幅を設定して探索幅を制限しているところが特徴です。
このビーム幅のおかげで, 計算量が膨大になってしまうことを防ぎつつ, それなりに良い結果を出すことができるわけです。
https://web.stanford.edu/~jurafsky/slp3/10.pdf
アルゴリズムのステップとしては次のようになります。
step1: 出力ベクトルyの中からスコアが上位のB(ビーム幅)個の要素を選び, flontierとする. 生成された部分的な出力のシーケンス（つまりflontierの要素）をhypothesesとする.
step2: それぞれのhypothesesが, 再びdecorderに渡されて出力ベクトルを得る
step3: スコアが高い上位B個のhypothesesを次のflontierに加える
step4: EOS(文の最後を示す特殊な記号)が生成されるまで続ける。生成されたら, flontierからこのhypothesesを除き, ビーム幅を1減らす
step5: ビーム幅が0になったら終了する. ここまでの操作で得られたB個のhypothesesが候補の訳文となる.
これを使えば比較的少ない計算量で訳文を生成することができるので, 非常に有力なアルゴリズムだといえます。
また, 図からも分かるように, 生成されたB個の訳文候補は文の長さが異なるので, 長いものほど確率が小さくなってしまいます。（単語に対する確率をより多く掛け合わせることになるから）
したがって, 文の長さに関する正規化を行うなどのことをして, 文が長いというだけで確率が小さくなってしまうのを防ぐ必要があります。
英語の動画になりますが, ビームサーチを解説した動画がYoutubeにアップロードされているので参考にしてみてください。
ただしこの動画では単語レベルではなく文字レベルでビームサーチを行っているので, そこだけ注意してください。
<参考文献>
Encoder-Decoder Models, At- tention, and Contextual Em- beddings https://web.stanford.edu/~jurafsky/slp3/10.pdf
