Forward algorithm

To estimate the optimal state sequence, we propose the new algorithm called the forward algorithm.

This algorithm summarizes the likelihood for all states. The optimal state sequence is then chosen as the maximum likelihood state at each time (frame).

This forward algorithm is described as follows.

1. For all $i\in\{1,...,N\}$, let
   
   $$\delta_1(i) = \pi_i \times b_i(\mbox{\boldmath$o$}_1)$$
   
   
   
   
   $$s_1^*= arg \max_i\delta_1(i)$$
   
   

2. Along the time axis $t=2,...,T$, for all $j\in\{1,...,N\}$, let
   
   $$\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. The likelihood for all possible state transition sequences and the optimal state at time $T$ are given as follows.
   
   $$\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)$$