Forward/Backward Procedure

We wish to compute the probability of observation sequence ${\bf O}=O_1 O_2\cdots O_T$ given the model $\Lambda=\{\pi_j, a_{ij}, b_j\}$. The forward procedure for $p({\bf O}\vert\Lambda)$ is

1. Initialization:

   $$\alpha_1(i) = \pi_i \; b_i(O_1), \;\;\;\; 1\leq i \leq N$$ (13.9)

   
   

2. Induction:

   $$\begin{array}{rcl} \alpha_{t+1}(j) = \left[ {\displaystyle \s... ...t+1}), && 1\leq t \leq T-1 \\ && 1\leq j \leq N \end{array}$$ (13.10)

   
   

3. Termination:

   $$p({\bf O}\vert\Lambda) = {\displaystyle \sum_{i=1}^N} \alpha_T(i)$$ (13.11)

   
   

The backward procedure is

1. Initialization:

   $$\beta_T(i) = 1$$ (13.12)

   
   

2. Induction:

   $$\begin{array}{rcl} \beta_t(i) = {\displaystyle \sum_{j=1}^N} ... ...1}(j), && t=T-1,T-2, \cdots, 1 && 1\leq i \leq N \end{array}$$ (13.13)