Skip to content

19 HMM, Particle Filtering, Applications

Hidden markov models

  • underlying markov chain over states \(X\)

Real HMM Examples

  • speech recognition
  • observation are acoustic signals (continuous-valued)
  • states are specific positions in specific words (so, tens of thousands)
  • machine translation HMM

Filtering/Monitoring

  • with filtering, we are trying to keep track of the distribution over time
  • \(B_t(X) = P_t(X_t | e_1, \dots, e_t)\)
  • we start with \(B_1\) in an initial setting, usually uniform
  • as time passes, or we get observations, we update \(B(X)\)
  • the Kalman Filter, which uses continuous variables, was invented in the 60's and first implemented as a method of trajectory estimation for the Apollo program

Example: robot localization

we have a room and the robot wants to know where it is in the room

we have a sensor model: where is the wall. \(\{\text{North}, \text{East}, \text{West}, \text{South}\}\)

the model would only make at most 1 mistake when reading where the walls are

our initial time is time = 0. the probability at time = 0 for all the squares in the room are equally likely to be the state that the room is in

then we get a sensor eval that there is a wall to the north and south, means that the robot's inferences change the reading of where the robot possibly is.

at the very least we know that the robot is not in a north-south corridor because there at least a wall to the north or to the south of it. the sensor would not make more than one mistake it could be at the junction of two corridors where theres a wall on the top but not the bottom, etc.

so even from this first observation, the robot can already update its posterior probability

if the robot keeps moving, getting observations from the sensors, we know that when the robot tries to move right, we know that given the sensor observation, its likely to keep going forward. Its likely that the robot stayed in the same spot, so theres a slight probability its still in the initial position, but much higher that it moved

the posterior probabilities keep changing, as the other squares are less likely, and the distribution is becoming more certain of the location of the robot.

the robot learns more about where it was and where it is. The loop is about knowing what the walls look like, etc.

Here, Markov Models combine all this information, so what is the underlying process?

Two things we do: we initialize, then get an observation, and then update the probabilities of the states based on the observation and previous observations.

You do the first BC and go forward and back through time until you get to the time that you were trying to predict in the first place.

imagine time step 1: \(P(X_1|e_1)\) so someone carrying an umbrella, what is the probability that it is raining given someone is carrying an umbrella.

first using the definition of conditional probability. this is just equal to the joint probability of \(X\)

\(P(x_1|e_1)\) \(= P(x_1, e_1)/P(e_1)\) \(= \alpha \, P(x_1, e_1)\) \(= P(x_1)P(e_1|x_1)\)

you can also think of this as an application of bayes rule flip the conditional probability statements around. we do that by starting from the state that we are in.

thats like kinda the first base case in HMMs: how likely that we are going to be in state 2. whats the probability of stage two?

in this case we are just looking at the state of \(d_2, d_3\).

unfrt yhid bwsurd nry mofrl sll er hsbr yo fo id msrhinslixr ouy

applying the product rule we can require this one into the other one.

\(P(X_2)\) \(P(x_2) = \sum_{x_1} P(x_1, x_2)\) \(= \sum_{x_1} P(x_1)P(x_2|x_1)\)

Passage of time

Assume we have a current belief \(P(X \mid \text{evidence to date})\) \(B(X_t) = P(X_t \mid e_{1:t})\)

then after some time passes \(P(X_{t+1} \mid e_{1:t}) = \sum_{x_t} P(X_{t+1}, x_t \mid e_{1:t})\) \(= \sum_{x_t} P(X_{t+1} \mid x_t, e_{1:t})P(x_t \mid e_{1:t})\)

In English: we want the belief about the next state \(X_{t+1}\) given all the evidence so far. We don't have a direct handle on \(X_{t+1}\) alone, so we bring in the current state \(x_t\) and sum it back out — that's the first line, marginalizing over \(x_t\) inside the joint. The second line just splits that joint with the product rule: the joint of \((X_{t+1}, x_t)\) given the evidence becomes the transition into \(X_{t+1}\) (conditioned on \(x_t\) and the evidence) times the belief we already hold about \(x_t\) given the evidence. So the step from line one to line two isn't a new fact — it's the same joint, rewritten as (transition) × (current belief).

= \(\sum_{x_t} P(X_{t+1}|x_t)P(x_t|e_{1:t})\)

or compactly

\(B'(X_{t+1}) = \sum_{x_t} P(X'|x_t)P(x_t)\)

basic idea: beliefs get pushed through transitions - with the belief notation we have to be careful about what step of \(t\) we are using.

Example: passage of time.

  • as time passes, uncertainty accumulates
  • transitions model: ghosts usually go clockwise
  • the model is being updated by transition dynamics
  • time passing without observation just accumulates uncertainty.
  • we are just updating the passage of time under the random dynamics of where the ghost could be randomly

that brings us to the next case, etc. but now to get to the other part of the hmm we have other evidence over time as well.

Two notes: the middle jump from line two to the next line uses the Markov assumption — \(P(X_{t+1} \mid x_t, e_{1:t})\) drops the evidence to become \(P(X_{t+1} \mid x_t)\), since the next state depends only on the current state. And in your line = α x1 P(x1, e1) I read the x1 as a stray token and treated it as \(\alpha \, P(x_1, e_1)\) (the normalizer times the joint) — flag if you meant something else there.

  • MarkovChain — Markov chains built by hand resurface as HMMs