Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 46 ยท Probabilistic Reasoning

Hidden Markov Models and Filtering

Learn temporal reasoning: hidden Markov models, the forward algorithm, Viterbi decoding, Kalman and particle filters, and robot localization in a corridor, in Python.

The Bayesian networks in the last lesson describe a single moment in time. Many AI problems unfold over time: a robot moves and senses, a speech recognizer hears a stream of sounds, a stock tracker sees prices change. In each case something important is hidden (where the robot really is, which word was spoken), and all the agent gets is a sequence of noisy observations.

A Hidden Markov Model (HMM) is the simplest model for this situation, and the algorithms around it (filtering, prediction, smoothing, most-likely-sequence) are the foundation of localization, tracking and speech recognition. In this lesson you will implement the forward algorithm and Viterbi, localize a robot in a corridor, and meet the Kalman and particle filters.

Temporal models and the Markov assumption

We model time as discrete steps t = 1, 2, 3, .... At each step there is a hidden state X_t and an observation E_t. Two simplifying assumptions make the model tractable.

  • Markov assumption: the next state depends only on the current state, not on the whole history: P(X_t | X_1..X_t-1) = P(X_t | X_t-1).
  • Sensor assumption: an observation depends only on the current state: P(E_t | X_1..X_t, E_1..E_t-1) = P(E_t | X_t).
graph LR
    X1["X1"] --> X2["X2"] --> X3["X3"] --> X4["X4"]
    X1 --> E1["E1"]
    X2 --> E2["E2"]
    X3 --> E3["E3"]
    X4 --> E4["E4"]

The hidden states form a chain; each emits one observation. We see only the E nodes.

An HMM is fully specified by three tables:

Part Symbol Meaning
Prior P(X_1) where the process starts
Transition model T[i, j] = P(X_t = j | X_t-1 = i) how the state evolves
Sensor (emission) model E[i, k] = P(observation k | X_t = i) how states produce readings

Four classic questions can be asked of an HMM.

  1. Filtering: what is the current state given all observations so far? P(X_t | e_1..e_t). This is what a robot needs while running.
  2. Prediction: what will the state be later? P(X_t+k | e_1..e_t).
  3. Smoothing: what was the state in the past, given everything seen since? More accurate than filtering because it also uses later evidence.
  4. Most likely explanation: which single sequence of states best explains the observations? (Viterbi.)

Filtering and the forward algorithm

Filtering is a recursive computation. The belief at time t is computed from the belief at time t-1 in two steps, which you will meet again in every filter in this lesson.

  1. Predict: push the old belief through the transition model: belief' = belief @ T.
  2. Update: multiply by the likelihood of the new observation and normalize: belief โˆ belief' ยท E[:, obs].

This recursion is the forward algorithm. It also yields the probability of the whole observation sequence if we multiply together the normalizing constants. The example is a cafรฉ: the hidden state is whether the day is Busy or Quiet, and the observation is whether the number of customers by noon is Low, Medium or High.

Python The forward algorithm for a cafe

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 belief swings with the evidence: two "High" days make Busy very likely (92%), then "Low" days flip it to Quiet. The forward algorithm touches each time step once and needs only a matrix multiplication per step, so its cost is linear in the length of the sequence. The brute-force check enumerates all 128 hidden sequences and reaches the same probability, 0.000545, which shows what the recursion saves: the number of sequences grows exponentially, the forward algorithm's work does not.

Tip: Real implementations compute in log space or rescale at each step, as the code above does with norm. Multiplying hundreds of small probabilities would otherwise underflow to zero.

Viterbi: the most likely sequence

Filtering gives a probability for each state at each step separately, but the best sequence is a different question. The most probable state at each time may not form the most probable path, because some transitions can be unlikely. The Viterbi algorithm uses dynamic programming: for each state it keeps the probability of the best path ending there, and a back-pointer to the previous state. At the end it follows the pointers backward.

It is the same recursion as the forward algorithm with max in place of sum. We use logarithms so that products become sums.

Python Viterbi decoding compared with filtering

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.

Viterbi and brute force agree. Filtering disagrees on day 6, a "Medium" day: Quiet (56%) is the single most likely state given the evidence so far, but the best complete path calls day 6 Busy, because the day-7 "High" reading is best explained by Busy, and staying in Busy (0.7) is a far likelier transition than switching from Quiet to Busy (0.4). The two answers are both right; they answer different questions. Speech recognizers and DNA gene finders use Viterbi to turn a stream of sounds or bases into the best sequence of hidden labels.

Robot localization in a corridor

Now an application. A robot sits somewhere in a circular corridor of 12 cells. Some cells have a door (D), the others a wall (W). It cannot see its position, only what is beside it, and its door sensor is right 80% of the time. It also moves imperfectly: a command to move one cell succeeds 80% of the time, but 10% of the time the robot stays and 10% of the time it overshoots by one.

This is an HMM whose state is the cell number. The belief is a histogram over the 12 cells, and the two steps are exactly predict (the move function) and update (the sense function). The robot starts in cell 0 with no knowledge, so the belief is uniform. It then senses D, moves one cell, senses D, moves, senses W, moves and senses W.

Python A histogram filter for robot localization

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 table prints the belief as a percentage per cell. After the first D reading, the four door cells (0, 1, 4, 8) each get 17%. After moving and sensing D again, cell 1 stands out because a door followed by another door exists only at cells 0 to 1. By the end the belief peaks at cell 3 with probability 0.333, and indeed the robot started at cell 0 and moved three times, so it is in cell 3. Notice that confidence is only a third, not 100%: the sensors are noisy, the motion is uncertain, and every move spreads the belief out again (move blurs, sense sharpens). A robot that keeps moving without sensing becomes steadily less certain, and one that keeps sensing in a symmetric corridor can stay ambiguous. This is the discrete version of Markov localization, the basis of many real robot systems (see Introduction to Robotics).

Kalman and particle filters

The histogram filter has a weakness: it needs a table over every possible state, which is wasteful for continuous quantities such as position. Two filters handle continuous states, using the same predict-update cycle.

Kalman filter. Assume the state is a Gaussian (a bell curve) described by a mean and a variance, motion adds a known amount plus Gaussian noise, and the sensor measures the state plus Gaussian noise. Then the belief stays Gaussian forever and can be updated in closed form. Prediction increases the variance (we are less sure after moving); the update decreases it by blending prediction and measurement with the Kalman gain K = variance / (variance + sensor_variance). A large gain means "trust the sensor", a small gain means "trust the prediction". It is optimal for linear-Gaussian systems and runs in microseconds, which is why it appears in GPS receivers, aircraft and phones.

Particle filter. When the belief can be anything (multi-modal, non-Gaussian), represent it by many random samples, the particles. Each step moves every particle with the noisy motion model, weights each particle by how well it explains the measurement, then resamples: particles are drawn with probability proportional to their weight, so good hypotheses multiply and bad ones disappear. Particle filters are flexible and easy to write, and their accuracy improves with the number of particles.

The next example tracks a vehicle moving about one unit per step along a line. The sensor error is large (standard deviation 1.5) and the motion noise small (0.3). We run the Kalman filter and a 1,000-particle filter on the same data.

Python Kalman filter against particle filter

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.

Both filters cut the sensor's error of about 1.5 down to roughly 0.65, and they agree closely, as they should: this problem is linear and Gaussian, which is the Kalman filter's ideal case. The gain settles near 0.18, meaning each new reading is weighted only 18% against the filter's prediction. The particle filter wins when the problem is not Gaussian, for example when a robot's position could be in one of several corridors; it costs far more computation to get the same accuracy.

Choosing a filter

Filter State space Belief shape Cost
HMM / histogram small discrete any table O(nยฒ) per step (with a dense transition matrix)
Kalman continuous, linear single Gaussian tiny matrix algebra
Extended / unscented Kalman continuous, mildly nonlinear approx. Gaussian small
Particle continuous, any many samples grows with particle count

All of them are one idea: predict, then update with evidence. Once an agent can estimate where it is, it still needs to choose what to do, which is the topic of Decision Making: Utility, MDPs and Value Iteration.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does the Markov assumption say?

    Given the present state, the past carries no extra information about the next state. This is what makes recursive filtering possible.
  2. 2. Which two steps make up one cycle of filtering?

    Prediction spreads the belief through time; the update multiplies by the likelihood of the new evidence and normalizes.
  3. 3. Why can the Viterbi path differ from the sequence of most likely states found by filtering?

    The most probable state at each time step need not form the most probable path, because transitions between them might be unlikely.
  4. 4. In the corridor robot, what does a move step do to the belief?

    Moving shifts the belief by the commanded distance and blurs it by the motion noise. Sensing is the step that sharpens it.
  5. 5. When is a particle filter preferable to a Kalman filter?

    A Kalman filter assumes a single Gaussian belief. Particles can represent any shape, at the cost of more computation.

Summary

  • An HMM has hidden states that evolve by a transition model and emit observations through a sensor model; the Markov and sensor assumptions make it tractable.
  • Filtering computes the current belief recursively: predict with the transition model, update with the observation, normalize (the forward algorithm).
  • Viterbi finds the single most likely state sequence with dynamic programming; it can differ from per-step filtering.
  • Robot localization is filtering over positions: motion blurs the belief, sensing sharpens it.
  • Kalman filters handle linear-Gaussian continuous states in closed form; particle filters use weighted random samples for arbitrary beliefs.
  • Always work with normalized or log probabilities to avoid underflow.

Next: Decision Making: Utility, MDPs and Value Iteration.