Viterbiサーチの経路計算

Viterbiサーチでは、最尤の単語列の結果を得るために２つの 方法が考えられる。

1. トレースバック

   各時刻・各状態において、最大累積尤度を計算したときに、選択 した経路を記憶しておく。そして尤度の計算が終了した後トレースバックを行 ない最尤の単語列を得る [1]。この方法は、各時刻・各状態において、選択した経路を記憶するために［ビーム幅$b$ $\times$ 最大認識時間の フレーム長］のメモリ量が必要である。しかし計算量は少なくて済む。
   

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

   各時刻・各状態において、最大累積尤度の計算と同時 に、選択した経路を次の状態に渡す。 この方法ではトレースバックをしないで最尤の単語列を得ることができる。 また、必要なメモリ量は［ビーム幅$b$ $\times$ 文を構成する最大単語数］であるが、 一般的には文を構成する最大単語数は 最大認識時間のフレーム長より少なくて済むため、トレースバックを行う方法より必要なメモリ は減少する。そのかわり、必要な計算量はやや増加する。

前者は、計算量が少なくて済むため良く利用されている。後者は、 前者と比較すると計算量が増加するが、各時刻・各状態においてト レースバックをしなくても経路を知ることが可能であるため、言語 モデルにおけるleft-right型のパーザーと組み合わせることが容易 である。また、多くの場合、前者と比較して小量のメモリですむ。 このアルゴリズムでは、メモリ量の増加を押えるため、後者を選択した。