ビームサーチ

各フレームごとの尤度計算において、累積尤度の低い単語列は正解の単語列にな る可能性が低いため、以後の探索から除外できる可能性が高い。そこで、フレー ムごとに最も高い累積尤度から正解の存在をおおよそ保証できる、ある個数（ビー ム幅$b$）のみ計算を続けることにより、計算量およびメモリ量が削減できる [4]。具体的には、すべての$w_n,..,w_0,i$に対して最も高い累積尤度 から、ある個数（ビーム幅$b$）のみを計算する。したがって $G_t(w_n,...,w_0,i)$を記憶するメモリ量は、フルサーチでは$O$(認識語彙数 $^n \times$単語の状態数)が必要であるのに対し、ビームサーチでは $O$(ビー ム幅 $b$)しか必要としないため大幅に削減できる。また、計算量もビーム幅の 計算方法によって異なるが、同様な比率で削減できる。

なお、フルサーチをフレーム同期で計算し、さらにビームサーチと組み合わせ たアルゴリズムは、フレーム同期型のstack decorder[5]と アルゴリズムは同一であると考えている。