Outline
•Graphical models
•Markov process
•Hiden Markov Models (HMM)
•Forward-backward algorithm
•Viterbi algorithm
Hyun Min Kang Statistical Computing (BIOSTAT615) 2
GraphicalModels101
•Mariage between probability theory and graph theory
•An effective tool to represent complex structure of
dependence/independence between random variable
•Vertex : a random variable
•Edge : dependency between random variables
Is ?
An examplegraphical model
Hyun Min Kang Statistical Computing (BIOSTAT615) 4
!⊥#
Is ?!⊥#|
(marginal independence)
(conditional independence)
An example probability distribution
H Pr(H)
0 Low 0.3
1 High 0.7
Hyun Min Kang Statistical Computing (BIOSTAT615) 5
S H Pr(S|H)
0 Cloudy 0 Low 0.7
1 Sunny 0 Low 0.3
0 Cloudy 1 High 0.1
1 Sunny 1 High 0.9
P S Pr(P|S)
0 Absent 0 Cloudy 0.5
1 Present 0 Cloudy 0.5
0 Absent 1 Sunny 0.1
1 Present 1 Sunny 0.9
The full jointdistribution
H Pr(H)
0 Low 0.3
1 High 0.7
6
S H Pr(S|H)
0 Cloudy 0 Low 0.7
1 High 0 Low 0.3
0 Cloudy 1 High 0.1
1 High 1 High 0.9
P S Pr(P|S)
0 Absent 0 Cloudy 0.5
1 Present 0 Cloudy 0.5
0 Absent 1 Sunny 0.1
1 Present 1 Sunny 0.9
H S P Pr(H,S,P)
0 0 0 0.105
0 0 1 0.105
0 1 0 0.009
0 1 1 0.081
1 0 0 0.035
1 0 1 0.035
1 1 0 0.063
1 1 1 0.567
Conditionaldistribution
H S Pr(H|S)
0 Low 0 Cloudy 0.750
1 High 0 Cloudy 0.250
0 Low 1 Sunny 0.125
1 High 1 Sunny 0.875
P S Pr(P|S)
0 Absent 0 Cloudy 0.5
1 Present 0 Cloudy 0.5
0 Absent 1 Sunny 0.1
1 Present 1 Sunny 0.9
H P S Pr(H,P|S)
0 0 0 0.3750
0 1 0 0.3750
1 0 0 0.1250
1 1 0 0.1250
0 0 1 0.0125
0 1 1 0.1125
1 0 1 0.0875
1 1 1 0.7875
Is ?!⊥#|
Hand Pare conditionallyindependent given S
•Hand Pdoes not have direct path in the graph
•Al paths from Hto Pare connected through S
•In such cases, conditioning on Sseparates Hand P
Hyun Min Kang Statistical Computing (BIOSTAT615) 8
More conditionalindependence
Hyun Min Kang Statistical Computing (BIOSTAT615) 9
Markov blanket
•Markov blanket 'Afor node Ais a
set of nodes composed of A’s
parents, children, and the other
parents of its children.
•Fact : Node Ais conditionaly
independent given its Markov
blanket 'A.
Hyun Min Kang Statistical Computing (BIOSTAT615) 10
https://en.wikipedia.org/wiki/Markov_blanket
( ⊥)−(−+( | +(
Markov proces
State diagram
Pr(q
t+1
|q
t
)
Hyun Min Kang 11
q
0
q
1
q
2
q
3
q
T
…
Markov proces : mathematicalrepresentation
Hyun Min Kang Statistical Computing (BIOSTAT615) 12
Markov process : example questions
•What is the chance of rain in day 2?
•If it rains today, what is the chance of rain on the day
after tomorow?
•What is the stationary distribution when T
Hyun Min Kang Statistical Computing (BIOSTAT615) 13
•What is the chance of rain in day 2?
•If it rains today, what is the chance of rain on the day
after tomorow?
•What is the stationary distribution when t is very large?
Markov process : example questions
Hyun Min Kang Statistical Computing (BIOSTAT615) 14
Markov process dependencies
•If it rains today, what is the chance of rain on the day
after tomorow?
•If it has rained for the past 3 days in a row, what is the
chance of rain on the day after tomorow?
Hyun Min Kang Statistical Computing (BIOSTAT615) 15
Markov process dependencies
•If it rains today, what is the chance of rain on the day
after tomorow?
•If it has rained for the past 3 days in a row, what is the
chance of rain on the day after tomorow?
Hyun Min Kang Statistical Computing (BIOSTAT615) 16
HidenMarkov Models (HMMs)
•A graphical model composed of hiddenstates and
observeddata.
•The hiden states folow a Markov proces
•The distribution of observed data depends onlyon the
hiden state.
Hyun Min Kang Statistical Computing (BIOSTAT615) 17
An exampleof HMM
•Hiden states:
•HIGH
•LOW
•Observed data
•Sunny
•Cloudy
•Rainy
Hyun Min Kang Statistical Computing (BIOSTAT615) 18
Mathematical representation of the example
•States
•Observed Data
•Initial States
•Transition
•Emision
Hyun Min Kang Statistical Computing (BIOSTAT615) 19
Marginalprobabilities
•What is the chance of rain in the day 4?
Hyun Min Kang Statistical Computing (BIOSTAT615) 20
Conditionalprobabilities
•If the observation was
(SUNY, SUNY, CLOUDY, RAINY, RAINY) = (O