Ve492: Introduction to Artificial Intelligence
Hidden Markov Models II
Paul M-SJTU Joint Institute
Slides adapted from http://ai.berkeley.edu, AIMA, UM, CMU
Copyright By PowCoder代写 加微信 powcoder
Learning Objectives
❖ How to perform approximate inference in HMMs?
❖ How to find the most likely explanation?
❖ What is a dynamic Bayes’ net?
❖ Particle Filtering
❖ Viterbi Algorithm for Most Likely Explanation
❖ Dynamic Bayesian Network
Quiz: Algorithms for Filtering
❖ Which algorithms can be applied to the filtering task?
❖ Variable elimination
❖ Prior sampling
❖ Rejection sampling
❖ Likelihood weighting
❖ Gibbs sampling
Limitations of Current Algorithms
❖ Exact inference infeasible if state space is large or continuous
❖ e.g., when |𝑋| is more than 106 or so (tracking 3 ghosts in a 10×20 world)
❖ e.g., robot localization
X0 X1 X2 X3 E1 E2 E3
❖ Previous sampling methods do not exploit the temporal structure of an HMM
Particle Filtering
❖ PF = approximate inference for filtering task
❖ Principle of Particle Filtering
❖ Track samples of 𝑋!, 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
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,manyxmayhaveP(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)
❖ In PF, a set of samples approximates 𝑓
!:# # # !:#
(𝑋 ) = 𝑃(𝑋 |𝑒 )
Particle Filtering: Elapse Time
❖ This first step captures the passage of 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
❖ New particles approximates: ∑"!𝑃(𝑋!#$|𝑥!)𝑓$:!(𝑥!)
❖ Consistency: If enough samples, close to exact values before and after
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: Resample
❖ Particles receive weights corresponding to P(e’ | X’)
❖ Rather than tracking weighted samples, we resample
❖ 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
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)
Summary: Particle Filtering
❖ Particles: track samples of states rather than an explicit distribution
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:
❖ Weknowthemap,butnottherobot’sposition
❖ Observationsmaybevectorsofrangefinderreadings ❖ Statespaceandreadingsaretypicallycontinuous
❖ Particlefilteringisamaintechnique
[ , et al.]
Most Likely Explanation
Inference tasks
❖ Filtering: P(Xt|e1:t)
❖ belief state—input to the decision process of a rational agent
❖ Prediction: P(Xt+k|e1:t) for k > 0
❖ evaluation of possible action sequences; like filtering without
the evidence
❖ Smoothing: P(Xk|e1:t) for 0 ≤ k < t
❖ better estimate of past states, essential for learning
❖ Most likely explanation: arg maxx1:t P(x1:t | e1:t)
❖ speech recognition, decoding with a noisy channel
HMMs: MLE Queries
❖ HMMs defined by
❖ States 𝑋
❖ Observations 𝐸
❖ Initial distribution: 𝑃(𝑋!)
❖ Transitions: 𝑃(𝑋"|𝑋"#!)
❖ Emissions: 𝑃(𝐸|𝑋)
X1 X2 X3 X4 X5 E1 E2 E3 E4 E5
❖ New query: most likely explanation: 𝑎𝑟𝑔𝑚𝑎𝑥)!:#𝑃(𝑥*:,|𝑒*:,)
❖ New method: the Viterbi algorithm
State Trellis
❖ State trellis: graph of states and transitions over time
❖ Each arc represents some transition
❖ Each arc has weight
❖ Each path is a sequence of states
❖ Product of weights on a path = sequence’s probability along with the evidence
❖ Forward algorithm computes sums of paths, Viterbi computes best paths
Forward / Viterbi algorithms
X1 X2 ... Forward Algorithm (sum)
For each state at time t, keep track of the total probability of all paths to it
f1:t+1 = FORWARD(f1:t , et+1)
= α P(et+1|Xt+1) åxt P(Xt+1| xt) f1:t
Viterbi Algorithm (max)
For each state at time t, keep track of
the maximum probability of any path to it
m1:t+1 = VITERBI(m1:t , et+1)
= P(et+1|Xt+1) maxxt P(Xt+1| xt) m1:t
Why is This True?
How About the MLE Path?
A Tricky Counter-Example
How to Recover the MLE Path?
Follow the Breadcrumbs...
Follow the Breadcrumbs...
Viterbi Algorithm
P(Wt|Wt-1)
0.18 sun 0.72 0s.u07n6 0.18 0.s0u1n36
0.09 0.01 0r.a3i1n5 0.24
0r.a0i2n2 0.06 0r.0a1in38 0.63
X1 X2 X3 XT
Time complexity?
Space complexity? O(|X| T)
Number of paths?
U3=false U4=true
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
Exact Inference in DBNs
❖ Variable elimination applies to dynamic Bayes nets
❖ Procedure: “unroll” the network for T time steps, then eliminate variables
until P(XT|e1:T) is computed
❖ 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(E2a |G2a ) * P(E2b |G2b )
❖ Resample: Select prior samples (tuples of values) in proportion to their likelihood
Concluding Remarks
❖ Hidden Markov Models
❖ Approximate inference via particle filtering
❖ Viterbi algorithm for MLE query
❖ Dynamic Bayes nets: compact representation of HMMs
❖ For more information:
❖ AIMA, Chapter 15 for Probabilistic Reasoning over Time
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com