Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

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 γt\gamma_t and ξt\xi_t, and implement them with scaling in O(TN2)\order{TN^2} 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

DerivationThe posterior identities
  1. P(O,Xt=i,Xt+1=j)=P(o1:t,Xt=i)⏟αt(i) aij bj(ot+1) P(ot+2:T∣Xt+1=j)⏟βt+1(j)P(O,X_t=i,X_{t+1}=j)=\underbrace{P(o_{1:t},X_t=i)}_{\alpha_t(i)}\,a_{ij}\,b_j(o_{t+1})\,\underbrace{P(o_{t+2:T}\mid X_{t+1}=j)}_{\beta_{t+1}(j)}

    Factor the joint with the chain rule and the HMM's independences: given XtX_t, everything later is independent of o1:to_{1:t}; given Xt+1X_{t+1}, the observations ot+1o_{t+1} and ot+2:To_{t+2:T} are independent of XtX_t and of each other:

  2. ξt(i,j)=αt(i) aij bj(ot+1) βt+1(j)P(O),γt(i)=∑jξt(i,j)=αt(i) βt(i)P(O)\xi_t(i,j)=\frac{\alpha_t(i)\,a_{ij}\,b_j(o_{t+1})\,\beta_{t+1}(j)}{P(O)},\qquad\gamma_t(i)=\sum_j\xi_t(i,j)=\frac{\alpha_t(i)\,\beta_t(i)}{P(O)}

    Divide by P(O)P(O) to get the pairwise posterior, and sum over jj, using the backward recursion, to get the single-step posterior:

  3. P(O)=∑iαt(i) βt(i)for every t,P(O)=∑iαT(i)P(O)=\sum_i\alpha_t(i)\,\beta_t(i)\quad\text{for every }t,\qquad P(O)=\sum_i\alpha_T(i)

    Since γt\gamma_t sums to 1, the likelihood can be read off at any time step; t=Tt=T gives the forward algorithm's answer.

  4. γt=α^t⊙β^t,ξt(i,j)=α^t(i) aij bj(ot+1) β^t+1(j)ct+1,log⁡P(O)=∑t=1Tlog⁡ct\gamma_t=\hat\alpha_t\odot\hat\beta_t,\qquad\xi_t(i,j)=\frac{\hat\alpha_t(i)\,a_{ij}\,b_j(o_{t+1})\,\hat\beta_{t+1}(j)}{c_{t+1}},\qquad\log P(O)=\sum_{t=1}^T\log c_t

    Scaling. The raw αt\alpha_t underflow exponentially in TT. Normalize: α^t=αt/P(o1:t)\hat\alpha_t=\alpha_t/P(o_{1:t}) is the filtered belief f1:tf_{1:t} of the Hidden Layer, with normalizer ct=P(ot∣o1:t−1)c_t=P(o_t\mid o_{1:t-1}); divide βt\beta_t by ct+1⋯cTc_{t+1}\cdots c_T to get β^t\hat\beta_t. Then

Both passes cost O(TN2)\order{TN^2} time, and storing the forward messages costs O(TN)\order{TN} memory. For very long sequences, checkpointing trades time for space: keep α^t\hat\alpha_t only every T\sqrt T steps and recompute each segment during the backward pass, for O(NT)\order{N\sqrt T} memory and about twice the time; recursive checkpointing reaches O(Nlog⁡T)\order{N\log T} memory at a log⁡T\log T factor in time (Binder, Murphy & Russell, 1997).

Check your understanding

In the umbrella world (prior (0.5,0.5)(0.5,0.5), persistence 0.7, P(u∣rain)=0.9P(u\mid\text{rain})=0.9, P(u∣dry)=0.2P(u\mid\text{dry})=0.2), with umbrellas on days 1 and 2, α2=(0.3105, 0.041)\alpha_2=(0.3105,\ 0.041) for (rain, dry). What is P(u1,u2)P(u_1,u_2), and what is the filtered P(rain2∣u1,u2)P(\text{rain}_2\mid u_1,u_2)?

  1. 0.31050.3105 and 0.8830.883
  2. 0.35150.3515 and 0.8830.883
  3. 0.35150.3515 and 0.8180.818
  4. 0.26950.2695 and 0.8830.883
Show the answer

B. 0.35150.3515 and 0.8830.883

P(O)=∑iαT(i)=0.3105+0.041=0.3515P(O)=\sum_i\alpha_T(i)=0.3105+0.041=0.3515, and normalizing α2\alpha_2 gives 0.3105/0.3515=0.8830.3105/0.3515=0.883, 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: (+,×)(+,\times) for the likelihood, (max⁡,×)(\max,\times) for the best path, and (max⁡,+)(\max,+) on log-probabilities, where Viterbi becomes a shortest-path computation on a trellis with TNTN nodes. Which decoder to use is a decision problem. Suppose you report a sequence x^1:T\hat x_{1:T} and are charged a loss.

Check your understanding

A gene finder is scored by the fraction of nucleotides it labels correctly (coding or non-coding). Which decoder minimizes its expected error?

  1. Viterbi, because it finds the most probable labeling
  2. Posterior decoding, choosing arg max⁡iγt(i)\argmax_i\gamma_t(i) at each position
  3. Filtering, choosing arg max⁡iP(Xt=i∣o1:t)\argmax_iP(X_t=i\mid o_{1:t}) at each position
  4. Either: they always give the same labeling
Show the answer

B. Posterior decoding, choosing arg max⁡iγt(i)\argmax_i\gamma_t(i) 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 max⁡λP(O∣λ)\max_\lambda P(O\mid\lambda) 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).

DerivationThe EM bound and the re-estimation formulas
  1. log⁡P(O∣λ′)=log⁡∑xP(x∣O,λ) P(O,x∣λ′)P(x∣O,λ) ≥ ∑xP(x∣O,λ)log⁡P(O,x∣λ′)⏟Q(λ′,λ)+H(P(⋅∣O,λ))\log P(O\mid\lambda')=\log\sum_xP(x\mid O,\lambda)\,\frac{P(O,x\mid\lambda')}{P(x\mid O,\lambda)}\ \ge\ \underbrace{\sum_xP(x\mid O,\lambda)\log P(O,x\mid\lambda')}_{Q(\lambda',\lambda)}+H\big(P(\cdot\mid O,\lambda)\big)

    For any λ′\lambda', write the likelihood as an expectation under the current posterior P(x∣O,λ)P(x\mid O,\lambda) and apply Jensen's inequality to the concave logarithm:

  2. log⁡P(O∣λ′)−log⁡P(O∣λ) ≥ Q(λ′,λ)−Q(λ,λ)\log P(O\mid\lambda')-\log P(O\mid\lambda)\ \ge\ Q(\lambda',\lambda)-Q(\lambda,\lambda)

    At λ′=λ\lambda'=\lambda the ratio inside the logarithm is the constant P(O∣λ)P(O\mid\lambda), so the bound is tight. Subtracting the two cases:

  3. Q(λ′,λ)=∑iγ1(i)log⁡πi′+∑i,j(∑t=1T−1ξt(i,j))log⁡aij′+∑j∑t=1Tγt(j)log⁡bj′(ot)Q(\lambda',\lambda)=\sum_i\gamma_1(i)\log\pi_i'+\sum_{i,j}\Big(\sum_{t=1}^{T-1}\xi_t(i,j)\Big)\log a_{ij}'+\sum_j\sum_{t=1}^T\gamma_t(j)\log b_j'(o_t)

    log⁡P(O,x∣λ′)\log P(O,x\mid\lambda') is a sum of log-parameters along the path, so QQ splits into separate terms for π\boldsymbol\pi, each row of AA and each row of BB, weighted by expected counts from forward–backward:

  4. πi′=γ1(i),aij′=∑t=1T−1ξt(i,j)∑t=1T−1γt(i),bj′(k)=∑t: ot=kγt(j)∑t=1Tγt(j)\pi_i'=\gamma_1(i),\qquad a_{ij}'=\frac{\sum_{t=1}^{T-1}\xi_t(i,j)}{\sum_{t=1}^{T-1}\gamma_t(i)},\qquad b_j'(k)=\frac{\sum_{t:\,o_t=k}\gamma_t(j)}{\sum_{t=1}^T\gamma_t(j)}

    Each term is maximized, under its normalization constraint, by normalized expected counts (Gibbs' inequality). The M-step therefore gives Q(λ′,λ)≥Q(λ,λ)Q(\lambda',\lambda)\ge Q(\lambda,\lambda), hence P(O∣λ′)≥P(O∣λ)P(O\mid\lambda')\ge P(O\mid\lambda). ∎

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 X0X_0 as in the Hidden Layer, the probability of a sequence is a product of observable operators, P(o1:t)=1⊤Aot⋯Ao1π0P(o_{1:t})=\mathbf 1^\top A_{o_t}\cdots A_{o_1}\boldsymbol\pi_0, where Ao=OoT⊤A_o=O_oT^\top is the forward step for symbol oo. Predictions are unchanged if every AoA_o is replaced by SAoS−1SA_oS^{-1} for an invertible SS (with π0\boldsymbol\pi_0 and 1\mathbf 1 transformed accordingly). Hsu, Kakade & Zhang (2012) showed that, when the transition and emission matrices have rank NN, 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

  • αt(i)βt(i)=P(O,Xt=i)\alpha_t(i)\beta_t(i)=P(O,X_t=i) gives γt\gamma_t, ξt\xi_t and P(O)P(O) at any tt, in O(TN2)\order{TN^2} time; scaled forward messages are filtered beliefs, and log⁡P(O)=∑tlog⁡ct\log P(O)=\sum_t\log c_t.
  • Viterbi is the (max⁡,×)(\max,\times) 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.

Question 1

Which expression equals the likelihood P(O∣λ)P(O\mid\lambda) for every tt between 1 and TT?

  1. ∑iαt(i)\sum_i\alpha_t(i)
  2. ∑iβt(i)\sum_i\beta_t(i)
  3. ∑iαt(i) βt(i)\sum_i\alpha_t(i)\,\beta_t(i)
  4. max⁡iαt(i) βt(i)\max_i\alpha_t(i)\,\beta_t(i)
Show the answer

C. ∑iαt(i) βt(i)\sum_i\alpha_t(i)\,\beta_t(i)

αt(i)βt(i)=P(O,Xt=i)\alpha_t(i)\beta_t(i)=P(O,X_t=i), and summing over ii gives P(O)P(O) at any tt. Only at t=Tt=T, where βT=1\beta_T=\mathbf 1, does ∑iαt(i)\sum_i\alpha_t(i) alone suffice.

Question 2

What does the EM monotonicity theorem guarantee for Baum–Welch?

  1. Convergence to the global maximum of the likelihood
  2. Convergence in a number of iterations polynomial in NN
  3. That the hidden states are recovered with their true labels
  4. That the likelihood P(O∣λ)P(O\mid\lambda) never decreases from one iteration to the next
Show the answer

D. That the likelihood P(O∣λ)P(O\mid\lambda) never decreases from one iteration to the next

Each M-step increases the lower bound QQ, 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.

Question 3

An implementation normalizes the forward vector at each step, recording the normalizers c1,…,cTc_1,\dots,c_T. How does it obtain log⁡P(O)\log P(O)?

  1. ∑tlog⁡ct\sum_t\log c_t
  2. log⁡cT\log c_T
  3. ∏tlog⁡ct\prod_t\log c_t
  4. It cannot; normalizing destroys the likelihood
Show the answer

A. ∑tlog⁡ct\sum_t\log c_t

ct=P(ot∣o1:t−1)c_t=P(o_t\mid o_{1:t-1}), and by the chain rule P(O)=∏tctP(O)=\prod_tc_t, so log⁡P(O)=∑tlog⁡ct\log P(O)=\sum_t\log c_t, 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).