ビームサーチ

Viterbiサーチは、全ての尤度の計算が終了した後に、累積尤度が 最大の単語列を選択するアルゴリズムである。したがって各フレー ムごとの尤度計算において累積尤度の低い単語列は、以後の探索か ら除外できる可能性が高い。そこで、フレームごとに最尤なものか らある個数（ビーム幅$b$）のみ計算を続けることにより、計算量 およびメモリ量が大幅に減らせる[4]。具体的には、すべ ての$w_1,w_0,i$に対して 表 2  step5 の式の計算のかわりに、最も高い累積尤度から、ある個数 （ビーム幅$b$）のみを計算する。したがって必要なメモリ量は $G_t(w_1,w_0,i)$ を記憶するために、フルサーチは[認識語彙数$^ 2 \times$ 単語の状態数]が必要であるのに対し、ビームサーチ では[ビーム幅 $b$]しか必要としないため大幅に削減できる。同様 な比率で計算量も削減できる。