CS计算机代考程序代写 Hidden Markov Mode algorithm CIS 471/571(Fall 2020): Introduction to Artificial Intelligence

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)