ビームサーチ

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

図 2.6: ビームサーチの計算方法