Hidden Markov models
A robot wakes up in a corridor and does not know which cell it is in. It has no GPS, only a cheap sensor that occasionally lies, and a motor that occasionally slips. It takes a step, reads the sensor, takes a step, reads again, and after a few readings a picture forms: a distribution over where it is, sharpening as evidence accumulates. Nothing in that story is exotic, yet it already contains the two central algorithms of this part. Hidden Markov models say that a sequence of noisy observations is generated by an underlying sequence of states you never see, states that wander according to a Markov chain and colour each observation they touch. Inferring those states is what forward–backward does, and it produces a probability distribution over every position at every time. Finding the single most probable whole sequence is what Viterbi does, and it produces one path. The two answers are different, they are computed by different recursions, and understanding why they disagree is the whole point.
The question
What you want is the past, but all you have is the present
Suppose a hidden quantity evolves over time and you never observe it directly. A robot's cell in a corridor, a word behind an acoustic signal, a part-of-speech tag behind a sentence, a market regime behind a price, a user's intent behind a click. What you do observe is a sequence of measurements, each one correlated with the hidden state that produced it but corrupted by noise. From the measurement sequence alone, what can you say about the hidden sequence?
There are two very different questions hiding in that sentence, and confusing them is the most common mistake in the subject. The first asks, at each time $t$ separately, for the probability distribution over the hidden state given everything you saw, before and after that step. That is a per-step answer, a full distribution over states, and it is the object a filter or a localiser reports. The second asks for the single most probable hidden sequence as a whole, one path through the state space that best explains the entire measurement stream. That is a single answer, and it is often the one you want when you have to commit to a story — decode a sentence, reconstruct a track, segment a signal.
These two questions usually have different answers. The best whole sequence is not the sequence of individually most likely states, because a state that is most likely at one time may force an unlikely transition from the state chosen the time before. A path pays for its transitions; a marginal does not. Once you see that, the two famous algorithms of this part stop looking like variations on one theme and start looking like answers to two questions that only resemble each other.
This part builds the model first, then the machinery. Forward–backward fills a trellis of probabilities cell by cell and gives you the per-step marginals; Viterbi runs a max where forward–backward runs a sum and gives you the single best path; and a readout compares the two on the same data so the disagreement is visible rather than asserted. Along the way the same corridor robot appears three times, because one concrete example carried all the way through beats three abstract ones.
The HMM model
A Markov chain you cannot see, colouring what you can
Write $X_t$ for the hidden state at time $t$, taking one of $K$ values, and $Y_t$ for the observation, taking one of a set of symbols. The model makes two promises and no others. The first is the Markov property: the next hidden state depends on the past only through the current state,
The second is conditional independence of the observations: conditionally on the hidden state at time $t$, the observation $Y_t$ is independent of everything else in the model, past and future alike. That gives an emission distribution $p(y_t\mid X_t=i)$, which for discrete observations is a matrix entry, and a starting distribution $\pi_i=P(X_1=i)$.
Those two assumptions are enough to write the probability of an entire hidden path and observation sequence as a product. Because the state chain is Markov and each observation is drawn from its own state alone,
The right-hand side is a chain of local factors, and that is exactly what makes the algorithms cheap. Nothing here couples a state to the whole history; every factor looks at most two neighbouring states. A brute-force search over all $K^T$ paths would multiply out this product for every path separately. The recursions in the next two sections avoid that by reusing shared subproducts, and they do it in time proportional to $TK^2$.
Two assumptions sound severe, so it is worth saying what they do not forbid. The Markov property does not say the hidden process forgets everything; it says everything about the future is already summarised in the present state. If that fails, enlarge the state until it holds — a state that remembers the last two cells, for instance, is still a Markov chain on a bigger space. The emission independence does not say the observations are independent of each other, only that once you know the hidden state they carry no further information about one another. This is why the model gets used where a hidden cause, not the measurements themselves, is the real structure. The previous part on graphical models draws exactly this factorisation as a chain, and the Markov chain part built the transition matrix on its own.
Forward–backward
Sum over the past, sum over the future, multiply
Take the first question: the distribution of $X_t$ given the complete observation sequence. The path probability above is a product over the whole chain, and the hidden variables other than $X_t$ have to be summed out. The reason the sum is cheap is that it splits cleanly at $t$ into a piece that depends only on the past and a piece that depends only on the future.
The past piece is the forward variable, the joint probability of being in state $i$ at time $t$ together with the observations up to that time. The future piece is the backward variable, the probability of the observations after $t$ given that the state at $t$ is $i$. Both satisfy simple recursions, and both read directly off the two model promises:
The forward recursion says: to be in $i$ and to have seen the data so far, you must have come from some state $j$, and the two events multiply. The backward recursion says the mirror image: from $i$ you go to some $j$, emit the next observation, and continue. The base cases are $\alpha_1(i)=\pi_i\,p(y_1\mid i)$ and $\beta_T(i)=1$. The forward pass sweeps left to right, the backward pass right to left, and each cell costs $K$ operations.
Multiply the two and normalise, and the whole path has been summed out around $t$:
The normalising constant is $P(Y_{1:T})$, the likelihood of the whole sequence. It falls out of the forward pass for free, and minimising its logarithm over the model parameters is the Baum–Welch procedure. The demo below shows the two passes filling a trellis cell by cell on the corridor robot; watch the smoothed marginals appear as bar strips only after the backward pass reaches each column.
Each column is one time step $t$ with its observed colour on top; each row is one corridor cell. Press Step: the forward pass shades a column of $\alpha$ values left to right, then the backward pass fills $\beta$ right to left. The pink bar in a cell is the smoothed marginal $\gamma_t(i)=P(X_t=i\mid Y_{1:T})$, drawn only once both passes have met that cell.
Notice what the smoothing buys you. The forward variable alone, normalised, is the filtered distribution $P(X_t\mid Y_{1:t})$: everything you know using only the data so far. The smoothed distribution $\gamma_t$ also uses the data that came later, so it is sharper and generally different. For time $t=T$ the two coincide, because there is no future; for early times the difference is largest. That is the gap between guessing where the robot is right now and reconstructing where it was, and only the second one is allowed to use the ending of the story.
Viterbi decoding
Swap the sum for a max and keep the argmax
Now the second question: the single most probable hidden sequence. The quantity to maximise is the joint probability of a path and the observations, and the joint factorises exactly as before. The crucial observation is that the maximum of a product of chained factors can be computed by the same dynamic programming sweep as the sum — replace the $\sum$ with a $\max$, and remember which predecessor achieved the maximum.
Define $\delta_t(i)$ as the probability of the best path ending in state $i$ at time $t$ and matching the observations so far. Then
with $\delta_1(i)=\pi_i\,p(y_1\mid i)$. The value $\delta_t(i)$ is the score of the best way to be in $i$ at that instant; the backpointer $\psi_t(i)$ records the state it came from. Once the whole trellis is filled, pick the state with the largest $\delta_T$ and walk the backpointers backwards. That backward walk is the backtrace: the path unrolls from the end to the beginning, one arrow at a time, and the demo animates exactly that.
The witness is worth stating precisely. Viterbi's output $x^*_{1:T}$ is the maximiser of the joint $P(x_{1:T},\,y_{1:T})$. It is not the sequence of per-step maximisers of $\gamma_t(i)$, first because the smoothed marginal is a different objective — it is conditioned on all the data and marginalised over all the other states — and second because the joint maximiser must pay for every transition, while the marginal maximiser at each step pays nothing for how it got there or where it goes next. Choosing the best state at each step independently can produce a "path" with impossible jumps. The demo below shows the max-plus trellis and the backtrace; the readout that follows compares the result against the smoothed marginals.
Cells are shaded by $\delta_t(i)$ within each column, and the small number is the backpointer $\psi_t(i)$. Press Replay backtrace to light the winning path from the last column back to the first, arrows and all.
Because the transition matrix here drifts to the right, the best path tends to advance steadily and to hug the coloured landmarks. Raise the sensor accuracy and the trellis sharpens until one column nearly always has a single bright cell; lower it and the shading flattens as the observations stop discriminating. The backtrace is what turns that landscape into a decision, and the arrows show the decision being made from the future backwards.
The robot in a corridor
When the best path and the best marginals part ways
Here is the running example in full. A robot lives in a corridor of five cells, numbered 0 to 4. Each step it drifts right with probability 0.55, stays with 0.25, and slips left with 0.20, with the walls reflecting the mass that would have left the corridor. Two cells are painted red and three blue, and the robot's colour sensor reads the true colour with probability equal to the accuracy slider and the wrong colour otherwise. The hidden state is the cell; the observation is a colour; and neither the robot nor you get to see the cell.
Forward–backward gives, at every time, a full distribution over the five cells: $P(X_t=i\mid Y_{1:T})$. That is what a localiser reports, and it is the right object when you care about uncertainty, when the answer might genuinely be a mixture, or when you intend to act on it. Viterbi gives one sequence of cells. That is the right object when you must produce a single transcript, a single track, a single segmentation.
They can disagree, and the disagreement is not a bug. The best path maximises the probability of the whole sequence, so it is willing to put a state somewhere merely plausible if that keeps the sequence coherent. The per-step marginals maximise each step alone, so they can each pick a locally very likely cell and still fail to concatenate into a legible path — often flipping between cells in a way no trajectory would. The readout below places the two side by side and marks the times where they differ.
The same trellis with two routes drawn on it: the bold solid line is the Viterbi path, the dashed line joins the per-step smoothed maxima. Red columns are the times where the two answers disagree.
Watch the colours of the disagreements. They cluster where the observation is ambiguous — near a red/blue boundary or just after a slip — and they tend to come in adjacent pairs, because a single flip in the marginals often cannot be matched by a legal transition and shows up as two. Which answer is "right" depends entirely on the question: for reporting a position on a map, smooth the marginals; for reconstructing the route the robot actually took, decode the path. Getting this distinction wrong is one of the quiet ways a probabilistic system surprises its author.
Where this shows up
The trellis is everywhere the state is hidden
Localisation along a route
A robot integrating odometry accumulates drift, and an HMM over discretised poses is the smallest honest fix: the transition model is the motion model and the emission model is the sensor. Forward–backward over the corridor is a one-dimensional relative of the full Bayes filter developed in the next part.
Decoding text and sequences
The token-by-token loop that generates a sequence in LLM serving is a search over a sequence of discrete hidden choices, and beam search is Viterbi's cousin: the same dynamic programming idea, truncated to a beam for tractability. When the objective is a whole-sequence score rather than a per-step one, you are in the max-plus world.
One layer of the chain
Strip away the observations and what remains is a Markov chain: the transition matrix, its stationary distribution, and the mixing that makes long-run behaviour forget the start. The HMM is that chain with a second, noisy layer glued on top, and the algorithms here are what you need to see through the glue.
Tracks and segmentations
Following a target through frames, smoothing a pose track, or labelling a video frame by frame are all hidden-state problems, and the same sum-product and max-product pair appears as message passing on the temporal chain. The graphical-models machinery of the previous part is the general version of what this trellis does by hand.
Cheat sheet
Every formula in one place
| Idea | Formula | Reading |
|---|---|---|
| Markov property | $P(X_{t+1}\mid X_t,\dots,X_1)=P_{X_t X_{t+1}}$ | The next state depends only on the present one. |
| Joint factorisation | $\pi_{X_1}p(y_1\mid X_1)\prod_{t\ge2}P_{X_{t-1}X_t}p(y_t\mid X_t)$ | Local factors over a chain; the reason the recursions are cheap. |
| Forward recursion | $\alpha_t(i)=p(y_t\mid i)\sum_j P_{ij}\,\alpha_{t-1}(j)$ | Past evidence flowing right; $\alpha_1(i)=\pi_i p(y_1\mid i)$. |
| Backward recursion | $\beta_t(i)=\sum_j P_{ij}\,p(y_{t+1}\mid j)\,\beta_{t+1}(j)$ | Future evidence flowing left; $\beta_T(i)=1$. |
| Smoothing | $\gamma_t(i)\propto\alpha_t(i)\beta_t(i)$ | $P(X_t=i\mid Y_{1:T})$; the normaliser is $P(Y_{1:T})$. |
| Filtering vs smoothing | $P(X_t\mid Y_{1:t})$ vs $P(X_t\mid Y_{1:T})$ | Filter uses the past only; smoothing uses both sides; equal at $t=T$. |
| Viterbi recursion | $\delta_t(i)=\max_j \delta_{t-1}(j)P_{ji}\,p(y_t\mid i)$ | Sum replaced by max; $\psi_t(i)=\arg\max_j$ keeps the predecessor. |
| Backtrace | $x^*_T=\arg\max_i\delta_T(i),\quad x^*_{t}=\psi_{t+1}(x^*_{t+1})$ | Walk the backpointers from the end to recover the best path. |
| Cost | $O(TK^2)$ time, $O(TK)$ memory | Both algorithms; the naive search is $O(K^T)$. |
Further reading
Where to go deeper
- L. R. Rabiner, "A tutorial on hidden Markov models and selected applications in speech recognition", Proceedings of the IEEE, 1989 — still the clearest full derivation of forward–backward and Viterbi, with the speech example that made the model famous.
- Christopher Bishop, Pattern Recognition and Machine Learning, chapter 13 — the HMM as a chain graphical model, with the sum-product and max-product messages stated in the same language as the previous part.
- Dan Jurafsky and James Martin, Speech and Language Processing, chapter 8 — the model from the language side, where the hidden states are tags and the Viterbi path is the parse you actually output.
- Sebastian Thrun, Wolfram Burgard and Dieter Fox, Probabilistic Robotics, chapter 7 — Markov localisation in a grid, the corridor example grown up, and the direct bridge to the Bayes filter coming next.
- Richard Durbin, Sean Eddy, Anders Krogh and Graeme Mitchison, Biological Sequence Analysis, 1998 — profile HMMs and the forward/backward algorithms as they are actually used in bioinformatics.