A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition

III.A Solution to problem 1

1. Why can’t \(P(O \mid \lambda)\) be computed by enumerating state sequences?
   \(P(O \mid \lambda) = \sum_Q \pi_{q_1} b_{q_1}(O_1) a_{q_1 q_2} b_{q_2}(O_2) \cdots\) sums over \(N^T\) sequences, about \(2T \cdot N^T\) operations: for \(N = 5\), \(T = 100\), around \(10^{72}\).
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), III.A Solution to problem 1
2. Define the forward variable and its recursion.
   \(\alpha_t(i) = P(O_1 \ldots O_t, q_t = S_i \mid \lambda)\). Initialization \(\alpha_1(i) = \pi_i b_i(O_1)\); induction \(\alpha_{t+1}(j) = \big[\sum_i \alpha_t(i) a_{ij}\big] b_j(O_{t+1})\); termination \(P(O \mid \lambda) = \sum_i \alpha_T(i)\). Cost about \(N^2 T\) (about 3000 operations for \(N = 5\), \(T = 100\)).

   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), III.A Solution to problem 1
3. Why is the forward procedure so efficient?
   Because of the lattice (trellis): there are only \(N\) states per time slot, so however long the sequence, all paths re-merge into these \(N\) nodes, and each node needs only the \(N\) values of the previous slot.
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), III.A Solution to problem 1
4. Define the backward variable and its recursion.
   \(\beta_t(i) = P(O_{t+1} \ldots O_T \mid q_t = S_i, \lambda)\), with \(\beta_T(i) = 1\) and \(\beta_t(i) = \sum_j a_{ij} b_j(O_{t+1}) \beta_{t+1}(j)\). Not needed for Problem 1, but used for Problems 2 and 3.
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), III.A Solution to problem 1