ビームサーチ ハイパー入門

この記事の目的と対象読者

　- 目的
　音声認識系の論文を読んでいるときにビームサーチとはなんぞや？論文を読むときにつまらないこと
　そして毎度恒例、私自身のためのノートです。
　- 対象読者
　　目的に合致する人

以上

最速で落ちつく大雑把な理解

・ビームサーチとはテキスト生成の際に、複数の候補から最もそれらしいものを探索するための手法
・文章生成（デコード）の後に複数候補を探索することにより文章全体で最大確率を目指す
ここでは簡単に音声Xから次の文字を何にするかを逐次決めている場面を想定します。
実際には現代ではデコード方法としてよく①自己回帰型（Attention decoderなど）②CTC③RNN-T型④その他がありますが、それはどこか遠くに置いておきましょう。

数式で納得しよう

「こんにちは」という文章を
「こ」→「ん」→・・・
のようにデコードしていくと考えます。
このとき、デコーダでは例えば

「ち」  0.70
「ゃ」  0.15
「ん」  0.08
「く」  0.03
...

のような語彙全体に対する確率分布を出力しています。
単純に確率が最も高い候補を選べばいいのではと思ったそこのあなた！
確かにその通りです。この手法は貪食法（Greedy法）と呼ばれる選択方法です。
しかし、この問題点は
各時点での最大確率を示す選択の積み重ねが必ずしも文章全体で最大確率を示すとは限らない
ことです。

人生と同じなんですね。その時点で最良の選択をしてきたとしても長いスパンで見るとそれが本当に最良なんだろうか？そんなことを考えてしまった人が考案したんでしょうかね？

脱線しました。
「ごめんさい」
（これをさっきの方法でデコードしようとしたらおそらく「ん」の後は「な」が最大確率を示すけれど、候補をいくつか保持しておくと正しい文章をデコードできるイメージでしょうか）私の喋る「さ」と「な」が音響的に類似していた場合の過程ですが

これを、CTC/Atteintionのハイブリットアーキテクチャ（例えばReazonSpeech ver2.0 ESPnet版がこれに当たります)_{※公式資料にはRNN-Tとありましたが使ってみた時に中身を見たらCTC/Attentionハイブリッドでした。}のASRシステムにおいて定式化すると以下になります。[1]

logP(g⋅c∣X)=logP(g∣X)+logP(c∣g,X)

g：現在までの仮説（例：「ごめん」）
c：次に追加する文字（候補）
X：入力音声の特徴系列

ここから算出した確率を部分仮説集合Ω_l0 として保持しておくことでスコアを更新していきます。
イメージ
Ω₀0 = {}

↓ 1文字展開

Ω₁0 = {ご, あ, こ, ...}

↓ さらに展開

Ω₂0 = {ごめ, ごま, あな, ...}

参考文献

Hori, Takaaki, Shinji WatanabeとJohn Hershey. 「Joint CTC/Attention Decoding for End-to-End Speech Recognition」. Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 2017年, 518–29. https://doi.org/10.18653/v1/P17-1048.　522ページの数式（９）