Hidden Markov Models

According to firgure 1, the prob of starting with s1,s2,s3 = [0.5, 0.3, 0.2]. What is the chance of observing the sequence of states s₁,s₃,s₃,s₂,s₁,s₃

0.003

What is a first order markov chain charachterized by?

Movinf from qt to state qt+1 only depends on state qt

What is an Ergodic HMM

In Fig2, there’s an equal probability to select any ball in a bowl. Any state can be reached from any other state.

What do the variables T,N,M,Q,V stand for

T = length of observation sequence (total number of balls selected)

N = number of states (bowls)

M = number of observation symbols (coloured balls)

Q = {q₁,q₂,…,q_N} series of states

V = {v₁,v₂,…,v_M} set of possible observation symbols

An HMM is described by λ = (A, B, π). What does this mean?

A = {aᵢⱼ} — State Transition Probability Matrix

• aᵢⱼ = P(qⱼ at time t+1 | qᵢ at time t)

• This tells us the probability of transitioning from state i at time t to state j at time t+1.

B = {bⱼ(k)} — Observation Probability Distribution

• bⱼ(k) = P(v_k at time t | qⱼ at time t)

• This gives the probability of observing symbol v_k when in state qⱼ at time t. Recall set of symbols V={v1,v2,v3}. where k is just the index ie. in v1, k =1.

π = {πᵢ} — Initial State Distribution

• πᵢ = P(qᵢ at time t = 1)

• These are the probabilities of starting in each of the possible states at time 1

Describe method to generate an observation sequence

An observation sequence O = O₁,O₂,…,O_T is generated as follows:

1.Choose an initial state q₁ according to the initial state distribution p

2.Set t = 1

3.Choose O_t according to b_1t(k), the symbol probability distribution of state q₁

4.Choose a state q₂ according to {a_ij}

5.Set t = t+1

6.Return to step 3 if t < T

7.Terminate

For Fig 2, construct the aij and bj(k) matrices

in diagram

Give 3 applications of Problem 1

1. Biological sequence Analysis: An HMM trained on known TATA boxes can calculate the probability that a new sequence contains one. The same can be done for replication origins, TF binding sites, centromeres etc.

2. EKG Analysis: Detect abnormal heart rhythms by comparing EKG signals to HMMs of normal/abnormal patterns.

3. Word and image recognition
   
   TLDR: you have something that you have lots of examples of, so you can calculate the probabilities of having specific emission frequencies for specific symbols. Generate a HMM on that trained data that you can then employ on any seq. Use algs to determine what was prob that THAT seq was generated by THIS HMM.

Applications of Problem 2: What is the most likely series of states to have produced a pattern?

So if you have a trained HMM and you have different states representing different things ie. coding, non-coding, CPG islands etc. then you can use Viterbi analyze an unknown seq and it will tell you most likely state that would have generated that series of symbols.