4.14 Hidden Markov models

What this is and why it exists

A hidden Markov model describes a process you cannot see through observations you can. That structure fits an enormous range of problems — speech, handwriting, biological sequences, machine condition, part-of-speech tagging — and it powered speech recognition for decades. It is also the clearest possible account of what a sequence model is doing, which makes it worth knowing even where you would now use something else.

The vocabulary

• Hidden state — the thing you care about and cannot observe directly.
• Observation — what you can see, produced by the hidden state.
• Markov assumption — the next hidden state depends only on the current one.
• Transition probability — the chance of moving from one hidden state to another.
• Emission probability — the chance of a hidden state producing a given observation.
• Initial distribution — how likely each hidden state is at the start.
• Evaluation, decoding, learning — the three classic problems.
• Dynamic programming — solving a problem by reusing solutions to overlapping subproblems.

The mental model

The structure is a chain you cannot see, producing signs you can. At each time step the process is in one of a fixed set of hidden states, and it emits one observation. Then it moves to a hidden state for the next step. You see the observations; you never see the states.

Three sets of numbers define the model. Transition probabilities: given the current hidden state, how likely is each next one. Emission probabilities: given a hidden state, how likely is each observation. An initial distribution over the first hidden state. And one assumption underlies all of it — the next state depends only on the current state, not on the whole history — which is what makes everything computable and is also the model's main simplification.

A worked picture makes it concrete. The weather is the hidden state, sunny or rainy, and you are in a windowless room; the observation is whether the person who comes in each day carries an umbrella. Umbrellas are more likely on rainy days and not certain either way, and weather persists — rainy days follow rainy days more often than not. From a sequence of umbrellas you infer a sequence of weather, and the model says exactly how.

Three problems define the subject, and keeping them distinct is most of the topic.

Evaluation: how likely is this observation sequence under this model? Useful for choosing between models — build one model per word and ask which makes the sound you heard most likely.

Decoding: which hidden sequence best explains these observations? This is the one that gives you an answer about the world.

Learning: given observations and no state labels, what transition and emission probabilities fit the data? Solved by an iterative procedure that alternates between estimating the hidden states with current parameters and re-estimating the parameters from those estimates, improving the fit each round and converging to a local optimum rather than a global one — so the starting point matters.

The forward algorithm answers evaluation, and its trick is reuse. The naive approach sums the probability over every possible hidden sequence, and there are as many of those as the number of states raised to the length of the observation sequence — hopeless beyond a few steps.

The insight is that all sequences ending in the same state at the same time can be summarised by one number. So compute, for each state and each time step, the total probability of having produced the observations so far and being in that state now. Get that for one time step and the next follows: for each state, add up the previous step's numbers weighted by the transition probabilities into it, then multiply by the emission probability for what you actually observed. Work is now proportional to the length times the square of the number of states, instead of exponential.

Do it by hand on a short sequence, because the reuse only becomes visible in the doing. Draw a grid: one row per hidden state, one column per time step. Fill the first column from the initial distribution times the emission probabilities for the first observation. Fill each later column from the one before it, one cell at a time. Add the final column and you have the answer. The grid is the algorithm, and after you have filled one you will never again find these methods mysterious.

Viterbi answers decoding, and the difference from forward is one operation. Instead of adding over the ways to arrive in a state, take the maximum — and record which predecessor gave it. At the end, take the best final cell and follow the recorded predecessors backwards to recover the whole sequence. Adding gives you total probability; maximising gives you the single best path.

The distinction that gives this algorithm its point is between the most likely state at each moment and the most likely sequence overall, which are different things. Choosing the most likely state independently at each step can produce a sequence the model says is impossible — the individually best state at one step may have no transition to the individually best state at the next. Viterbi finds the best complete sequence, which is coherent by construction. If that reasoning sounds familiar, it is the same argument the sequence-labelling topic made about structured prediction, and this is the algorithm underneath it.

One practical note that matters in implementation: multiplying many small probabilities underflows to zero. Work with logarithms and add rather than multiply — the maximising step is unaffected, and the whole method becomes numerically stable.

Why did speech recognition reach for this first? Because speech is exactly this structure. What you want is a sequence of hidden linguistic units — phonemes, words — and what you have is a noisy acoustic signal produced by them. The hidden states are the linguistic units, the transitions are how likely one unit follows another, and the emissions are how likely a piece of sound is given the unit being spoken. The fit is so close that it is nearly a definition, and the field built on it for decades: emissions modelled from acoustic features, transitions from pronunciation dictionaries, and the language model contributing further transition structure.

What replaced it was models that learn the representation and the transitions together, without the assumption that the next state depends only on the current one and without hand-designed acoustic features. But the questions did not change — how likely is this sequence, and which hidden sequence explains it — and that is why this model remains the clearest way to see what a sequence model is doing. When a neural sequence model produces an output, it is answering the decoding question with a richer notion of state, and the reason a coherence-enforcing layer helps it is the reason Viterbi exists.

What you should now be able to explain or do

Describe hidden states, observations, transitions and emissions, and state the Markov assumption. Name the three classic problems and say what each is for. Explain why enumerating all hidden sequences is hopeless and what the forward algorithm reuses. Fill a forward grid by hand on a short sequence. Run Viterbi and say which single operation differs from forward. Explain why the most likely state at each moment is not the most likely sequence. Use logarithms to avoid underflow. Say why speech recognition fitted this model and what changed when it was replaced.

Check yourself