CS代考 Ve492: Introduction to Artificial Intelligence

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