Interactive demo · Bayesian and Probabilistic Machine Learning · Chapter 13

Hidden Markov models: sampling, forward-backward, Viterbi and Baum-Welch

A hidden state z_n ∈ {1, 2, 3} follows a Markov chain with transition matrix A, and each state emits a point x_n in the plane from its own Gaussian (ellipses: 1 and 2 standard deviations). The forward-backward algorithm gives the posterior probability γ(z_n) of each state at each step (a point's colour is the mix of the state colours); Viterbi finds the single most probable path; Baum-Welch is EM for the parameters, and its log likelihood can only go up.

Show

Sequence length N

Stay probability A_kk

Emission spread (overlap)

left-to-right model (Figs 13.9, 13.10)

Baum-Welch (EM)

Try these

True model: emission means (0.31, 0.72), (0.30, 0.20), (0.70, 0.47) and covariances read off Figure 13.8 of Bishop (2006), all standard deviations multiplied by the spread; off-diagonal transitions share 1 − A_kk equally; π uniform. The left-to-right model starts in state 1, may only stay or move up by one, and stays with probability 1 − 3/N, so a sequence typically visits all three states. Baum-Welch starts from three data points chosen at random as means, the data covariance for every state and A_kk = 0.6 (left-to-right: the sequence cut into thirds). The random numbers are seeded, so a class sees the same pictures.

In the lecture notes

Chapter 13 notes: Section 13.2 (hidden Markov models, sampling, left-to-right models), Section 13.2.1 (maximum likelihood and the Baum-Welch M step), Section 13.2.2 (the forward-backward algorithm), Section 13.2.4 (scaling factors) and Section 13.2.5 (the Viterbi algorithm).
Python code: code/ch13_sequential_data.py (functions hmm_sample, forward_backward, viterbi, baum_welch; Figures 13.8, 13.12, 13.13, 13.16) and the checks in code/checks_ch13.py. Passing JSRandom(seed) to hmm_sample reproduces this page's sequences; preset 1 is the sequence of our Figure 13.8.