[Probability] Hidden Markov Model

Notations

States are hidden, observations are noisy and just partial reflections of the states.

Computations

Inference
– How to compute likelihood
– How to compute most likely (hidden) state sequence

Learning
– How to estimate parameters that maximize (multiple) observation sequences

Computing likelihood

Goal: computing likelihood of a state at time t+1 given all observations to time t+1

Fill up table of alpha [nxT]

Inference in HMMs

Goal: computing the most likely path of the states given observation to time T

Keyword: Viterbi path, Viterbi algorithm

Fill up table of l [nxT], which is the log probability of most likely t-step “path” that ends in state i at time t.

Start with the base case at t=1, find relationship between time t and time t+1 and recurse to T.

Base case for maximum log probability

Recursion for maximum log probability

Computing Viterbi path

Most likely state at time t given stat j at time t+1 with observations to time t.

Recursion gives us the Viterbi path

Learning in HMMs

Goal: given sequence of observations, estimate parameters (initial state, transition matrix, emission matrix) to maximize the likelihood.

Keyword: “forward-backward” algorithm (Baum-Welch)

Time complexity of this process is O(n^2T)

Gaussian Mixture Model (GMM)

Easy to understand ML estimation of Gaussian Mixture Model by making an analogy with K-means clustering, and EM algorithm is just an extension of it to cover the incomplete data case.

Belief Updating

Recursion relation for real-time updating of beliefs based on incoming evidence. Very useful for agents that must monitor their environments in real-time

Keyword: Kalman filtering

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.