HMM Algorithms
Forward–backward, Viterbi and Baum–Welch.
Rabiner's 1989 tutorial organized hidden Markov models around three problems: how likely is an observation sequence, which hidden path explains it best, and which parameters make it most likely. The answers are two dynamic programs over a trellis and an EM loop that provably never makes the fit worse. They ran speech recognition for decades, and they still power gene finders, sequence alignment and the training of speech models with CTC.
What you’ll learn
- Prove the forward–backward identities for the posteriors and , and implement them with scaling in time.
- Prove the correctness of the Viterbi algorithm, and derive posterior decoding and Viterbi decoding as Bayes decisions under different losses.
- Derive Baum–Welch as EM, and prove that each iteration does not decrease the likelihood.
- Explain local optima and identifiability, spectral learning of HMMs, and where HMM dynamic programming lives on in modern sequence models.
Forward–backward, precisely
Factor the joint with the chain rule and the HMM's independences: given , everything later is independent of ; given , the observations and are independent of and of each other:
Divide by to get the pairwise posterior, and sum over , using the backward recursion, to get the single-step posterior:
Since sums to 1, the likelihood can be read off at any time step; gives the forward algorithm's answer.
Scaling. The raw underflow exponentially in . Normalize: is the filtered belief of the Hidden Layer, with normalizer ; divide by to get . Then
Both passes cost time, and storing the forward messages costs memory. For very long sequences, checkpointing trades time for space: keep only every steps and recompute each segment during the backward pass, for memory and about twice the time; recursive checkpointing reaches memory at a factor in time (Binder, Murphy & Russell, 1997).
In the umbrella world (prior , persistence 0.7, , ), with umbrellas on days 1 and 2, for (rain, dry). What is , and what is the filtered ?
- and
- and
- and
- and
Show the answer
B. and
, and normalizing gives , the Hidden Layer's filtered value. Every scaled forward message is a filtered belief.
Decoding: Viterbi versus posterior decoding
The forward algorithm and Viterbi are the same dynamic program over different semirings: for the likelihood, for the best path, and on log-probabilities, where Viterbi becomes a shortest-path computation on a trellis with nodes. Which decoder to use is a decision problem. Suppose you report a sequence and are charged a loss.
A gene finder is scored by the fraction of nucleotides it labels correctly (coding or non-coding). Which decoder minimizes its expected error?
- Viterbi, because it finds the most probable labeling
- Posterior decoding, choosing at each position
- Filtering, choosing at each position
- Either: they always give the same labeling
Show the answer
B. Posterior decoding, choosing at each position
Per-position accuracy is Hamming loss, minimized term by term by the posterior marginals. If the score were "entire annotation exactly right", Viterbi would be the Bayes decision instead.
Learning: Baum–Welch is EM
With the hidden path unobserved, maximum likelihood has no closed form. If the path were observed, the answer would be normalized counts. Baum–Welch (Baum, Petrie, Soules & Weiss, 1970) replaces the counts by their expectations under the current posterior, an instance of the EM algorithm (Dempster, Laird & Rubin, 1977).
For any , write the likelihood as an expectation under the current posterior and apply Jensen's inequality to the concave logarithm:
At the ratio inside the logarithm is the constant , so the bound is tight. Subtracting the two cases:
is a sum of log-parameters along the path, so splits into separate terms for , each row of and each row of , weighted by expected counts from forward–backward:
Each term is maximized, under its normalization constraint, by normalized expected counts (Gibbs' inequality). The M-step therefore gives , hence . ∎
Identifiability, spectral learning and HMMs today
Is there an efficient algorithm that provably learns an HMM? In general, no one expects one: Mossel & Roch (2006) showed that learning HMMs would let you learn parity with noise, a problem believed to be hard. Under rank conditions, however, learning becomes easy.
With the prior on as in the Hidden Layer, the probability of a sequence is a product of observable operators, , where is the forward step for symbol . Predictions are unchanged if every is replaced by for an invertible (with and transformed accordingly). Hsu, Kakade & Zhang (2012) showed that, when the transition and emission matrices have rank , such a transformed set can be estimated from the empirical probabilities of observation pairs and triples by a singular value decomposition, with polynomial sample complexity and no local optima. Tensor decompositions of the same moments recover the parameters themselves (Anandkumar et al., 2014).
HMM dynamic programming lives on inside modern systems:
- Speech recognition. Hybrid systems, in which a deep network supplies the emission probabilities of an HMM, dominated the early 2010s (Hinton et al., 2012). Connectionist temporal classification (Graves et al., 2006) trains end-to-end models with a forward–backward pass over all alignments of the transcript, using an extra blank symbol.
- Biological sequences. Gene finders and profile HMMs for protein families decode genomes and search sequence databases with Viterbi and forward scores.
- State-space sequence models. Deep architectures built on linear recurrences, such as S4 and Mamba, revisit the structure of the filtering recursion with learned, deterministic dynamics.
Key takeaways
- gives , and at any , in time; scaled forward messages are filtered beliefs, and .
- Viterbi is the version of the forward algorithm and returns the most probable path; posterior decoding minimizes the expected number of wrong positions. The Viterbi path itself may be far from certain (0.34 in the umbrella example).
- Baum–Welch is EM: expected counts from forward–backward, then normalization. Jensen's inequality makes the likelihood non-decreasing, but only local optima are guaranteed.
- Learning HMMs is hard in general but tractable under rank conditions via observable operators and spectral methods. HMM dynamic programming survives in hybrid speech recognizers, CTC and biological sequence analysis.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Which expression equals the likelihood for every between 1 and ?
Show the answer
C.
, and summing over gives at any . Only at , where , does alone suffice.
What does the EM monotonicity theorem guarantee for Baum–Welch?
- Convergence to the global maximum of the likelihood
- Convergence in a number of iterations polynomial in
- That the hidden states are recovered with their true labels
- That the likelihood never decreases from one iteration to the next
Show the answer
D. That the likelihood never decreases from one iteration to the next
Each M-step increases the lower bound , which touches the log-likelihood at the current parameters, so the likelihood cannot go down. Nothing prevents convergence to a local optimum or a saddle point.
An implementation normalizes the forward vector at each step, recording the normalizers . How does it obtain ?
- It cannot; normalizing destroys the likelihood
Show the answer
A.
, and by the chain rule , so , computed without underflow.
Further reading
- L. R. Rabiner, "A tutorial on hidden Markov models and selected applications in speech recognition," Proceedings of the IEEE 77(2), 257–286 (1989).
- L. E. Baum, T. Petrie, G. Soules & N. Weiss, "A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains," Annals of Mathematical Statistics 41(1), 164–171 (1970).
- A. J. Viterbi, "Error bounds for convolutional codes and an asymptotically optimum decoding algorithm," IEEE Transactions on Information Theory 13(2), 260–269 (1967).
- A. P. Dempster, N. M. Laird & D. B. Rubin, "Maximum likelihood from incomplete data via the EM algorithm," Journal of the Royal Statistical Society B 39(1), 1–38 (1977).
- D. Hsu, S. M. Kakade & T. Zhang, "A spectral algorithm for learning hidden Markov models," Journal of Computer and System Sciences 78(5), 1460–1480 (2012).