COMP4318 · Machine Learning and Data Mining
Markov Models & Hidden Markov Models
Week 11 covers sequence models: Markov chains and the Markov property, hidden Markov models (states, emissions, transitions), and the inference algorithms — the Forward algorithm for an observation's probability and Viterbi for the most likely state sequence. Both sample exam papers include an HMM question, so the Forward/Viterbi recurrences are prime material; a Markov-chain sequence-probability calculation is a common lead-in. The homework quiz (h11) drills them.
What this chapter covers
- 01Markov property: P(πₜ | π₁…πₜ₋₁) = P(πₜ | πₜ₋₁); transition matrix A and initial distribution A0
- 02Sequence probability P(π1,…,πK) = P(π1)·Π P(πᵢ₊₁ | πᵢ)
- 03Hidden Markov Model λ = (states, A, A0, emission matrix E); the states are hidden, only observations are seen
- 04Problem 1 (Evaluation): probability of an observation sequence via the Forward algorithm
- 05Forward recurrence: fₖ(1) = A0(k)·eₖ(x1); fₖ(i) = eₖ(xᵢ)·Σⱼ fⱼ(i−1)·aⱼₖ; P(X) = Σₖ fₖ(m)
- 06Problem 2 (Decoding): most likely hidden-state sequence via Viterbi (max instead of sum, plus back-pointers)
- 07Problem 3 (Learning): estimate the model λ from observations via EM
- 08Complexity N²T for Forward/Viterbi versus naïve path enumeration; applications in POS tagging, speech and bioinformatics
Probability of a state sequence in a Markov chain
- +1Use the Markov factorisation P(π1,π2,π3) = P(π1)·P(π2|π1)·P(π3|π2) — each state depends only on the previous one.
- +1Substitute: P(Sunny)·P(Sunny|Sunny)·P(Rainy|Sunny) = 0.6·0.8·0.2.
- +1Multiply: 0.6·0.8 = 0.48; 0.48·0.2 = 0.096.
Key terms
- Markov property
- The assumption that the next state depends only on the current state, not the earlier history: P(πₜ | π₁…πₜ₋₁) = P(πₜ | πₜ₋₁).
- Transition matrix
- The matrix A with aᵢⱼ = P(next = j | current = i) giving the probabilities of moving between states; paired with an initial distribution A0.
- Hidden Markov Model
- A Markov chain whose states are hidden and emit observations via an emission matrix E; defined by λ = (states, A, A0, E).
- Emission probability
- eₖ(x) = P(observation x | state k); how likely each hidden state is to produce each observation.
- Forward algorithm
- Dynamic programming that sums over all state paths to give the probability of an observation sequence: fₖ(i) = eₖ(xᵢ)·Σⱼ fⱼ(i−1)·aⱼₖ, then P(X) = Σₖ fₖ(m).
- Viterbi algorithm
- Like the Forward algorithm but taking the max instead of the sum and storing back-pointers, to recover the single most likely hidden-state sequence.
Markov Models & Hidden Markov Models FAQ
What makes a model 'Markov'?
The Markov property: the future depends only on the present state, not on how you got there. So the probability of the next state is conditioned only on the current one, which is what lets you multiply one-step transition probabilities to score a whole sequence.
Forward vs Viterbi — when do I use each?
Use the Forward algorithm to compute the probability of an observation sequence (Problem 1, Evaluation) — it sums over all hidden-state paths. Use Viterbi to find the single most likely hidden-state sequence (Problem 2, Decoding) — it is the same recurrence but takes a max instead of a sum and keeps back-pointers so you can trace the path back.
What's the difference between a Markov chain and a hidden Markov model?
In a Markov chain the states are observed directly, so you can read off the sequence and multiply transition probabilities. In a hidden Markov model the states are hidden and you only see observations emitted by them (via the emission matrix), so you need the Forward algorithm to score observations and Viterbi to infer the likely states.
How much of the exam is Markov models?
Both mined sample papers include an HMM question, so the Forward and Viterbi recurrences and a Markov-chain sequence probability are worth rehearsing thoroughly. Confirm the exact weighting on Canvas and the unit outline, since the paper's structure can vary between offerings.
Exam move
Learn the two recurrences as a matched pair: Forward (sum over previous states, fₖ(i) = eₖ(xᵢ)·Σⱼ fⱼ(i−1)·aⱼₖ) for the probability of an observation sequence, and Viterbi (max plus back-pointer) for the most likely state path. Rehearse a small two- or three-step HMM by hand, filling a trellis column by column, and practise a Markov-chain sequence probability as the warm-up. Keep 'sum for probability, max for path' as your one-line memory hook. When a trellis column comes out wrong, ask Sia to recompute it step by step and check your transitions and emissions.
Working through Markov Models & Hidden Markov Models in COMP4318? Sia is AskSia’s AI Machine Learning tutor — ask any COMP4318 Markov Models & Hidden Markov Models question and get a clear, step-by-step explanation grounded in how COMP4318 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
