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

III.C Solution to problem 3

1. Can the HMM parameters maximizing \(P(O \mid \lambda)\) be found analytically?
   No: there is no known analytic solution, and for finite training data no optimal way of estimating them. Iterative methods (Baum–Welch/EM, or gradient techniques) find local maxima.
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), III.C Solution to problem 3
2. Define \(\xi_t(i, j)\) and \(\gamma_t(i)\).
   \(\xi_t(i, j) = P(q_t = S_i, q_{t+1} = S_j \mid O, \lambda) = \frac{\alpha_t(i) a_{ij} b_j(O_{t+1}) \beta_{t+1}(j)}{P(O \mid \lambda)}\), and \(\gamma_t(i) = \sum_j \xi_t(i, j)\). Summed over \(t\), they give expected numbers of transitions from \(S_i\) to \(S_j\) and from \(S_i\).
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), III.C Solution to problem 3
3. Give the Baum–Welch re-estimation formulas.
   \(\bar{\pi}_i = \gamma_1(i)\); \(\bar{a}_{ij} = \frac{\sum_t \xi_t(i, j)}{\sum_t \gamma_t(i)}\) (expected transitions \(i \to j\) / expected transitions from \(i\)); \(\bar{b}_j(k) = \frac{\sum_{t: O_t = v_k} \gamma_t(j)}{\sum_t \gamma_t(j)}\) (expected times in \(j\) seeing \(v_k\) / expected times in \(j\)).
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), III.C Solution to problem 3
4. What does Baum’s theorem guarantee about re-estimation?
   Either the current model is a critical point of the likelihood (and re-estimation leaves it unchanged), or the re-estimated model is strictly more likely: \(P(O \mid \bar\lambda) > P(O \mid \lambda)\). Iterating converges to a local maximum, often one of many.
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), III.C Solution to problem 3
5. How is Baum–Welch related to EM?
   It is EM for this problem: the E step computes Baum’s auxiliary function \(Q(\lambda, \bar\lambda) = \sum_Q P(Q \mid O, \lambda) \log P(O, Q \mid \bar\lambda)\), the M step maximizes it; the stochastic constraints on the parameters are satisfied automatically.
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), III.C Solution to problem 3