Forward復号法

最適状態遷移系列の推定にはViterbi復号法の他にForward復号法 が考えられる。このアルゴリズムは、始めに HMMのパラメータ $\mbox{\boldmath$M$}$がコード系列 $\mbox{\boldmath$O$}$を出力する時の尤度を、 各状態からの総和で計算する。次に最適状態遷移系列は各時刻 における最大の尤度を持つ状態とする。このForward復号法を次 に示す。

1. 全ての $i\in\{1,...,N\}$に対し、
   
   $$\delta_1(i) = \pi_i \times b_i(\mbox{\boldmath$o$}_1)$$
   
   
   
   
   $$s_1^*= arg \max_i\delta_1(i)$$
   
   

2. 時間軸$t=2,...,T$に沿って、全ての $j\in\{1,...,N\}$に対し
   
   $$\delta_t(j) = \sum_i[\delta_{t-1}(i) \times a_{ij} \times b_j(\mbox{\boldmath$o$}_t)]$$
   
   
   
   
   $$s_t^*= arg \max_j\delta_t(j)$$
   
   

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