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)$     (39)

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

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

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

  1. 初期化

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

  2. 繰返し

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

  3. 最終チェック

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

  4. 経路トレース

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

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

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