Hidden Markov Model

Markov Chain

It is a stochastic process describing a sequence of possible events in which the possibility of each event depends only on the current state

All these while the state is given

Hidden State

Only observations are present and nothing explicit about the state

Three important uses

• Given the observations, calculate state estimation $$P(q_t=S_i|O1O2O3O4..Ot)$$

• Most Probable Path - Given the observations, what is the most probable path that is taken (VITERBI algorithm)

• Learning HMMs - Given observations, what is the maximum likelihood HMM that could have produced this string of observations (E.M. Algorithm)

Representation of HMM

$$lamda= < N,M,\pi,a_{ij},b_i(j)>$$

State Estimation

Given the observations, find the state at time t

The Probability of a given series of observations, non exponential-cost-style

$$\alpha_t(i) = P(O_1O_2...O_t \cap q_t=S_i|λ)$$

Calculation of Probability of observations

$$P(O_1O_2..O-t)=\sum_{i=1}^N\alpha_t(i)$$

Probability of a state given the observations

$$P(q_t=S_i|O_1O_2O_3..O_t)=\alpha_t(i)/\sum_{i=1}^N\alpha_t(j)$$

Most probable path given observations

$$\delta_i(j)= max_j [\delta_{i-1}(j)a_{ij}]B_j(O_i)$$