CMPSC442-Wk9-Mtg25
Markov Processes and Models
AIMA 14.1-14.2
CMPSC 442
Week 9, Meeting 25, Three Segments
Outline
● Markov Assumption
● Types of Inference Tasks
● Filtering, aka, Likelihood
2Outline, Wk 9, Mtg 25
Markov Processes and Models
AIMA 14.1-14.2
CMPSC 442
Week 9, Meeting 25, Segment 1 of 3: Markov Assumption
Handling Uncertainty over Time
● Builds on search in partially observable worlds
○ Belief states + transition model define how agent predicts how the world might be at each next
time step
○ Sensor model defines how to update the belief state
● Probability is used to quantify degrees of belief in elements of the belief state
● Time is handled by considering a set of random variables at each next point in
time
4Markov Assumption
Extending a Bayesian Network to Handle Time
● What if we want to compare the probability of sequences?
○ Alarm
t1
, MaryCalls
t2
, JohnCalls
t3
○ Alarm
t1
, JohnCalls
t2
, MaryCalls
t3
5Markov Assumption
Markov Assumption
● Russian statistician Andrei Markov
● Each state depends on a fixed finite number of prior states
● Future is conditionally independent of the past
● A Markov chain is a Bayesian network that incorporates time (temporal
sequences of states)
6Markov Assumption
Random Variables Indexed over Time
● Assume: fixed, constant, discrete time steps t
● Notation: Xa:b = Xa , Xa+1 ,…, Xb-1 , Xb
● Markov assumption: random variable Xt depends on bounded subset of X0:t-1
7Markov Assumption
First-order Markov Process
● Bayesian network over time
○ Random variables . . . Xt-2 , Xt-1 , Xt , Xt+1 , Xt+2 . . .
○ Directed edges for conditional independence
● Each state Xt is conditioned on the preceding state Xt-1
8Markov Assumption
Second Order Markov Process
● Each time step Xt is conditioned on the preceding states Xt-2, Xt-1
9Markov Assumption
Sensor Markov Assumption
● The agent’s observations or evidence Et at time t depend only on the state Xt
at time t
10Markov Assumption
HMMS: Reasoning about Unobserved States
● Transition model: How states change over time
● Sensor model: How the state at a given time t affects what evidence the agent
perceives at t
● The distribution of the random variable Xt of states, and the random variable Et
of evidence form the agent’s belief state
11Markov Assumption
Markov Processes and Models
AIMA 14.1-14.2
CMPSC 442
Week 9, Meeting 25, Segment 2 of 3: Inference Tasks
Umbrella World Example
You are the security guard stationed at a secret underground installation. You want
to know whether it’s raining today, but your only access to the outside world occurs
each morning when you see the director coming in with, or without, an umbrella.
For each day t, the set Et thus contains a single evidence variable Umbrellat or Ut
for short (whether the umbrella appears), and the set Xt contains a single state
variable Raint or Rt for short (whether it is raining).
13Inference Tasks
Umbrella World Assumptions that License an HMM
● Transition model: Changes in the world are caused by a stationary process
○ The conditional probability of it raining today, given yesterday, P(Rt|Rt-1 ), is the same for all t
● States are not observed: they are hidden
● Sensor model:
○ The evidence variables Ut (observations of umbrellas) are conditioned on the concurrent
states: P(Ut|Rt )
14Inference Tasks
Bayesian Network Structure for Umbrella World
15Inference Tasks
Full Joint Probability Distribution: Umbrella World
● Umbrella World is a Hidden Markov Model (HMM) with known parameters
(CPTs for transition model and sensor model)
● Full joint probability distribution for the umbrella world at time t is the product
of
○ Prior at time t=0
○ Transition model
○ Sensor model
16Inference Tasks
Inference Task: Computing the Belief State (Filtering)
● State estimation: the posterior distribution over the most recent state, given all
the evidence to date
● For example, what is the probability it will rain today, given all the evidence to
date
● Referred to as filtering from early work on signal processing to filter out noise
by estimating the underlying signal
● When extended to the posterior over a sequence of states, it is referred to as
computing likelihood (cf. Jurafsky & Martin)
17Inference Tasks
Inference Task: Prediction
● Compute posterior over a future state, based on all the evidence to date
● For example, what is the probability it will rain in three days
18Inference Tasks
Inference Task: Smoothing
● Compute the posterior distribution over a past state
● Smoothing gives a better estimate of Xk, k ≤ t, than was available at time tk
○ More evidence is incorporated for the state Xk – evidence preceding, concurrent with, and
following Xk
19Inference Tasks
Inference Task: Most Likely Explanation
● Find the most likely sequence of states that could have generated a set of
observations (decoding, in Jurafsky & Martin)
20Inference Tasks
Inference Task: Learning (Chapter 20)
● Model parameters are unknown
○ Transition model
○ Sensor model
● Model parameters can be learned from the data
○ Maximum likelihood parameter estimation
○ Expectation maximization (EM)
21Inference Tasks
Markov Processes and Models
AIMA 14.1-14.2
CMPSC 442
Week 9, Meeting 25, Segment 3 of 3: Filtering
Example Filtering
● Question: If it rains on day 1, is the probability of rain on day 2 higher than on
day 1 or lower than on day 1?
● Query: P(R2|u1:2 ) (given the evidence of an umbrella on day 1, and on day 2)
23Filtering
Filtering Exemplified
● Recursive estimation: for some function f, where the agent needs to compute
the new state Xt+1 based on the new evidence et+1, recursively add in evidence
at each new time step to get the subsequent state
24Filtering
Recursive estimation for P(Xt+1|e1:t+1 )
25
Divide up the evidence
Filtering
Recursive estimation for P(Xt+1|e1:t+1 )
26Filtering
Divide up the evidence
Bayes’ Rule
Sensor Markov assumption
Recursive estimation for P(Xt+1|e1:t+1 )
27Filtering
Computing the Probability of a State Given E1:2
● Query: P(R2|u1:2 )
● Day 0
○ No observations
○ Assume 50/50 chance it rained
28Filtering
Computing the Probability of a State Given E1:2
● Day 1: Umbrella is observed, U1=t
29Filtering
Computing the Probability of a State Given E1:2
● Day 1: Umbrella is observed, U1=t
● Update with the probability of the evidence for t=1
30Filtering
Computing the Probability of a State Given E1:2
● Day 2: Umbrella is observed, U2=t
31Filtering
Computing the Probability of a State Given E1:2
● Day 2: Umbrella is observed, U2=t
● Update with the probability of the evidence for t=2
32Filtering
Computing the Probability of a State Given E1:2
● Day 2: Umbrella is observed, U2=t
● Update with the probability of the evidence for t=2
33Filtering
Probability of rain increases from day 1 to
day 2 because the conditional
probabilities show that rain persists
Summary
● The Markov assumption is to assume the future is conditionally independent of
the past; a Markov chain is a Bayesian Network that incorporates time
○ The same random variables recur at each time step
● A Hidden Markov Model is a Bayesian Network over time
○ Markov assumption is made for the transition model
○ Markov assumption is made for the sensor model
○ States are hidden
34Summary, Wk 9, Mtg 25