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

III.B Solution to problem 2

1. Why is there no unique solution to Problem 2?
   Except for degenerate models there is no “correct” state sequence, only sequences optimal under some criterion, and the right criterion depends on the use (learning model structure, continuous speech recognition, state statistics…).
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), III.B Solution to problem 2
2. What is the “individually most likely states” criterion, and its flaw?
   Choose \(q_t = \arg\max_i \gamma_t(i)\), where \(\gamma_t(i) = \frac{\alpha_t(i)\beta_t(i)}{P(O \mid \lambda)}\), maximizing the expected number of correct states. But the resulting sequence may be invalid (use a transition with \(a_{ij} = 0\)), since it ignores the probability of state sequences.
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), III.B Solution to problem 2
3. Describe the Viterbi algorithm.
   Find the single best path: \(\delta_t(i)\) is the highest probability of a path ending in \(S_i\) at time \(t\); \(\delta_{t+1}(j) = \big[\max_i \delta_t(i) a_{ij}\big] b_j(O_{t+1})\), keeping back-pointers \(\psi_{t+1}(j) = \arg\max_i\); at the end take \(\arg\max_i \delta_T(i)\) and backtrack.
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), III.B Solution to problem 2
4. How does Viterbi differ from the forward procedure?
   It is the same lattice computation with maximization over previous states in place of summation, plus backtracking to recover the path.
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), III.B Solution to problem 2