AI AI-03.03
Hidden Markov models
Hidden states and observations over time, the forward algorithm, Viterbi decoding on a trellis, and the HMMs behind decades of speech recognition.
The big idea
Some things you care about are never observed directly. A speech recogniser hears sound waves, not words. A fitness tracker measures wrist movement, not whether you are walking, cycling or asleep. A grammar checker sees words, not their parts of speech. In each case there is a hidden story that unfolds over time, and an observed signal that each step of the story produces, noisily.
A hidden Markov modelA probabilistic model of a sequence in which a hidden state evolves step by step (each state depending only on the previous one) and each state emits an observation. (HMM) is the simplest model of that situation. It is a Bayesian network repeated over time: each hidden state depends only on the one before, and each observation depends only on the current hidden state. From that structure come two fast algorithms: one computes how likely a sequence of observations is, and one recovers the single most likely hidden story behind it.
Imagine a friend in another city who never mentions the weather but tells you what they did each day: walked in the park, went shopping, cleaned the flat. Walks suggest sun; cleaning suggests rain; and weather tends to persist from one day to the next. From "walk, shop, clean" you can make a principled guess about the three days' weather, and an HMM makes that guess exact.
How it works
Step 1: The ingredients
An HMM has hidden states, observations, and three tables:
- Start probabilities: how likely each hidden state is on day 1. Rainy 0.6, Sunny 0.4.
- Transition probabilities : how the hidden state changes. Rain stays rain with 0.7; sun stays sun with 0.6.
- Emission probabilities : how each state produces observations. On a rainy day: walk 0.1, shop 0.4, clean 0.5. On a sunny day: walk 0.6, shop 0.3, clean 0.1.
The Markov assumption is that tomorrow depends only on today, not on the whole history. It is a simplification, and it is what makes the algorithms fast.
Step 2: The probability of one story
The probability of a particular hidden path together with the observations is a product along the path, just as in a Bayesian network. For "Sunny, Rainy, Rainy" with "walk, shop, clean":
With hidden states and days there are possible paths: 2 states over 3 days is 8 paths, but 50 states over 100 time steps is . Trying them all is out of the question.
Step 3: The trellis and dynamic programming
The trick is that paths share pieces. Every path that is Rainy on day 2 continues from day 2 in the same way, whatever happened on day 1. So for each day and each state, keep just one number that summarises all paths ending there, and build day 's numbers from day 's. Laid out as a grid of states by days, this is the trellisA grid with one column per time step and one node per hidden state, with edges for transitions; HMM algorithms fill it in column by column.:
- Day 1: walk Start probability times emission: Rainy 0.6 x 0.1 = 0.06, Sunny 0.4 x 0.6 = 0.24.
- Day 2: shop For each state, take the best predecessor. Rainy: from Sunny, 0.24 x 0.4 = 0.096, times 0.4 for shop = 0.0384. Sunny: from Sunny, 0.24 x 0.6 x 0.3 = 0.0432.
- Day 3: clean Rainy: from Rainy, 0.0384 x 0.7 x 0.5 = 0.01344. Sunny: from Sunny, 0.0432 x 0.6 x 0.1 = 0.0026.
- Backtrack The best final value is Rainy, 0.01344. Its back-pointer leads to Rainy on day 2, whose back-pointer leads to Sunny on day 1.
Step 4: The forward algorithm, summing
To find the probability of the observations, , each trellis node stores the sum over all paths ending there:
Adding up the last column gives the answer. This is the forward algorithmDynamic programming over the trellis that sums the probabilities of all hidden paths, giving the total probability of an observation sequence in time proportional to T times N squared., and it costs steps instead of . A speech recogniser used it to score how well each candidate word's model explains a stretch of audio.
Step 5: The Viterbi algorithm, maximising
To find the single most likely hidden path, replace the sum with a max, and remember which predecessor gave the max (a back-pointer). That is the Viterbi algorithmDynamic programming over the trellis that keeps, for each state and time, the probability of the best path ending there and a back-pointer, then traces back the single most likely hidden sequence., and it is what Figure 1 steps through. At the end, start from the best node in the last column and follow the back-pointers.
Try it
Both algorithms on the weather example, with the Viterbi table printed day by day:
# Hidden weather, observed activity: a friend far away tells you only
# what they did each day. Guess the weather behind it.
STATES = ["Rainy", "Sunny"]
START = {"Rainy": 0.6, "Sunny": 0.4}
TRANS = {"Rainy": {"Rainy": 0.7, "Sunny": 0.3},
"Sunny": {"Rainy": 0.4, "Sunny": 0.6}}
EMIT = {"Rainy": {"walk": 0.1, "shop": 0.4, "clean": 0.5},
"Sunny": {"walk": 0.6, "shop": 0.3, "clean": 0.1}}
OBS = ["walk", "shop", "clean"]
def forward(obs):
"""P(observations): sum over every hidden path, one day at a time."""
alpha = {s: START[s] * EMIT[s][obs[0]] for s in STATES}
for o in obs[1:]:
alpha = {s: EMIT[s][o] *
sum(alpha[r] * TRANS[r][s] for r in STATES)
for s in STATES}
return sum(alpha.values())
def viterbi(obs):
"""Most likely hidden path: like forward, but max instead of sum."""
delta = {s: START[s] * EMIT[s][obs[0]] for s in STATES}
back = []
show = lambda s: f"{s} {delta[s]:.4f}"
print(f" day 1 {obs[0]:5}: " + " ".join(map(show, STATES)))
for day, o in enumerate(obs[1:], 2):
prev = {s: max(STATES, key=lambda r: delta[r] * TRANS[r][s])
for s in STATES}
delta = {s: delta[prev[s]] * TRANS[prev[s]][s] * EMIT[s][o]
for s in STATES}
back.append(prev)
print(f" day {day} {o:5}: " + " ".join(
f"{s} {delta[s]:.4f} (from {prev[s]})" for s in STATES))
last = max(STATES, key=delta.get)
path = [last]
for prev in reversed(back): # follow the back-pointers
path.insert(0, prev[path[0]])
return path, delta[last]
print(f"P(walk, shop, clean) = {forward(OBS):.6f}")
print("Viterbi table (best path probability ending in each state):")
path, p = viterbi(OBS)
print(f"most likely weather: {' -> '.join(path)} (p = {p:.5f})")Output
P(walk, shop, clean) = 0.033612
Viterbi table (best path probability ending in each state):
day 1 walk : Rainy 0.0600 Sunny 0.2400
day 2 shop : Rainy 0.0384 (from Sunny) Sunny 0.0432 (from Sunny)
day 3 clean: Rainy 0.0134 (from Rainy) Sunny 0.0026 (from Sunny)
most likely weather: Sunny -> Rainy -> Rainy (p = 0.01344) The probability of seeing "walk, shop, clean" at all is 0.0336, summed over all 8 weather paths. The most likely single path is Sunny, Rainy, Rainy with probability 0.01344, matching Figure 1. Notice day 2: on its own, "shop" is slightly more likely on a rainy day (0.4 against 0.3), but the Viterbi table at day 2 favours Sunny (0.0432 against 0.0384) because the walk on day 1 made sun likely and sun tends to persist. The final decision flips day 2 to Rainy only once day 3's "clean" is seen. HMM decoding is about the whole sequence, not each step in isolation.
Going deeper
Filtering, smoothing and learning
Other questions use the same trellis. Filtering asks for the current state given everything so far (the normalised forward values), which is what a tracker does in real time. Smoothing asks about a past state given the whole sequence, combining a forward pass with a backward pass. And when the tables are unknown, the Baum-Welch algorithm, a case of expectation maximisation, estimates them from unlabelled observation sequences by alternating between inferring hidden states and re-counting.
Speech, tagging and genes
For decades, speech recognition was built on HMMs: each word or sound unit was a small HMM whose hidden states were stages of the sound and whose observations were acoustic features, with the Viterbi algorithm searching for the best word sequence. Part-of-speech taggers used HMMs with tags as hidden states and words as observations, and gene-finding programs use them to label stretches of DNA as coding or non-coding. The Viterbi algorithm itself was introduced in 1967 for decoding error-correcting codes and is still used in digital communications.
What replaced them
The Markov assumption is the HMM's weakness: one hidden state must carry everything relevant about the past, and emissions depend only on the current state. Conditional random fields relaxed the second assumption; recurrent neural networks and then transformers ( Self-attention, step by step ) dropped the first, learning long-range context directly. In speech recognition, neural models first replaced the HMM's emission tables and then, in end-to-end systems, the HMM itself. The trellis idea survives: dynamic programming over sequence alignments (as in the CTC loss) and beam search over sequences ( Local search and optimization ) are its descendants.
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| Hidden Markov model | Small data, interpretable states, fast exact inference with forward and Viterbi | Markov assumption; one hidden state must summarise the whole past |
| Brute-force over all paths | Tiny problems, checking an implementation | N^T paths: impossible beyond toy sizes |
| Neural sequence models (RNNs, transformers) | Long-range context and large datasets | Need much more data and compute; harder to interpret |
Common mistakes
- Taking the most likely state at each step separately and calling it the most likely path. The per-step choices can form a path that is unlikely, or even impossible, as a whole.
- Multiplying many small probabilities directly. Long sequences underflow to zero; real implementations add log probabilities instead.
- Confusing transition and emission tables. Transitions link hidden states over time; emissions link a hidden state to what is observed.
- Assuming the hidden states learned by Baum-Welch mean what you hoped. They are whatever best explains the data and may need interpretation.
In the wild
Where you will see this: HMMs powered speech recognition and dictation software for decades, and are still used in bioinformatics for gene finding and protein family models, in activity recognition from wearable sensors, and in finance to model switches between market regimes. The Viterbi algorithm runs in mobile phones, satellite links and disk drives to decode error-correcting codes.
Check yourself
-
In an HMM, what does the transition table describe?
Show answer
B. How the hidden state changes from one step to the next Transitions link hidden states over time; emissions link hidden states to observations.
-
What is the difference between the forward and Viterbi algorithms?
Show answer
B. Forward sums over paths to get P(observations); Viterbi takes the max to find the single best path Both fill the same trellis; replacing the sum with a max (plus back-pointers) turns one into the other.
-
An HMM has 10 hidden states and the sequence has 50 steps. Roughly how much work does Viterbi do?
Show answer
B. 50 x 10 x 10 = 5,000 steps Each of T steps considers N predecessors for each of N states: T x N^2.
-
Why can the most likely state at each step, chosen separately, differ from the Viterbi path?
Show answer
B. Because the best path depends on transitions between steps, which per-step choices ignore Viterbi optimises the whole sequence jointly. In the example, day 2 looks sunny on its own but is rainy on the best path.
Recap
- An HMM has hidden states that change over time (transitions) and emit observations (emissions).
- The Markov assumption, each state depends only on the previous one, makes inference fast.
- The trellis holds one number per state per time step; dynamic programming fills it in T x N^2 steps.
- The forward algorithm sums over paths to score observations; Viterbi maximises to recover the best hidden path.
- HMMs powered speech recognition and tagging for decades before neural sequence models replaced them.