Hidden Markov Models
A Hidden Markov Model (HMM) is a graphical model for sequences where the thing you care about is hidden and you only see noisy evidence of it. The weather (hidden) drives whether someone carries an umbrella (observed); the spoken phoneme (hidden) drives the audio waveform (observed). HMMs were the workhorse of speech recognition and bioinformatics for decades.
Real-world examples: Speech recognition, part-of-speech tagging, gene finding, gesture recognition, financial regime detection, decoding DNA.
Two assumptions
An HMM has a chain of hidden states and observations , built on two Markov assumptions:
- Markov property: the next hidden state depends only on the current one: .
- Output independence: each observation depends only on the current hidden state: .
These give the joint:
The three matrices
| Symbol | Name | Meaning |
|---|---|---|
| Initial distribution | ||
| Transition matrix | ||
| Emission matrix |
Intuition
Picture a person in a windowless room (you can't see the weather = hidden state) who each day carries an umbrella or not (the observation). Rainy days transition to rainy days often (), and rain makes umbrellas likely (). From a week of umbrella sightings alone, you can infer the hidden weather sequence.
Three classic problems
Every HMM use case is one of these three, each with a dynamic-programming algorithm:
| Problem | Question | Algorithm |
|---|---|---|
| 1. Likelihood | : how probable is this sequence? | Forward |
| 2. Decoding | Most likely hidden path | Viterbi |
| 3. Learning | Best from data | Baum–Welch (EM) |
Problem 1: the Forward algorithm
Naively, sums over hidden paths — exponential. The forward algorithm does it in by caching :
Then . This is dynamic programming: reuse the sum over all paths ending in each state rather than re-enumerating paths.
Problem 2: Viterbi decoding
Viterbi finds the single most likely hidden sequence. It's the forward recursion with replaced by , plus back-pointers to reconstruct the path:
Sum vs max
Forward and Viterbi are the same recursion with one operator swapped. Forward sums over paths (total probability of the evidence); Viterbi maximizes over paths (the best explanation). Back-pointers in Viterbi let you trace the winning path backward at the end.
Worked example: Viterbi by hand
States , . Transitions . Emissions for : Rainy , Sunny . Observe Walk → Shop.
Step 1 (Walk): , .
Step 2 (Shop), Rainy: (came from Sunny). Step 2, Sunny: (came from Sunny).
Winner at : Sunny (), back-pointer → Sunny. Best path: Sunny → Sunny.
Backpointer table (tracking the best path)
| Time step | Observation | Rainy (, from) | Sunny (, from) |
|---|---|---|---|
| Walk | 0.06, — | 0.24, — | |
| Shop | 0.0384, Sunny | 0.0432, Sunny |
The highest score at is , so we start back-tracking from Sunny. Reading the path backwards from the highest final state: . In our example this gives the state sequence Sunny → Sunny: at the winner is Sunny, and its back-pointer records it came from Sunny at .
To reconstruct the path in code, store at every step. At the end, find , then follow the back-pointers: . This single backward pass recovers the complete optimal sequence in time — no additional computation beyond what the forward pass already stored.
Step through the decoder
The same numbers as the table above, one lattice cell at a time — every incoming candidate scored, the max taken, the loser discarded, and a backpointer stored:
Viterbi — max over paths, and the backpointers that reconstruct one
A two-state weather HMM — Rainy or Sunny — where you never see the weather, only what someone did: Walk, Shop or Clean. The observations are Walk → Shop. Viterbi answers one specific question: **which single hidden sequence is most probable?**
| Rainy | Sunny | |
|---|---|---|
| Rainy | 0.70 | 0.30 |
| Sunny | 0.40 | 0.60 |
| Walk | Shop | Clean | |
|---|---|---|---|
| Rainy | 0.10 | 0.40 | 0.50 |
| Sunny | 0.60 | 0.30 | 0.10 |
Viterbi decoding on the Rainy/Sunny HMM worked by hand above, cell by cell: every incoming candidate scored, the max taken, the loser discarded, and a backpointer stored so the winning path can be walked back at the end. The last step swaps max for sum — the forward algorithm — on the identical lattice, and the per-step argmax disagrees with the best whole path. That disagreement is the whole reason both algorithms exist.
What to notice as you step:
- The loser is discarded permanently. When picks the Sunny predecessor, the Rainy-to-Rainy path is gone for good. That pruning is what makes the recursion instead of , and it is only valid because the Markov property guarantees no discarded prefix could ever be rescued by a later observation.
- is not a probability of a state. It is the score of one complete best-path-so-far. The brute-force enumeration step confirms it: equals the joint probability of the single best path, not the marginal.
- The final step swaps
maxforsum: that one change is the forward algorithm, and the answers diverge on identical numbers. says Rainy is the more likely state at ; says the best path ends in Sunny. Per-step argmax and best-whole-path are genuinely different questions, which is why Viterbi bothers with backpointers at all.
Viterbi Algorithm — Weather / Ice Cream HMM
States: Hot (orange), Cold (indigo), Neutral (yellow). Click Step to fill one column. Back-pointer arrows (→) show which previous state maximised the probability. The teal path is the optimal decoded sequence.
import numpy as np
from hmmlearn import hmm # pip install hmmlearn
model = hmm.CategoricalHMM(n_components=2)
model.startprob_ = np.array([0.6, 0.4])
model.transmat_ = np.array([[0.7, 0.3],
[0.4, 0.6]])
model.emissionprob_ = np.array([[0.1, 0.4, 0.5], # Rainy: Walk/Shop/Clean
[0.6, 0.3, 0.1]]) # Sunny
obs = np.array([[0], [1]]) # Walk, Shop
logprob, states = model.decode(obs, algorithm="viterbi")
print("best hidden path:", states) # -> [1 1] = Sunny, Sunny
print("log P:", round(logprob, 3))
Problem 3: Baum–Welch (learning)
When you have observation sequences but no hidden labels, Baum–Welch (an instance of the EM algorithm) estimates . It alternates an E-step (run forward and backward passes to compute how responsible each state and transition is for the data) with an M-step (re-estimate all parameters as normalized expected counts), repeating until the likelihood converges to a local optimum. It is the same E/M loop as Gaussian Mixture Models — HMMs are essentially "GMMs with a Markov chain tying the components across time."
HMM as a graphical model
An HMM is just a specific Bayesian Network: a chain with each . Everything from the Bayesian Networks lesson applies — the forward/backward passes are belief propagation specialized to a chain.
Underflow: work in log space
Multiplying many probabilities underflows to 0 fast. Real implementations run the forward/Viterbi recursions in log space (sums of log-probs, logsumexp for the forward sum), or rescale at each step. hmmlearn does this for you.
Limits and what replaced HMMs
HMMs assume discrete hidden state and a strict Markov chain. For richer dependencies and continuous representations, RNNs/LSTMs and Transformers (earlier courses) largely superseded HMMs in speech and NLP, but HMMs remain valuable when data is scarce, interpretability matters, or the Markov structure is genuinely correct (e.g. bioinformatics).
Exercise
Which two assumptions define a Hidden Markov Model?
Need a hint?
One is about hidden states, one about observations.
Exercise
What is the key difference between the Forward algorithm and the Viterbi algorithm for HMMs?
Need a hint?
One sums over paths, the other maximizes.
Exercise
The Baum-Welch algorithm for learning HMM parameters is an instance of which general algorithm?
Need a hint?
It alternates an E-step and an M-step.
Common mistakes
- Confusing Forward with Viterbi: Forward sums (likelihood); Viterbi maximizes (best path). Don't use one for the other's question.
- Multiplying probabilities in linear space: underflow; use logs.
- Expecting a global optimum from Baum–Welch: it's EM, so it finds a local optimum; use multiple random restarts.
Key takeaways
- An HMM has hidden states (Markov chain) emitting observations.
- Forward sums over paths (likelihood); Viterbi maximizes (best path).
- Baum-Welch learns the parameters. It is EM for sequences.
- Work in log space to avoid underflow.
Related concepts
- Bayesian Networks: the graphical model HMMs specialize
- The EM Algorithm: the EM algorithm behind Baum-Welch
- Recurrent Neural Networks: the neural approach to sequence modeling