Viterbiサーチの経路計算

Viterbiサーチにおいて最尤の単語列の結果を得るアルゴリズムとして、２つ の方法が考えられる。

1. 最大累積尤度の計算終了後にトレースバック

   各時刻・各状態において、最大累積尤度を計算したときに、選択した経路を記 憶しておく。そして尤度の計算が終了した後、トレースバックを行ない最尤の 単語列を得る[40]。この方法は、各時刻・各状態において、選択した経 路を記憶するために$O$(認識語彙数$\times$音声データのフレーム数)のメ モリ量が必要である。

2. 最大累積尤度と同時に計算

   各時刻・各状態において、最大累積尤度の計算と同時に、選択した経路を次の 状態に渡す。図2.11）に単語bigramを使用した場合の例を示す。 単語 trigramを使用したときもほぼ同様なアルゴリズムになる。このアルゴリ ズムにおいて必要なメモリ量は$O$ (認識語彙数$\times$文の単語数)である。 ただし、この方法は、経路をコピーする必要があるため計算量は前の方法と比 較すると、若干増加する。

   図 2.11: Viterbiサーチの経路計算方法

   

前者は、計算量が少なくて済むため広く利用されている。後者は、前者と比 較すると計算量は若干増加するが、多くの場合、文の単語数は音声データの フレーム数より少ないためメモリ量が削減できる。なお、このアルゴリズム は各時刻・各状態（$G_t(w_0,i)$）においてトレースバックをしなくても累 積尤度が最大の単語列を知ることができる。