Forward decoding ( New spotting algorithm )

In this algorithm, first, a score is calculated for summing each score of a state. Next, the optimal state sequence is assigned for the best score of each frame. This decoding algorithm is given as follows.

$s_t$ : optimal state sequence at time $t$;
$\delta_t(j)$ : score at time $t$ and state $j$ ;
$N$ : number of states for Ergodic HMM ;
$a_{ij}$ ; transition probability at state $i$ to $j$;
$b_j(\mbox{\boldmath$o$}_t)$ ; output probability at state $j$
when the observation vector is $(\mbox{\boldmath$o$}_t)$ ;

1. For all states $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. Calculate $j\in\{1,...,N\}$ along the time axis for $t=2,...,T$ and for all states j, compute:
   

   $\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 final score is given by :
   $\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)$

Finally, if the optimal state sequence is the last state of any word, it is assumed that this word is recognized.

This decoding algorithm is similar to the forward-backward algorithm[5]. However, it can recognize the word for each frame, and therefore, can be regarded as a kind of word spotting algorithm.