Hidden Markov Model





Hidden Markov Model (HMM) is a parameterized distribution for sequences of observations. An intuitive way to explain HMM is to go through an example. Suppose that Taylor hears (a.k.a. observes) a sequence of T sounds o1, o2, ..., oT and he wants to reason something about this sequence. He makes the assumption that the sequence of sounds that he heard depends on a sequence of T words s1, s2, ..., sT , which he never gets to see and which is why they are called the hidden states. HMM gives Taylor a method which, under certain assumptions, allows him to assign appropriate probabilities to sound sequences O’s and word sequences S’s and to make reasonable deductions about them.

HMM makes several assumptions about the data it models:

  1. The observations o1, o2, ..., oT come from a known, finite sets V, called the observation space.
  2. The hidden states s1, s2, ..., sT come from a known, finite sets Q, called the hidden state space.
  3. The HMM assigns a probability to any given sequence s1, s2, ..., sT .

The chain rule says that

$P(s_1,s_2,s_3,....,s_T)=\prod_{t=1}^{T} P(s_t|s_0,s_1,s_2,...s_{t-1})=\prod_{t=1}^{T} P(s_t|s_{\lt t})..................(1.1)$

Here, we are being a little sloppy in terms of notation by assuming that there is a starting state s0, just so that the indexing is valid. In practice, such state s0 is sometimes called the starting state, and one can assign a probability distribution to it too. HMM goes further than Equation 1.1 by assuming that

$P(s_t|s_{\lt t})=P(s_t|s_{t-1})...............................(1.2)$

This is called the Markov assumption. With this assumption, Equation 1.1 can be rewritten as


Note that the Markov assumption generally does not hold. In our example, sequences of words usually have dependencies that go back longer than one immediate step.

  1. Each observation $o_t$ only depends on the immediate hidden state $s_t$. Formally

$P(o_t|o_{\lt t},s_{\lt t})=P(o_t|s_t).....................................(1.4)$

This is called the Independence assumption.

Terminology in HMM

The term hidden refers to the first order Markov process behind the observation. Observation refers to the data we know and can observe. Markov process is shown by the interaction between “Rainy” and “Sunny” in the below diagram and each of these are HIDDEN STATES.

enter image description here

OBSERVATIONS are known data and refers to “Walk”, “Shop”, and “Clean” in the above diagram. In machine learning sense, observation is our training data, and the number of hidden states is our hyper parameter for our model.

T=length of the observations sequence
N=number of states in the model
M=number of observations symbols
Q={$q_0,q_1,...,q_{N-1}$=distinct states of the Markov process
V={0,1,............,M-1}=set os possible observations
A=state transitions probablities
B=observation probability matrix
$ \pi$=initial state distribution
O=($O_0,O_1,...,O_{T-1}$)=observation sequence
T = don’t have any observation yet, N = 2, M = 3, Q = {“Rainy”, “Sunny”}, V = {“Walk”, “Shop”, “Clean”}

State transition probabilities are the arrows pointing to each hidden state. Observation probability matrix are the blue and red arrows pointing to each observation from each hidden state. The matrix is row stochastic meaning the rows add up to 1.

$a_{ij}=P(\text{ state }q_j \text{ at }t+1|\text{state }q_i \text{ at }t)$

$b_{j(k)}=P(\text{observation k at t|state }q_j \text{ at t})$

The matrix explains what the probability is from going to one state to another or going from one state to an observation.

Initial state distribution gets the model going by starting at a hidden state.

Full model with known state transition probabilities, observation probability matrix, and initial state distribution is marked as,

$\lambda =(A,B,\pi)$

page hidden markov model • 1.6k  views

Next up

Read More Questions



Study Full Subject


Know More