next up previous contents
次へ: トレリス法と対数を用いたアルゴリズムの違い 上へ: 認識アルゴリズム 戻る: Forwardアルゴリズム(トレリス法)   目次

Viterbiアルゴリズム

Viterbiアルゴリズムは,モデルの最適な状態遷移行列(最適経路)と,この経路上 での確率を求めるアルゴリズムである.

$ P(y|M)$ を厳密に求めないで,近似的に,モデルMが符号ベクトル系列$ y$ を出力する ときの最も可能性の高い状態系列上での出現確率を用いることを考える.この出 現確率(尤度)は,各遷移での確率値を対数変換しておくことにより,加算と大小判 定のみからなるDP演算によって高速に求めることができる.このアルゴリズムを以下に示す. $ i = 1,2, \cdots ,S$ において

$\displaystyle f'(i,t) = \left\{ \begin{array}{ll} \log \pi_{i} & (t = 0) \\ \m...
...log a_{ji} b_{ji} ( y_{t}) \} & (t = 1, 2, \cdots ,T ) \end{array} \}\right.$ (26)

を計算し,対数尤度

$\displaystyle L = \max_{i, s_i \in F} f' (i,t)$ (27)

を求める[4].

5は,前記の図2のHMMがラベル系列$ abb$ を出力する例に適応した例であるが,最短経路となるのが図の太い矢印で示した経路である.

Viterbiアルゴリズムは,本研究においてHMMの初期モデル作成とマルチパス法 による認識に使用されている.

図 5: Viterbi アルゴリズムの適用例
\resizebox{15cm}{!}{\includegraphics{viterbi_sample.eps}}


平成20年5月16日