Skip to content
Tutorials Center
My learning

Topics

Lesson 87 of 111 ยท Beyond the Basics

Hidden Markov Models

Learn hidden Markov models with runnable NumPy code: Markov chains, the forward algorithm, Viterbi decoding and Baum-Welch training on a small weather example.

Many data sets are sequences where the thing you care about is not directly visible. You hear a series of sounds and want the words behind them. You see a person's daily activities and want to guess the weather. You read the characters of a protocol log and want to know which state the machine was in. A hidden Markov model (HMM) is a small probabilistic model for exactly this: a hidden state that changes over time, and an observation that depends on the current state.

HMMs were the standard tool for speech recognition and part-of-speech tagging before neural networks took over, and they are still a good fit when you have little data, need a model you can inspect, or want exact probabilities. They also teach three ideas that appear everywhere in sequence modeling: dynamic programming over time, the difference between filtering and decoding, and learning from data with missing labels.

Two layers

Hidden states Rainy or sunny. Never observed.
Observations Walk, shop or clean. We see these.
Transitions How the state changes day to day.
Emissions What each state tends to produce.

Both tables are probabilities.

1 / 2

From Markov chains to hidden Markov models

A Markov chain is a sequence of states where the next state depends only on the current one, not on the history. A weather chain with the states Rainy and Sunny is described by a transition matrix A, where A[i, j] is the probability of moving from state i to state j. A chain also needs a start distribution ฯ€ for the first state. That is the Markov property from Reinforcement Learning Basics, without the actions and rewards.

In a hidden Markov model you do not see the states. Each state instead produces an observation according to an emission matrix B, where B[i, k] is the probability that state i emits observation k. An HMM is therefore the triple (ฯ€, A, B):

  • ฯ€: how the sequence starts.
  • A: how the hidden state moves.
  • B: what we get to see for each state.

Our running example: the hidden state is the day's weather, and the observation is what your flatmate did that day (walk, shop or clean). Rainy days lead to cleaning, sunny days to walks.

The three classic problems

  1. Evaluation: given a model and an observation sequence, how likely is the sequence? The forward algorithm answers this.
  2. Decoding: given a model and the observations, which hidden state sequence is most likely? The Viterbi algorithm answers this.
  3. Learning: given only observation sequences, what are the best ฯ€, A and B? The Baum-Welch algorithm answers this.

The obvious way to evaluate a sequence would be to add up the probability of every possible state path. With n states and T time steps that is n^T paths, which is hopeless for long sequences. Dynamic programming reduces it to about T ยท nยฒ steps, because the probability of being in a state at time t can be built from the probabilities at time t โˆ’ 1.

Forward algorithm and Viterbi

The forward algorithm keeps alpha[t, i], the probability of the first t observations and of being in state i at time t. Each step multiplies the previous vector by the transition matrix and then by the probability of the new observation. After the last step, summing alpha gives the likelihood of the whole sequence. Real implementations rescale alpha at each step, because a product of many small probabilities underflows to zero, and they keep the logarithm of the scale factors.

Viterbi has the same shape but replaces "sum over previous states" with "take the best previous state", remembers which one was best (the back-pointers), and walks them backwards at the end. It works in log space for the same numerical reason.

The program below runs both on a five-day sequence, and checks them against brute force, which is possible only because 2โต = 32 paths is tiny.

Python Forward algorithm and Viterbi decoding

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The forward algorithm's likelihood (0.00323) matches the brute-force sum over all 32 paths. The filtered probabilities show how belief shifts day by day: the first walk makes sunshine likely (0.80), but two days of cleaning in a row push the belief to 0.91 Rainy, and the final walk turns it back to Sunny. Viterbi finds Sunny, Rainy, Rainy, Rainy, Sunny, again identical to the brute-force best path.

Notice that filtering (the best guess for each day using only data up to that day) and decoding (the best joint path using the whole sequence) can differ. Day 2 is filtered as roughly a coin flip (0.532 Rainy), but the full path calls it Rainy, because the cleaning on the following days is strong evidence.

Viterbi returns the single most probable path, not the most probable state on each day. The two answers can disagree: the best path is not always made of the individually most likely states. If you need the probability of each day's state using all the data, use the forward and backward passes together (called smoothing), which is what the next section does.

Learning the model with Baum-Welch

What if you do not know A and B? Baum-Welch learns them from observations alone. It is an instance of expectation-maximization (EM), the same idea behind Gaussian mixtures:

  1. E-step: with the current parameters, run the forward pass and a symmetric backward pass to compute how likely each state is at every time step (gamma), and how likely each state-to-state transition is (xi). These are expected counts.
  2. M-step: set the new parameters from the expected counts. For example, the new A[i, j] is the expected number of transitions i โ†’ j divided by the expected number of visits to i.

Every iteration is guaranteed not to decrease the likelihood of the data, but the process can stop at a local optimum, like k-means does, so the starting values matter. Also, the labels of the hidden states are arbitrary: the model may call "sunny" state 0, so you compare learned tables with the truth only after matching states by their emission profiles.

We generate 500 observations from a known two-state model and give the learner only the observations.

Python Baum-Welch: recover the hidden model

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The log-likelihood rises at every iteration, from -558 to about -528, and flattens out. The learned transition matrix (about 0.72/0.28 and 0.35/0.65) and emission matrix are close to the truth (0.8/0.2, 0.3/0.7, and emissions like 0.7/0.2/0.1), but not identical, because 500 points are a small sample. Decoding with the learned model recovers the hidden state on about 82% of the days, far above the 54% you would get by always guessing the commoner state.

Using HMMs in practice

  • Continuous observations. If observations are numbers rather than categories, B becomes a probability density for each state, usually a Gaussian or a Gaussian mixture. The algorithms stay the same.
  • Choosing the number of states. It is a hyperparameter. Compare likelihood on held-out sequences, or use a penalized score such as BIC.
  • Libraries. The hmmlearn package wraps these algorithms (it is not available in this browser runner, which is why we wrote them by hand). Fit with several random starts and keep the best likelihood.
  • Where they fit. Part-of-speech tagging (tags are hidden, words are observed), gene finding, speech and handwriting, regime detection in time series, and activity recognition from sensors.
  • Limits. The Markov assumption forgets everything but the current state, and the emissions are assumed independent given the state. Recurrent and Transformer models relax both assumptions, at the cost of needing far more data.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which three things define a hidden Markov model?

    An HMM is (pi, A, B): how the hidden chain starts, how its state moves, and how each state produces observations.
  2. 2. Why does the forward algorithm avoid summing over all state paths one by one?

    Dynamic programming builds the probability of each state at time t from the values at time t-1. That turns an exponential sum into a few matrix-vector products per step.
  3. 3. What does the Viterbi algorithm return?

    Viterbi maximizes the probability of the whole path. The most probable state on each individual day can differ from this path, which is why smoothing and decoding are separate ideas.
  4. 4. Baum-Welch is run twice on the same data from different random starting tables and ends with different parameters. Why?

    Like k-means, EM climbs to a local maximum of the likelihood, so the start matters. State numbering is arbitrary too, so you compare tables only after matching states.
  5. 5. Your observations are sensor readings measured as real numbers. What changes in the HMM?

    With continuous observations each state emits from a density (often a Gaussian or a mixture). The forward, Viterbi and Baum-Welch algorithms keep the same structure.

Summary

  • An HMM has a hidden Markov chain (start distribution ฯ€, transitions A) and an emission distribution B for what you observe.
  • The forward algorithm computes the likelihood of an observation sequence in T ยท nยฒ steps; use scaling or logs to avoid underflow.
  • Viterbi finds the most probable hidden path with dynamic programming and back-pointers; it can differ from the per-day filtered guesses.
  • Baum-Welch is EM: it estimates expected state and transition counts, then re-estimates the tables; the likelihood never decreases, but the result depends on the start.
  • HMMs suit small sequence problems where you want an inspectable model; neural sequence models take over when you have lots of data.

Next: Machine Learning for Time Series turns sequences into a supervised problem.