Introduction
Many problems involve a state you cannot see that changes over time: the weather outside a windowless office, the word someone is saying, the position of a robot, whether a machine is wearing out. What you can see are noisy observations: whether people carry umbrellas, a sound wave, a laser reading. A hidden Markov model (HMM) connects the two and lets an agent keep an up-to-date belief about the hidden state.
How it works
An HMM has:
- hidden states, such as Rain and Dry;
- a transition model P(Xₜ | Xₜ₋₁): rain tends to follow rain;
- a sensor model P(Eₜ | Xₜ): umbrellas are likely when it rains;
- a prior P(X₀).
It assumes the Markov property: today's state depends only on yesterday's, and today's observation depends only on today's state.
Prediction without observations multiplies the belief by the transition model step by step; for a Markov chain that is all there is.
Filtering keeps P(Xₜ | e₁…eₜ) up to date with two steps per observation:
- predict: P(Xₜ = s) = Σᵣ P(Xₜ₋₁ = r) P(s | r);
- update: multiply by P(eₜ | s) and normalize.
This is the forward algorithm. The cost per step depends only on the number of states, so it can run forever.
The most likely explanation, the single sequence of states that best explains all the observations, needs a different recursion: the Viterbi algorithm. It keeps, for each state, the probability of the best path ending there, and updates it with max instead of sum: best(s) = P(e | s) · maxᵣ best(r) P(s | r). It also remembers which r gave the max, so the best path can be read back at the end.
Syntax
predicted = {s: sum(belief[r] * T[r][s] for r in states) for s in states}
weights = {s: predicted[s] * E[s][obs] for s in states}
belief = {s: w / sum(weights.values()) for s, w in weights.items()} # filtering
best[s] = E[s][obs] * max(best[r] * T[r][s] for r in states) # Viterbi
Example
STATES = ["Rain", "Dry"]
transition = {"Rain": {"Rain": 0.7, "Dry": 0.3}, "Dry": {"Rain": 0.3, "Dry": 0.7}}
sensor = {"Rain": {"umbrella": 0.9, "none": 0.1}, "Dry": {"umbrella": 0.2, "none": 0.8}}
prior = {"Rain": 0.5, "Dry": 0.5}
seen = ["umbrella", "umbrella", "none", "umbrella", "umbrella"]
belief = dict(prior)
print("filtering, P(rain today | everything seen so far):")
for day, obs in enumerate(seen, start=1):
predicted = {s: sum(belief[r] * transition[r][s] for r in STATES) for s in STATES}
weights = {s: predicted[s] * sensor[s][obs] for s in STATES}
total = sum(weights.values())
belief = {s: w / total for s, w in weights.items()}
print(f" day {day} ({obs}): {belief['Rain']:.4f}")
best = {s: sum(prior[r] * transition[r][s] for r in STATES) * sensor[s][seen[0]] for s in STATES}
paths = {s: [s] for s in STATES}
for obs in seen[1:]:
new_best, new_paths = {}, {}
for s in STATES:
came_from = max(STATES, key=lambda r: best[r] * transition[r][s])
new_best[s] = best[came_from] * transition[came_from][s] * sensor[s][obs]
new_paths[s] = paths[came_from] + [s]
best, paths = new_best, new_paths
last = max(STATES, key=lambda s: best[s])
print("most likely weather (Viterbi):", " ".join(paths[last]))
print(f" probability of that sequence with these observations: {best[last]:.6f}")Line by line
- Rain tends to last (0.7), and umbrellas appear on 90% of rainy days but also 20% of dry ones.
- Each filtering step predicts from yesterday's belief, multiplies by the chance of today's observation and normalizes.
- Two umbrella days make rain likely; a day without umbrellas makes it unlikely; two more umbrella days raise it again.
- Viterbi keeps the best path into each state and extends it one day at a time.
- The most likely sequence is rain, rain, dry, rain, rain: the day without umbrellas is best explained as a dry day.
Expected result
filtering, P(rain today | everything seen so far):
day 1 (umbrella): 0.8182
day 2 (umbrella): 0.8834
day 3 (none): 0.1907
day 4 (umbrella): 0.7308
day 5 (umbrella): 0.8673
most likely weather (Viterbi): Rain Rain Dry Rain Rain
probability of that sequence with these observations: 0.011574
In the real world
Speech recognition used HMMs for decades, with phonemes as hidden states and sound features as observations. Gene finders label DNA with HMMs, GPS receivers and robots filter positions with the same predict-update cycle (the Kalman filter is its continuous version), and mobile keyboards once used Viterbi to decode swipes into words.
Common mistakes
- Updating before predicting, which skips the transition.
- Forgetting to normalize, so beliefs shrink towards zero over long sequences.
- Taking the most likely state at each step as the most likely sequence: Viterbi's answer can differ.
- Underflow on long sequences: the Viterbi probabilities become tiny, so real systems add logarithms instead of multiplying.
Best practices
- Check that every row of the transition and sensor tables sums to 1.
- Work through two steps by hand before trusting the code.
- Use logarithms for long sequences in Viterbi.
Summary
A hidden Markov model links hidden states through a transition model and to observations through a sensor model. Filtering predicts with the transition model, updates with the sensor model and normalizes, one step at a time. The Viterbi algorithm replaces sum with max to find the most likely sequence of hidden states.
Quick check
Key takeaways
- Filtering repeats two steps: predict with the transition model, then update with the sensor model and normalize.
- Viterbi is the same recursion with max instead of sum, plus a record of which state each best path came from.
- Both take time proportional to the number of steps, not exponential in it.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.