CS计算机代考程序代写 chain Bayesian Hidden Markov Mode Bayesian network CMPSC442-Wk9-Mtg25

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