next up previous contents
次へ: 単語のtrigramを使用したときのViterbiサーチ 上へ: アルゴリズムの改良 戻る: Viterbi サーチにおけるN-bestサーチ   目次

Viterbiサーチの経路計算

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

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

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

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

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

    図 2.11: Viterbiサーチの経路計算方法
    \begin{figure}\begin{center}
\fbox{\epsfile{file=FIGURE/figure4.5.ps,width=100mm}}\end{center}\end{figure}

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



Jin'ichi Murakami 平成13年1月5日