Hidden Markov Models

Often, we want to reason about a sequence of observations:

• speech recognition

• robot localization

• user attention

• medical monitoring

Need to introduce time (or space) into our models

Markov Models

• value of X at a given time is called the state

• parameters:

  • called transition probabilities or dynamics

  • specify how the state evolves over time

• stationarity assumption

  • transition probabilities the same at all times

• no choice of action

Conditional Independence

• past and future independent given the present

• each time step only depends on the previous

• this is called the (first order) Markov property

• we can always use generic BN reasoning if we truncate the chain at a fixed length

Mini-Forward Algorithm:

• P(x₁) = known

• P(x_t) = ∑ P(x_t | x_t-1) P(x_t-1)

Stationary Distributions

• the distribution we end up with is called the stationary distribution P_x of the chain

  • P_∞(X) = P_{∞ + 1}(X) = ∑ P(X | x) P_∞(x)

Hidden Markov Models

• underlying Markov chain over states X

• observe outputs (effects) at each time step

Conditional Independence and HMMs

• Markov hidden process:

  • future depends on past via the present

• Current observation independent of all else given current state

Filtering / Monitoring

• task of tracking the distribution B_t(X) = P_t(X_t | e_1, …, e_t) over time

• start with B₁(X) in an initial setting, usually uniform

• as time passes we update B(X)

Passage of Time:

• Assume we have current belief P(X | evidence to date)

  • B(X_t | e_{1 : t})

• then, after one time step passes

  • P(X_{t + 1} | e_{1 : t}) = ∑ P(X_{t + 1} | x_{t ,} c_{1 : t}) P(x_t | c_{1 : t})

    • ∑ P(X_{t + 1} | x_t) P(x_t | c_{1 : t})

Observation:

• assume we have current belief P(X | previous evidence)

  • B’(X_{t + 1}) = P(X_{t + 1} | e_{1 : t})

• then, after evidence

  • P(X_{t + 1} | e_{1 : t + 1}) = P(X_{t + 1} , e_{t + 1} | e_{1 : t}) / P(e_{t + 1} | e_{1 : t})

The Forward Algorithm

• given evidence at each time and want to know

  • B_t(X) = P(X_t | e_{1 : t})

• we can derive the following updates

  • P(x_t | e_{1 : t}) ∝ x P(x_t , e_{1 : t})

    • = ∑ P(X_{t - 1} , x_t , e_{1 : t})