Viterbiアルゴリズム

推定されたHMMのパラメータ $\mbox{\boldmath$M$}$がコード系列 $\mbox{\boldmath$O$}$を出力する時 の最も可能性の高い状態遷移系列は、Viterbiアルゴリズムにより 効率的に求まる。Viterbiアルゴリズムを次に示す。

1. 全ての $i\in\{1,...,N\}$に対し、
   
   $$\delta_1(i) = \log\pi_i + \log b_i(\mbox{\boldmath$o$}_1), \phi_1(i) = 0$$
   
   
   とおく。
2. 時間軸$t=2,...,T$に沿って、全ての $j\in\{1,...,N\}$に対し
   
   $$\delta_t(j) = \max_i[\delta_{t-1}(i)+\log a_{ij} + \log b_j(\mbox{\boldmath$o$}_t)],$$
   
   
   
   
   $$\phi_t(j) = \arg\max_i[\delta_{t-1}(i) + \log a_{ij}]$$
   
   

3. 状態遷移系列に対する対数尤度及び$T$時刻目の最適状態を次式 で求める。
   
   $$\max_{\mbox{\boldmath$S$}}P(\mbox{\boldmath$O$},\mbox{\boldmath$S$}\mid\mbox{\boldmath$M$}) = \max_j\delta_T(j),$$
   
   
   
   
   $$s_T^* = \arg\max_j\delta_T(j)$$
   
   

4. 時間軸$t=T-1,...,1$に沿って、次式により状態遷移系列を得る。
   
   
   $$s_t^*=\phi_{t+1}(s_{t+1}^*)$$