Introduction to Hidden Markov
Models (HMMs) CompSci 369, 2022
School of Computer Science, University of Auckland
Copyright By PowCoder代写 加微信 powcoder
Last lecture
The Poisson process Markov chains
This lecture
Intro to HMMs
The Viterbi algorithm
States of a Markov chain are not seen, we only see symbols that states emit. All states emit the same symbols but with di erent probabilities.
We observe the sequence of symbols, want to know the sequence of states.
HMM Weather example
A sequence of states (wind directions) might look like: Producing the sequence of symbols (weather):
HMM Notation
is the state sequence with ith state Transition probability from state to state is Symbol sequence is , with ith symbol
often use for the generic symbol
Emission probability is probability of emitting
from state
)k = iπ|b = ix(P = )b(ke b
ix x )k=1−iπ|l=iπ(P=lka l k
HMM Weather example notation
HMM Example: Cheating casino
A casino occasionally switches from a fair die to a loaded die.
Rolling loaded die gives 6 50\% of the time, each of 1-5 10\% of the time. States are: and corresponding to the Fair and Loaded die. Emissions are: 1,2,3,4,5,6 corresponding to value rolled
Transition probabilities: and
Emission probabilities: and
5.0 = )6(Le 5,…,1 = b 01/1 = )b(Le 6,…,1 = b 6/1 = )b(Fe
9.0 = FLa − 1 = LLa 59.0=LFa−1= FFa 1.0= FLa 50.0=LFa
HMM Example: Cheating casino
From this process, we might observe the symbol sequence (i.e., a sequence of rolls of the die)
66662664266661532543563643224263665424266152
LLLLLLFFFFLLLLFFFFFFFFFFFFFFLLLLLLLLFFFLFFFF )ecnueqes etats( setatS
66662664266661532543563643224263665424266152 )ecneuqes lobmys( slloR
Joint probability of state and symbol seqeunce
Think of HMM as a generative process:
the rst state is chosen according to probability .
From rst state, a symbol is emitted according to the probabilities . The next state is then chosen according to transition probs
The next state emits a symbol and so on.
Joint probability of states and symbols is thus:
.1+iπiπa)ix(iπe ∏ 1π0a = )a ,e|π ,x(P = )π ,x(P
HMM Problems
Decoding — given model and output, nd most likely state path (use Viterbi algorithm)
Evaluation — given model and output, what is probability model generated that output (use forward or backward algorithms)
Posterior decoding — given model and output, what is probability of being in each state at each time (use forward-backward algorithm)
Learning — given model structure and output, nd parameters of model (use Baum-Welch algorithm)
Viterbi algorithm
Given symbol sequence , nd state path that maximises the joint probability: Can nd using a dynamic programming approach.
. ) π , x ( P x aπm g r a = ∗ π πx
Viterbi algorithm
Let be the probability of the most probable state path ending in state at observation
So Suppose Then
is the best score of the state path for the rst observations. is known for all states .
can be calculated for observation as
Use this recursion to nd best state path.
Assume boundary conditions: always start in begin state called 0, so
.)lka)i(kv(xakm )1+ix(le = )1 + i(lv 1+ix
)1 + i(lv )i(kv
)i(kv )i(kv
Viterbi algorithm
Initialisation : Recursion
Termination: Traceback
The termination step assumes the end state is modelled as modelled, this term disappears.
. If the end is not
)∗iπ(iretnioP = 1−∗iπ )0ka)L(kv(kxam gra = ∗Lπ 1 , … ,L = i
)0ka)L(kv(kxam = )∗π,x(P
)lka)1 − i(kv(kxam gra = )l(iretnio P
)lka)1 − i(kv(kxam )ix(le = )i(lv L , … ,1 = i 0>k 0=)0(kv 1=)0(0v 0=i
Viterbi algorithm
Even the most probable path has very low probability, so it is important to work in log units.
The recursion in log units is where
))1+ix(le(gol = )1+ix(lE ,)lka(gol = lkA ,))i(kv(gol = )i(kV
)lkA + )i(kV(xakm + )1+ix(lE = ))lka(gol + )i(kV(xakm + ))1+ix(le(gol = )1 + i(lV
Viterbi algorithm (log units)
Initialisation : Recursion
Termination: Traceback
)∗iπ(iretnioP = 1−∗iπ )0kA+)L(kV(kxamgra= ∗Lπ 1,…,L=i
)0kA + )L(kV(kxam = )∗π ,x(P
)lkA + )1 − i(kV(kxam gra = )l(iretnio P
)lkA+)1−i(kV(kxam+)ix(lE=)i(lV L,…,1=i 0>k ∞−=)0(kV 0=)0(0V 0=i
Viterbi algorithm (log units)
The key part of the algorithm is calculating the recursion
Think of as a matrix. Row indices are states, column indices are positions along sequence.
)i ,k( V = )i(kV )lkA + )i(kV(xakm + )1+ix(lE = )1 + i(lV
Viterbi example: CpG islands
Methylation changes the nucleotide pair CG (written CpG) to TG, so CpG is rarer than expected in genome.
But in functional regions, methylation is less common so we see more CpGs there. These regions are known as CpG islands.
Model each part of a sequence as having either high or low CpG content. Label the regions (for high CpG content) and (for low).
Viterbi example: CpG islands
In high CpG regions, C and G each occur with probability 0.35 and T and A with probability 0.15.
In low CpG regions, C and G are probability 0.2 and T, A are 0.3.
The initial state is H with probability 0.5 and L with probability 0.5. Transitions are given by .
Find the most likely state sequence given the sequence of symbols .
4.0 = HLa,6.0 = LLa ,5.0 = LHa = HHa
AAGTCACGG = x
Viterbi example: CpG islands
Work in log units (here use log base 2, can use any base, usually base e easiest): set and
Recursion is:
)lkA + )1 − i(kV(kxam + )ix(lE = )i(lV
737.1− 223.2− 223.2− 737.1−
737.2− 515.1− 515.1− 737.2− = ))A(He(gol TGC A
737.0− 223.1− L
1− 1−=)HHa(gol H =A LH
)e(2gol = E
)a(2gol = A
Want to ll out:
)lkA + )1 − i(kV(kxam + )ix(lE = )i(lV
Viterbi example: CpG islands
Traceback begins in the nal column by nding state that maximises the joint probability, in this case.
Following the pointers from this position and recording the state at each step gives us the state path with the highest probability is
LLLLLLHHH = ∗π
Viterbi algorithm examples
Recall the cheating casino which had a fair die (F) and a loaded die (L). The loaded die rolls a six 50% of the time.
LLLLLLFFFFLLLLFFFFFFFFFFFFFFLLLLLLLLFFFLFFFF )ecnueqes etats eurt( setatS
LLLLLLLLLLLLLFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF mtirogla ibretiV gnisu ecnueqes etats detcurtsnoceR
66662664266661532543563643224263665424266152 )ecneuqes lobmys( slloR
Automatic Chord Recognition — Chordec
Video of Chordec app in use
Paper: R. Chen, W. Shen, A. Srinivasamurthy, P. Chordia: “Chord Recognition Using Duration-Explicit Hidden Markov Models”, in International Society of Music Information Retrieval Conference (ISMIR), Oct 2012
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com