CS计算机代考程序代写 Bayesian Hidden Markov Mode CS 4610/5335

CS 4610/5335
Sequential Bayes Filtering
Robert Platt Northeastern University
Material adapted from:
1. Russell & Norvig, AIMA
2. Dan Klein & Pieter Abbeel, UC Berkeley CS 188 3. Lawson Wong, CS 5335
4. Chris Amato, CS 5100
5. Sebastian Thrun, Wolfram Burgard, & Dieter Fox,
Probabilistic Robotics

1-D example
From “Probabilistic Robotics” (Ch. 7-8)
by Sebastian Thrun, Wolfram Burgard, & Dieter Fox

1-D example
From “Probabilistic Robotics” (Ch. 7-8)
by Sebastian Thrun, Wolfram Burgard, & Dieter Fox
Challenge: Robot can only sense wall/door at its current location

1-D example
From “Probabilistic Robotics” (Ch. 7-8)
by Sebastian Thrun, Wolfram Burgard, & Dieter Fox
Challenge: Robot can only sense wall/door at its current location
Robot starts somewhere random, keeps on heading right,
detects Wall, Door, Wall, Wall, …
Where is it now?

1-D example
From “Probabilistic Robotics” (Ch. 7-8)
by Sebastian Thrun, Wolfram Burgard, & Dieter Fox
Robot starts somewhere random, keeps on heading right. Where is it after:
WWDWDWWW WWWDWWW

1-D example
From “Probabilistic Robotics” (Ch. 7-8)
by Sebastian Thrun, Wolfram Burgard, & Dieter Fox
Robot starts somewhere random, keeps on heading right. Where is it after:
WWDWDWWW WWWDWWW WWWDDDWWW WDWDDWWDDDWWW

2-D Example
Robot is actually located here, but it doesn’t know it.
Prob
Gray level denotes estimated probability that robot is in that square
01
Goal: localize the robot based on sequential observations
– robot is given a map of the world; robot could be in any square – initially, robot doesn’t know which square it’s in
Image: Berkeley CS188 course notes (downloaded Summer 2015)

2-D Example
Robot perceives that there are walls above and below, but no walls either left or right
Prob
Gray level denotes estimated probability that robot is in that square
01
On each time step, the robot moves, and then observes the directions in which there are walls.
– observes a four-bit binary number
– observations are noisy: there is a small chance that each bit will be flipped.
Image: Berkeley CS188 course notes (downloaded Summer 2015)

2-D Example
Prob
01
Image: Berkeley CS188 course notes (downloaded Summer 2015)

2-D Example
Prob
01
Question: how do we update this probability distribution from time t to t+1?
Image: Berkeley CS188 course notes (downloaded Summer 2015)

Rules of Probability

Conditional Probabilities
Conditional probability: P(A| B)=P(A,B) (if P(B)>0 ) P(B)
14

Bayes’ Rule
It’s easy to derive from the product rule:
Solve for this
15

Interpretation:
Posterior
P(state | obs)
Likelihood * Prior
P(obs | state) P(state)
= ————————————–
P(obs)
Evidence
Bayesian inference
16

Interpretation:
Posterior
P(state | obs)
Likelihood * Prior
P(obs | state) P(state)
= ————————————–
P(obs)
Evidence
Bayesian inference
E.g., State = Is it raining outside right now? – Prior: It rains on 30% of days in Boston
– P(rain) = 0.3 ; P(not rain) = 1-0.3 = 0.7
Observation = People are carrying wet umbrellas – P(obs | rain) = 0.9 ; P(obs | not rain) = 0.2
Bayes’ rule: P(rain | obs) α P(obs | rain) * P(rain) – P(rain | obs) α 0.9 * 0.3 = 0.27
– P(not rain | obs) = ?
19

1-D example (Init) p(x1) = Uniform

1-D example (Observation) p(x1) = Uniform
Detect z1=Door. P(z1=Door | x1):

1-D example (Posterior update) p(x1) = Uniform
Detect z1=Door. P(z1=Door | x1) :
Apply Bayes’ rule. P(x1 | z1=Door) α P(z1=Door | x1) * P(x1) :

1-D example (Posterior update) p(x1) = Uniform
Detect z1=Door. P(z1=Door | x1) :
Apply Bayes’ rule. P(x1 | z1=Door) α P(z1=Door | x1) * P(x1) : Normalization step not shown explicitly:
– Calculate RHS for all values of x1
– Divide RHS by the sum (such that posterior sums to 1)

1-D example (Transition)
P(x1 | z1=Door) :
Take one step to the right. P(x2 | x1, z1=Door) :

1-D example (Observation) P(x2 | x1, z1=Door) :
Detect z2=Door. P(z2=Door | x2) :

1-D example (Transition)
P(x2 | z2=Door, z1=Door) :
Take more steps, etc.

Mobile robot localization (Hallway example)
From
“Probabilistic Robotics” (Ch. 7-8)
by
Sebastian Thrun, Wolfram Burgard,
& Dieter Fox
Continuous case; Ideal outcome
30

Mobile robot localization (Hallway example)
From
“Probabilistic Robotics” (Ch. 7-8)
by
Sebastian Thrun, Wolfram Burgard,
& Dieter Fox
This is an important problem!
– Ch. 2-4 (half of Part 1)
is HMM inference
– Ch. 7-8 (entire Part 2!)
is about localization – There are 4 parts,
17 chapters in total
31

Mobile robot localization (Hallway example)
From
“Probabilistic Robotics” (Ch. 7-8)
by
Sebastian Thrun, Wolfram Burgard,
& Dieter Fox
Discrete case;
Exact HMM inference
32

1-D example
1
2
3
4
Consider a 1-D grid world
The agent can only move right
Single action still has stochastic outcomes
P(Actually moves right) = 0.8 P(Stays still) = 0.2

1-D example
1
2
3
4
Consider a 1-D grid world
The agent can only move right
Single action still has stochastic outcomes
P(Actually moves right) = 0.8 P(Stays still) = 0.2
What if agent does not know where it is exactly? – New: State uncertainty
Belief: Probability distribution over states
P(1) = 0.8 P(2) = 0.2 P(3) = 0.0 P(4) = 0.0
What information can we use to infer our state? – New: Noisy observations
Robot detects whether upper cell is door/empty P(Empty | In state 1) = 0.9 P(Door | In state 1) = 0.1 P(Empty | In state 2) = 0.1 P(Door | In state 2) = 0.9 …

1-D example
1
2
3
4
Consider a 1-D grid world
The agent can only move right
Suppose we know that x0 = 1 P(x1) = ?

1-D example
1
2
3
4
Consider a 1-D grid world
The agent can only move right
Suppose we know that x0 = 1
P(x1): P(x1=1)=0.2 P(x1=2)=0.8

1-D example
1
2
3
4
Consider a 1-D grid world
The agent can only move right
Suppose we know that x0 = 1
P(x1): P(x1=1)=0.2 P(x1=2)=0.8
What if we did not know x0, but only had a belief P(x0)? P(x0): P(x0=1)=0.8 P(x0=2)=0.2
With prob. 0.8, we start in x0 = 1, then:
– With prob. 0.8, we end up in x1 = 2 – With prob. 0.2, we end up in x1 = 1
With prob. 0.2, we start in x0 = 2, then:
– With prob. 0.8, we end up in x1 = 3 – With prob. 0.2, we end up in x1 = 2
→ p = 0.8 * 0.8 = 0.64 → p = 0.8 * 0.2 = 0.16
→ p = 0.2 * 0.8 = 0.16 → p = 0.2 * 0.2 = 0.04

1-D example
What if we did not know x0, but only had a belief P(x0)? P(x0): P(x0=1)=0.8 P(x0=2)=0.2
With prob. 0.8, we start in x0 = 1, then:
– With prob. 0.8, we end up in x1 = 2 – With prob. 0.2, we end up in x1 = 1
With prob. 0.2, we start in x0 = 2, then:
– With prob. 0.8, we end up in x1 = 3 – With prob. 0.2, we end up in x1 = 2
→ p = 0.8 * 0.8 = 0.64 → p = 0.8 * 0.2 = 0.16
→ p = 0.2 * 0.8 = 0.16
→ p = 0.2 * 0.2 = 0.04 P(x1 = 1) = 0.16 P(x1 = 2) = 0.64 + 0.04 = 0.68 P(x1 = 3) = 0.16

1-D example
1
2
3
4
Consider a 1-D grid world
The agent can only move right
What if we did not know x0, but only had a belief P(x0)? P(x0): P(x0=1)=0.8 P(x0=2)=0.2
P(x1 = 1) = 0.16 P(x1 = 2) = 0.64 + 0.04 = 0.68 P(x1 = 3) = 0.16
What information can we use to infer our state? Suppose we detect that the upper cell is a door Observation at state x1: y1 = Door

Recall: Bayes’ Rule
One interpretation:
P(effect | cause) P(cause) P(cause | effect) = ————————————–
Another interpretation:
Posterior
P(state | obs)
P(effect)
Likelihood * Prior
P(obs | state) P(state)
= ————————————–
P(obs)
Evidence
47

1-D example
1
2
3
4
Consider a 1-D grid world
The agent can only move right
What if we did not know x0, but only had a belief P(x0)? P(x0): P(x0=1)=0.8 P(x0=2)=0.2
P(x1 = 1) = 0.16 P(x1 = 2) = 0.64 + 0.04 = 0.68 P(x1 = 3) = 0.16
Observation at state x1: y1 = Door
How do we use y1 = Door to update P(x1)?
P(obs | state) P(state) P(state | obs) = ————————————–
P(obs)

1-D example
1
2
3
4
Consider a 1-D grid world
The agent can only move right
What if we did not know x0, but only had a belief P(x0)? P(x0): P(x0=1)=0.8 P(x0=2)=0.2
P(x1 = 1) = 0.16 P(x1 = 2) = 0.64 + 0.04 = 0.68 P(x1 = 3) = 0.16
Observation at state x1: y1 = Door
How do we use y1 = Door to update P(x1)?
P(y1 = Door | x1) P(x1) P(x1 | y1 = Door) = ————————————–
P(y1 = Door)

1-D example
What if we did not know x0, but only had a belief P(x0)?
P(x0): P(x0=1)=0.8 P(x0=2)=0.2
P(x1 = 1) = 0.16 P(x1 = 2) = 0.64 + 0.04 = 0.68 P(x1 = 3) = 0.16
Observation at state x1: y1 = Door
P(y1 = Door | x1) P(x1) P(x1 | y1 = Door) = ————————————–
P(y1 = Door)
Notice that y1 = Door is fixed – we cannot change this Posterior probability varies with x1
but denominator does not!

1-D example
What if we did not know x0, but only had a belief P(x0)?
P(x0): P(x0=1)=0.8 P(x0=2)=0.2
P(x1 = 1) = 0.16 P(x1 = 2) = 0.64 + 0.04 = 0.68 P(x1 = 3) = 0.16
Observation at state x1: y1 = Door
P(x1 |y1=Door) α P(y1=Door|x1)P(x1)
Notice that y1 = Door is fixed – we cannot change this Posterior probability varies with x1
but denominator does not!

1-D example
What if we did not know x0, but only had a belief P(x0)?
P(x0): P(x0=1)=0.8 P(x0=2)=0.2
P(x1 = 1) = 0.16 P(x1 = 2) = 0.64 + 0.04 = 0.68 P(x1 = 3) = 0.16
Observation at state x1: y1 = Door
P(x1 |y1=Door) α P(y1=Door|x1)P(x1)
Notice that y1 = Door is fixed – we cannot change this Posterior probability varies with x1
but denominator does not!
Compute numerator product for each x1, then normalize

1-D example
What if we did not know x0, but only had a belief P(x0)?
P(x0): P(x0=1)=0.8 P(x0=2)=0.2
P(x1 = 1) = 0.16 P(x1 = 2) = 0.64 + 0.04 = 0.68 P(x1 = 3) = 0.16
Observation at state x1: y1 = Door
Compute numerator product for each x1, then normalize
P(x1 |y1=Door) α P(y1=Door|x1)P(x1)
P(x1 = 1 | y1 = Door) α P(y1 = Door | x1 = 1) P(x1 = 1) = 0.1 * 0.16 = 0.016 P(x1 = 2 | y1 = Door) α P(y1 = Door | x1 = 2) P(x1 = 2) = 0.9 * 0.68 = 0.612 P(x1 = 3 | y1 = Door) α P(y1 = Door | x1 = 3) P(x1 = 3) = 0.1 * 0.16 = 0.016

1-D example
What if we did not know x0, but only had a belief P(x0)?
P(x0): P(x0=1)=0.8 P(x0=2)=0.2
P(x1 = 1) = 0.16 P(x1 = 2) = 0.64 + 0.04 = 0.68 P(x1 = 3) = 0.16
Observation at state x1: y1 = Door
Compute numerator product for each x1, then normalize
P(x1 |y1=Door) α P(y1=Door|x1)P(x1)
P(x1 = 1 | y1 = Door) α P(y1 = Door | x1 = 1) P(x1 = 1) = 0.1 * 0.16 = 0.016 P(x1 = 2 | y1 = Door) α P(y1 = Door | x1 = 2) P(x1 = 2) = 0.9 * 0.68 = 0.612 P(x1 = 3 | y1 = Door) α P(y1 = Door | x1 = 3) P(x1 = 3) = 0.1 * 0.16 = 0.016
0.016 + 0.612 + 0.016 = 0.644 ≠ 1 → That’s okay, we normalize

1-D example
What if we did not know x0, but only had a belief P(x0)?
P(x0): P(x0=1)=0.8 P(x0=2)=0.2
P(x1 = 1) = 0.16 P(x1 = 2) = 0.64 + 0.04 = 0.68 P(x1 = 3) = 0.16
Observation at state x1: y1 = Door
Compute numerator product for each x1, then normalize
P(x1 |y1=Door) α P(y1=Door|x1)P(x1)
P(x1 = 1 | y1 = Door) α P(y1 = Door | x1 = 1) P(x1 = 1) = 0.1 * 0.16 = 0.016 P(x1 = 2 | y1 = Door) α P(y1 = Door | x1 = 2) P(x1 = 2) = 0.9 * 0.68 = 0.612 P(x1 = 3 | y1 = Door) α P(y1 = Door | x1 = 3) P(x1 = 3) = 0.1 * 0.16 = 0.016
0.016 + 0.612 + 0.016 = 0.644 ≠ 1 → That’s okay, we normalize P(x1 = 1 | y1 = Door) = 0.016 / (0.016 + 0.612 + 0.016) ≈ 0.025
P(x1 = 2 | y1 = Door) ≈ 0.950 P(x1 = 3 | y1 = Door) ≈ 0.025

Recap: 1-D example
1
2
3
4
Consider a 1-D grid world
The agent can only move right
What if agent does not know where it is exactly? – Belief: Probability distribution over states What information can we use to infer our state? – Noisy observations

Hidden Markov Models

Recursive forward filtering in HMMs
1
2
3
4
Consider a 1-D grid world
The agent can only move right
A Hidden Markov Model (HMM) is specified by 3 things: – Initial belief P(x0)
– Transition model P(xt+1 | xt)
– Observation model P(yt | xt) (or emission model P(et | xt))
61

Recursive forward filtering in HMMs
A Hidden Markov Model (HMM) is specified by 3 things: – Initial belief P(x0)
– Transition model P(xt+1 | xt)
– Observation model P(yt | xt) (or emission model P(et | xt))
b0 = Initial belief
For t = 1 to T:
Compute prediction step
Compute bt-1 → t using bt-1 and transition model
Compute observation step
Compute bt using bt-1 → t and observation model
67

Forward filtering (prediction step) More generally, at every time step:
1
2
3
4
68

Forward filtering (observation step) More generally, at every time step:
1
2
3
4
69

Mobile robot localization (Hallway example)
From
“Probabilistic Robotics” (Ch. 7-8)
by
Sebastian Thrun, Wolfram Burgard,
& Dieter Fox
Discrete case;
Exact HMM inference
70

Published by admin

Leave a Reply Cancel reply