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

V Implementation issues for HMMs

1. Why is scaling necessary in the forward–backward computation?
   Each \(\alpha_t(i)\) is a sum of products of many probabilities below 1, so it heads exponentially to zero; for \(t\) around 100 it underflows even in double precision.
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), V Implementation issues for HMMs
2. How does scaling work, and how is the likelihood obtained?
   Normalize the \(\alpha_t(i)\) at each \(t\) by \(c_t = 1 / \sum_i \alpha_t(i)\), scale the \(\beta\)s with the same factors (which cancel in the re-estimation formulas), and compute \(\log P(O \mid \lambda) = -\sum_t \log c_t\).
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), V Implementation issues for HMMs
3. How is Viterbi made numerically safe?
   Work with logarithms: \(\phi_t(j) = \max_i [\phi_{t-1}(i) + \log a_{ij}] + \log b_j(O_t)\), which needs no scaling; the log terms can be precomputed.
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), V Implementation issues for HMMs
4. Why must left-right models be trained on multiple observation sequences, and how?
   Each state sees only a few observations before moving on, so one sequence gives too little data. Re-estimation sums the expected counts over all independent sequences (each with its own scaling).
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), V Implementation issues for HMMs
5. How should HMM parameters be initialized?
   Random or uniform initial \(\pi\) and \(A\) usually suffice; good initial \(B\) estimates help for discrete symbols and are essential for continuous mixtures, e.g. from manual segmentation, maximum-likelihood segmentation, or segmental k-means.
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), V Implementation issues for HMMs
6. How can insufficient training data be handled?
   More data, a smaller model, or interpolating the full model with a reduced (tied) model, \(\bar\lambda = \epsilon\lambda + (1 - \epsilon)\lambda'\), with \(\epsilon\) estimated by forward–backward on held-out data (deleted interpolation, Jelinek and Mercer).
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), V Implementation issues for HMMs