next up previous contents
次へ: Baum-Welchアルゴリズム 上へ: 認識アルゴリズム 戻る: 認識アルゴリズム   目次

Viterbiアルゴリズム

Viterbiアルゴリズムはモデル$\lambda$において最適な状態系列(最短経路) $S=s_1,s_2,\cdots,s_T$と,この経路上での確率を求めるアルゴリズムである.

モデル$\lambda$において観測系列 $O=o_1,o_2,\dots,o_T$に対する最適な状態系列 $S=s_1,s_2,\cdots,s_T$を求めるために,時刻$t$で状態$i$に至るまでの最適 状態確率$\delta_t(i)$を定義する.

$\displaystyle \delta_t(i)=
\max_{s_1,s_2,\cdots,s_t-1}p(s_1,s_2,\cdots,s_t=i,o_1,o_2,\cdots,o_t\vert\lambda)$     (14)

時刻$t+1$における最適状態の確率は次のように導出できる.

$\displaystyle \delta_{t+1}(j)=[\max_i \delta_t(i)a_{ij}]・b_{ij}(o_{t+1})$     (15)

時刻$t$状態$i$において生成確率を最大にする経路(状態遷移)を$\Psi_t(j)$,最 適経路の生成確率を$p^*$,最適経路上の最終状態を$s^*_T$とすると最適経路, およびその生成確率は以下の手順で求まる.

  1. 初期化

    $\displaystyle \delta_0=π_i\Psi_0(i)=0     (1<i<N)$     (16)

  2. 繰返し

    $\displaystyle \delta_t(j)$ $\textstyle =$ $\displaystyle \max_{1\leq i\leq N}[\delta_{t-1}(i)a_{ij}b_{ij}(o_t)]$ (17)
    $\displaystyle \Psi_t$ $\textstyle =$ $\displaystyle \arg\max_{1\leq i\leq N}[\delta_{t-1}(i)a_{ij}b_{ij}]
     (1<t<T),(1<j<N)$ (18)

  3. 最終チェック

    $\displaystyle p^*$ $\textstyle =$ $\displaystyle \max_{1\leq i\leq N}[\delta_T(i)]$ (19)
    $\displaystyle s^*_T$ $\textstyle =$ $\displaystyle \arg\max_{1\leq i\leq N}[\delta_T(i)]$ (20)

  4. 経路トレース

    $\displaystyle s^*_t=\Psi_{t+1}(s_{t+1})     (t=T-1,\cdots,1)$     (21)

4.で求めた $s^*_0,s^*_1,\cdots,s *_T$が最適経路となる. Viterbiアルゴリズムは,HMMの初期モデル作成と認識に使用されている.


next up previous contents
次へ: Baum-Welchアルゴリズム 上へ: 認識アルゴリズム 戻る: 認識アルゴリズム   目次
平成20年3月11日