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)$を定義する．

$$\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)$$ (9)

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

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

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

1. 初期化
   
   

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

   
   

2. 繰返し
   
   

   $$\delta_t(j) = \max_{1\leq i\leq N}[\delta_{t-1}(i)a_{ij}b_{ij}(o_t)]$$ (12)

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

   
   

3. 最終チェック
   
   

   $$p^* = \max_{1\leq i\leq N}[\delta_T(i)]$$ (14)

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

   
   

4. 経路トレース
   
   

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

   
   

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