CIS 471/571(Fall 2020): Introduction to Artificial Intelligence
Lecture 18: HMMs, Particle Filters
Thanh H. Nguyen
Source: http://ai.berkeley.edu/home.html
Announcement
§Class on Thursday, Dec 03rd §Exam review
§End-of-course Survey
§Open until 06:00 PM on Fri, Dec 04th
Thanh H. Nguyen
11/30/20
2
Today
§HMMs §Particle filters
§Applications:
§Robot localization / mapping
Recap: Reasoning Over Time
§Markov models
X1 X2 X3 X4
§Hidden Markov models
X1 X2 X3 X4 X5
E1 E2 E3 E4 E5
0.3
0.7
rain
sun
0.7
0.3
X
E
P
rain
umbrella
0.9
rain
no umbrella
0.1
sun
umbrella
0.2
sun
no umbrella
0.8
Filtering / Monitoring
§ Filtering, or monitoring, is the task of tracking the distribution Bt(X) = Pt(Xt | e1, …, et) (the belief state) over time
§ We start with B1(X) in an initial setting, usually uniform §As time passes, or we get observations, we update B(X)
The Forward Algorithm
§ We are given evidence at each time and want to know §Induction: assuming we have current belief
§ Intermediate belief update: 𝐵$ (𝑋) = 𝑃 𝑋 |𝑒 !”# !”# #:!
𝑃 𝑋)*+|𝑒+:()*+) ← 𝑃 𝑋)*+|𝑒+:) ← 𝑃 𝑋)|𝑒+:)
Observation Passage of time update update
Example: Weather HMM
B(+r) = 0.5 B(-r) = 0.5
Rain0
B’(+r) = 0.5 B’(-r) = 0.5
B(+r) = 0.818 B(-r) = 0.182
Rain1
Umbrella1
B’(+r) = 0.627 B’(-r) = 0.373
B(+r) = 0.883 B(-r) = 0.117
Rain2
Umbrella2
Rt
Rt+1
P(Rt+1|Rt)
+r
+r
0.7
+r
-r
0.3
-r
+r
0.3
-r
-r
0.7
Rt
+r
+r
-r
-r
Ut
+u
-u
+u
-u
P(Ut|Rt)
0.9
0.1
0.2
0.8
Particle Filtering
Particle Filtering
§ Filtering: approximate solution
§ Sometimes |X| is too big to use exact inference § |X| may be too big to even store B(X)
§ E.g. X is continuous
§ Solution: approximate inference
§ Track samples of X, not all values
§ Samples are called particles
§ Time per step is linear in the number of samples § But: number needed may be large
§ In memory: list of particles, not states
§ This is how robot localization works in practice § Particle is just new name for sample
0.0
0.1
0.0
0.0
0.0
0.2
0.0
0.2
0.5
Representation: Particles
§ Our representation of P(X) is now a list of N particles (samples) § Generally, N << |X|
§ Storing map from X to counts would defeat the point
§ P(x) approximated by number of particles with value x §So, many x may have P(x) = 0!
§ More particles, more accuracy
§ For now, all particles have a weight of 1
Particles:
(3,3) (2,3) (3,3) (3,2) (3,3) (3,2) (1,2) (3,3) (3,3) (2,3)
Particle Filtering: Elapse Time
§ Each particle is moved by sampling its next position from the transition model
§ This is like prior sampling – samples’ frequencies reflect the transition probabilities
§ Here, most samples move clockwise, but some move in another direction or stay in place
§ This captures the passage of time
§ If enough samples, close to exact values before and after (consistent)
Particles:
(3,3) (2,3) (3,3) (3,2) (3,3) (3,2) (1,2) (3,3) (3,3) (2,3)
Particles:
(3,2) (2,3) (3,2) (3,1) (3,3) (3,2) (1,3) (2,3) (3,2) (2,2)
Particle Filtering: Observe
§ Slightly trickier:
§ Don’t sample observation, fix it
§ Similar to likelihood weighting, downweight samples based on the evidence
Particles:
(3,2) (2,3) (3,2) (3,1) (3,3) (3,2) (1,3) (2,3) (3,2) (2,2)
Particles:
(3,2) w=.9 (2,3) w=.2 (3,2) w=.9 (3,1) w=.4 (3,3) w=.4 (3,2) w=.9 (1,3) w=.1 (2,3) w=.2 (3,2) w=.9 (2,2) w=.4
§ As before, the probabilities don’t sum to one, since all have been downweighted (in fact they now sum to (N times) an approximation of P(e))
Particle Filtering: Resample
§Rather than tracking weighted samples, we resample
Particles:
(3,2) w=.9 (2,3) w=.2 (3,2) w=.9 (3,1) w=.4 (3,3) w=.4 (3,2) w=.9 (1,3) w=.1 (2,3) w=.2 (3,2) w=.9 (2,2) w=.4
(New) Particles:
(3,2) (2,2) (3,2) (2,3) (3,3) (3,2) (1,3) (2,3) (3,2) (3,2)
§ N times, we choose from our weighted sample distribution (i.e. draw with replacement)
§This is equivalent to renormalizing the distribution
§ Now the update is complete for this time step, continue with the next one
Recap: Particle Filtering
§Particles: track samples of states rather than an explicit
distribution
Elapse
Weight
Resample
Particles:
(3,3) (2,3) (3,3) (3,2) (3,3) (3,2) (1,2) (3,3) (3,3) (2,3)
Particles:
(3,2) (2,3) (3,2) (3,1) (3,3) (3,2) (1,3) (2,3) (3,2) (2,2)
Particles:
(3,2) w=.9 (2,3) w=.2 (3,2) w=.9 (3,1) w=.4 (3,3) w=.4 (3,2) w=.9 (1,3) w=.1 (2,3) w=.2 (3,2) w=.9 (2,2) w=.4
(New) Particles:
(3,2) (2,2) (3,2) (2,3) (3,3) (3,2) (1,3) (2,3) (3,2) (3,2)
Robot Localization
§In robot localization:
§ We know the map, but not the robot’s position
§ Observations may be vectors of range finder readings
§ State space and readings are typically continuous (works basically like a very fine grid) and so we cannot store B(X)
§ Particle filtering is a main technique
Particle Filter Localization (Sonar)
[Video: global-sonar-uw-annotated.avi]
Dynamic Bayes Nets
Dynamic Bayes Nets (DBNs)
§ We want to track multiple variables over time, using multiple sources of evidence
§ Idea: Repeat a fixed Bayes net structure at each time
§ Variables from time t can condition on those from t-1
t =1 t =2 t =3
G1a
G1b
E1a E1b
G2a
G2b
E2a E2b
G3a
G3b
E3a E3b
§ Dynamic Bayes nets are a generalization of HMMs
[Demo: pacman sonar ghost DBN model (L15D6)]
Exact Inference in DBNs
§ Variable elimination applies to dynamic Bayes nets
§ Procedure: “unroll” the network for T time steps, then eliminate variables until
t =1 t =2 t =3
P(XT|e1:T) is computed
G1a
G1b
E1a E1b
G2a
G2b
E2a E2b
G3a
G3b
E3a E3b
§ Online belief updates: Eliminate all variables from the previous time step; store factors for current time only
DBN Particle Filters
§ A particle is a complete sample for a time step
§ Initialize: Generate prior samples for the t=1 Bayes net
§ Example particle: G1a = (3,3) G1b = (5,3)
§ Elapse time: Sample a successor for each particle
§ Example successor: G2a = (2,3) G2b = (6,3)
§ Observe: Weight each entire sample by the likelihood of the evidence conditioned on
the sample
§ Likelihood: P(E1a |G1a ) * P(E1b |G1b )
§ Resample: Select prior samples (tuples of values) in proportion to their likelihood
Most Likely Explanation
HMMs: MLE Queries
§ HMMs defined by
§ States X
§ Observations E
§ Initial distribution: § Transitions:
§ Emissions:
§ New query: most likely explanation: § New method: the Viterbi algorithm
X1 X2 X3 X4 X5 E1 E2 E3 E4 E5
State Trellis
§ State trellis: graph of states and transitions over time sun sun sun sun
rain rain rain rain
§ Each arc represents some transition
§ Each arc has weight
§ Each path is a sequence of states
§ The product of weights on a path is that sequence’s probability along with the evidence § Forward algorithm computes sums of paths, Viterbi computes best paths
Forward / Viterbi Algorithms
sun sun
rain rain
Forward Algorithm (Sum)
sun sun
rain rain
Viterbi Algorithm (Max)