COMP5318 — Applied Machine Learning
Week 11: Markov Models and Hidden Markov Models
Probabilistic models for sequences. A Markov chain models transitions between observable states; a Hidden Markov Model (HMM) adds a layer of hidden states that emit observations. We meet the three fundamental HMM problems and the dynamic programming algorithms that solve them.
Course materials
Week 11 introduces a whole new kind of model: probabilistic sequence models. The slides walk a single weather example (Rainy / Cloudy / Sunny with clothing observations) all the way through the Markov chain, the HMM definition, the Forward algorithm, and the Viterbi algorithm. Re-derive each numerical step by hand before reading the worked solution.
| File | What you should learn from it |
|---|---|
| ml11.pdf | History of Markov chains; the Markov assumption; transition matrix \(A\) and initial vector \(\pi\); sequence-probability formula via the chain rule; HMM components \(\lambda = (A, B, \pi)\); the three problems (Evaluation, Decoding, Learning); enumeration baseline and its \(2T\,N^T\) complexity; Forward algorithm with recurrence \(f_k(i)\); Viterbi algorithm with score \(V_k(i)\) and backpointer \(\text{Ptr}\); EM / Baum-Welch outline for learning; applications in POS tagging, finance, bioinformatics, vision, security. |
Markov models: sequences of observable states
A Markov chain is a probabilistic model of how a system moves through a finite set of states over discrete time. Its defining feature is that the next state depends only on the current state, not on the full history.
For a sequence of states \(\pi_1, \pi_2, \ldots, \pi_n\), \(P(\pi_i \mid \pi_1, \ldots, \pi_{i-1}) = P(\pi_i \mid \pi_{i-1})\). Only the previous state matters. This memoryless property is what makes the model tractable.
Transition matrix \(A\)
Entry \(a_{ij} = P(\pi_t = j \mid \pi_{t-1} = i)\) is the probability of moving from state \(i\) to state \(j\). Rows sum to 1. Estimated from counts in historical data or from domain knowledge.
Initial distribution \(\pi\) (a.k.a. \(A_0\))
A vector \(\pi(s) = P(\text{start in } s)\). Combined with \(A\), it lets us compute the probability of any state sequence.
Weather example
Three states: Rainy, Cloudy, Sunny. From the row "Sunny" of \(A\): \(P(\text{Sunny} \mid \text{Sunny}) = 0.8\), \(P(\text{Rainy} \mid \text{Sunny}) = 0.1\), \(P(\text{Cloudy} \mid \text{Sunny}) = 0.1\). The next day's weather depends only on today.
Sequence probability
\(P(\pi_1, \ldots, \pi_k) = P(\pi_1)\prod_{i=1}^{k-1} P(\pi_{i+1} \mid \pi_i)\). E.g. \(P(\text{S, S, C, R}) = 0.1 \cdot 0.8 \cdot 0.1 \cdot 0.2 = 0.0016\).
As a graph
Nodes are states; directed edges carry transition probabilities. A "Start" node with weights \(\pi(s)\) feeds the chain. Useful diagram for spotting absorbing states or unreachable states.
Hidden Markov Models: observations from hidden states
In an HMM we cannot directly observe the underlying state — we only see indirect observations that depend on it. The lecture's running example: you are locked in a room and the only signal about today's weather is the caregiver's clothing (Shirt / Jacket / Hoodie).
A finite set of \(N\) hidden states \(\{s_1, \ldots, s_N\}\); a set of observation symbols \(\{v_1, \ldots, v_K\}\); a transition matrix \(A\) with \(a_{ij} = P(\pi_t = s_j \mid \pi_{t-1} = s_i)\); an emission matrix \(B\) (also called \(E\)) with \(b_i(v_k) = P(o_t = v_k \mid \pi_t = s_i)\); and an initial distribution \(\pi\) (the slides call it \(A_0\)).
Weather HMM
Hidden states: Rainy, Cloudy, Sunny. Observations: Shirt, Jacket, Hoodie. The emission matrix \(B\) tells how likely each garment is given today's true weather, e.g. \(b_{\text{Sunny}}(\text{Hoodie}) = 0.79\).
Chess example (Kubat)
Hidden states: strong / weak opponent. Observations: win / lose / draw. The mother only sees results; from the sequence and a known \(\lambda\) she can infer opponent strength.
Problem 1 - Evaluation
Given \(\lambda\) and observation sequence \(O\), compute \(P(O \mid \lambda)\). Solved by the Forward algorithm.
Problem 2 - Decoding
Given \(\lambda\) and \(O\), find the most likely hidden state sequence \(\arg\max_Q P(Q \mid O, \lambda)\). Solved by Viterbi.
Problem 3 - Learning
Given only an observation sequence \(O\), estimate \(\lambda = (A, B, \pi)\). Solved by Baum-Welch, an EM algorithm.
Problem 1 — Evaluation with the Forward algorithm
We want \(P(O \mid \lambda)\) for a given observation sequence. A naive enumeration over all \(N^T\) hidden paths costs roughly \(2T\,N^T\) multiplications — infeasible for long sequences. The Forward algorithm exploits dynamic programming to bring this down to \(O(N^2 T)\).
\(f_k(i)\) is the probability of having seen \(o_1, \ldots, o_i\) and being in state \(k\) at time \(i\). The recurrence is \(f_k(i) = b_k(o_i) \sum_j f_j(i-1)\, a_{jk}\), summed over all predecessor states \(j\).
Step 1 — Initialise
\(f_k(1) = \pi_k\, b_k(o_1)\) for each state \(k\). Combine the prior of state \(k\) with the chance it emitted the first observation.
Step 2 — Recurse
For \(t = 2, \ldots, T\), \(f_k(t) = b_k(o_t) \sum_j f_j(t-1)\, a_{jk}\). Sum over all ways to reach state \(k\) from the previous step.
Step 3 — Terminate
\(P(O \mid \lambda) = \sum_k f_k(T)\). Total probability marginalises over the final hidden state.
Complexity
\(O(N^2 T)\) versus \(O(2T N^T)\) for enumeration. With \(N = 3\) states and \(T = 100\) observations, that is roughly \(900\) vs \(\sim 10^{47}\) operations.
Problem 2 — Decoding with the Viterbi algorithm
Now we want the single most likely sequence of hidden states that explains the observations. Viterbi is structurally identical to Forward except it maximises over predecessors instead of summing, and stores a backpointer so we can recover the best path.
\(V_k(i) = b_k(o_i) \max_j V_j(i-1)\, a_{jk}\) is the probability of the best path ending at state \(k\) after observing \(o_1, \ldots, o_i\). The backpointer \(\text{Ptr}_k(i) = \arg\max_j V_j(i-1)\, a_{jk}\) records which previous state made the maximum.
Forward vs Viterbi
Forward uses \(\sum\) and answers "how likely is the sequence?". Viterbi uses \(\max\) and answers "what is the best explanation?". Both are \(O(N^2 T)\) dynamic programs over the same trellis.
Trace-back
After the final step pick \(q_T = \arg\max_k V_k(T)\). Then walk backwards: \(q_{t-1} = \text{Ptr}_{q_t}(t)\) for \(t = T, \ldots, 2\). The result is the most probable hidden state sequence.
Step 1
Initialise \(V_k(1) = \pi_k\, b_k(o_1)\).
Step 2
For \(t = 2, \ldots, T\) compute \(V_k(t)\) and \(\text{Ptr}_k(t)\) for every state \(k\).
Step 3a
Pick the final state \(q_T = \arg\max_k V_k(T)\).
Step 3b
Trace back through \(\text{Ptr}\) to recover \(q_{T-1}, \ldots, q_1\).
Problem 3 — Learning with Baum-Welch (EM)
When we know only an observation sequence and not the model parameters, we must learn \(\lambda = (A, B, \pi)\). This is solved with the Baum-Welch algorithm, an instance of Expectation-Maximisation.
1. Initialise \(\lambda = (A, B, \pi)\) to random (but valid) probability distributions. 2. E step: using current \(\lambda\), compute the expected counts of state-transitions and emissions consistent with \(O\) (via forward and backward variables). 3. M step: re-estimate \(\lambda\) from those expected counts. 4. Iterate. The likelihood \(P(O \mid \lambda)\) is guaranteed to increase (or stay constant) each iteration; stop when it plateaus.
Why iterative?
Maximum likelihood for HMMs has no closed form because the hidden state sequence is unknown. EM treats the hidden states as "missing data" and alternates between filling them in (E) and refitting parameters (M).
Local optima
EM only guarantees a local optimum. Different random initialisations can converge to different solutions, so multiple restarts are common.
Connection to forward / backward
The E step uses the Forward variable \(f_k(t)\) plus a Backward variable \(\beta_k(t)\) to compute the posterior over hidden states — the same DP machinery as Problem 1.
Study questions to answer before moving on
Using the lecture's weather Markov chain with \(\pi = (P(\text{R}), P(\text{C}), P(\text{S})) = (0.6, 0.1, 0.3)\) and transition rows \(P(\cdot \mid \text{S}) = (0.1, 0.1, 0.8)\), \(P(\cdot \mid \text{C}) = (0.2, 0.6, 0.2)\), compute \(P(\text{S, S, C, R})\).
Use the Markov product: \(P(\text{S}) \cdot P(\text{S} \mid \text{S}) \cdot P(\text{C} \mid \text{S}) \cdot P(\text{R} \mid \text{C}) = 0.3 \cdot 0.8 \cdot 0.1 \cdot 0.2 = 0.0048\).
The slides use a slightly different \(\pi\) where \(P(\text{S}) = 0.1\), giving \(0.1 \cdot 0.8 \cdot 0.1 \cdot 0.2 = 0.0016\). Plug in whichever initial distribution your version of the slides uses.
For the HMM example with \(O = (\text{Shirt}, \text{Hoodie})\), confirm that \(f_{\text{Cloudy}}(2) = 0.0189\) given \(f_R(1) = 0.48\), \(f_C(1) = 0.15\), \(f_S(1) = 0.001\), the transition column for Cloudy \((0.3, 0.3, 0.4)\), and \(b_{\text{Cloudy}}(\text{Hoodie}) = 0.1\).
\(f_C(2) = 0.1 \cdot (0.48 \cdot 0.3 + 0.15 \cdot 0.3 + 0.001 \cdot 0.4) = 0.1 \cdot 0.1894 = 0.01894 \approx 0.0189\).
In the worked Viterbi example the algorithm decides the second hidden state is Sunny and the first is Rainy. Explain in words why the path Rainy → Sunny wins even though Sunny → Sunny might intuitively explain a Hoodie better.
The prior \(\pi_{\text{Sunny}}\) is small (0.1) and \(b_{\text{Sunny}}(\text{Shirt})\) is tiny (0.01), so \(V_{\text{Sunny}}(1) = 0.001\). Starting from Rainy gives \(V_R(1) = 0.48\), and even with the small transition \(a_{R \to S} = 0.1\) the product \(0.48 \cdot 0.1 = 0.048\) dominates competing predecessors, so the backpointer chooses Rainy. Viterbi balances all three of prior, transition, and emission — not just the last emission.
Chapter quizzes
Self-test and math questions for this week are in the Quiz Hub (practice or exam mode).