CS代写 Probabilistic Reasoning over Time: Temporal Inference

Probabilistic Reasoning over Time: Temporal Inference
CSci 5512: Artificial Intelligence II
Instructor:
February 3, 2022

Copyright By PowCoder代写 加微信 powcoder

Instructor:
Probabilistic Reasoning over Time:Temporal Inference

Announcements
HW1 posted (due Thu Feb 10)
Probabilistic Reasoning over Time:Temporal Inference
Instructor:

Time and uncertainty
The world changes
Rational agent needs to track and predict Example: Car diagnosis vs. Diabetes
Consider state and evidence variables over time Xt = set of unobservable state variables at time t
Example: BloodSugart, StomachContentst, etc. Et = set of observable evidence variables at time t Example: MeasuredBloodSugart, FoodEatent, etc.
Time can be discrete or continuous Notation: Xa:b =Xa,Xa+1,…,Xb−1,Xb
Probabilistic Reasoning over Time:Temporal Inference
Instructor:

Markov Processes (Markov Chains)
Construct a Bayes net from these variables: Parents? Markov assumption Xt depends on bounded subset of X0:t−1
First-order: P(Xt|X0:t−1) = P(Xt|Xt−1) Second-order: P(Xt|X0:t−1)=P(Xt|Xt−2,Xt−1)
Sensor Markov assumption: P(Et|X0:t,E0:t−1) = P(Et|Xt) Stationary process:
Transition model P(Xt|Xt−1) fixed for all t Sensor model P(Et|Xt) fixed for all t
Probabilistic Reasoning over Time:Temporal Inference
Instructor:

First-order Markov assumption often not true in real world Possible fixes:
Increase order of Markov process
Augment state, e.g., add Tempt, Pressuret
Example: Robot Motion
Augment position and velocity with Batteryt
Probabilistic Reasoning over Time:Temporal Inference
Instructor:

Inference Tasks
Filtering: P(Xt|e1:t)
Belief state is input to the decision process
Prediction: P(Xt+k|e1:t) for k > 0 Evaluation of possible state 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: argmaxx1:t P(x1:t|e1:t) Example: Speech recognition, decoding from noisy channel Probabilistic Reasoning over Time:Temporal Inference Instructor: Aim: A recursive state estimation algorithm P(Xt+1|e1:t+1) = f(et+1,P(Xt|e1:t)) From Bayes rule P(Xt+1|e1:t+1) = P(Xt+1|e1:t,et+1) = αP(et+1|Xt+1,e1:t)P(Xt+1|e1:t) = αP(et+1|Xt+1)P(Xt+1|e1:t) Probabilistic Reasoning over Time:Temporal Inference Instructor: Filtering (cont.) P(Xt+1|e1:t+1) = αP(et+1|Xt+1)P(Xt+1|e1:t) 􏳎 􏳍􏳌 􏳏􏳎 􏳍􏳌 􏳏 Update Prediction First term obtained from CPT Expanding the second term P(Xt+1|e1:t+1) = αP(et+1|Xt+1)􏳇P(Xt+1|xt,e1:t)P(xt|e1:t) xt = αP(et+1|Xt+1)􏳇 P(Xt+1|xt) P(xt|e1:t) 􏳎 􏳍􏳌 􏳏xt 􏳎 􏳍􏳌 􏳏􏳎 􏳍􏳌 􏳏 Sensor Model Transition Model Recursion Recursive filtering f1:t+1 = αForward(f1:t,et+1) where f1:t = P(Xt|e1:t) Time and space requirement is constant (independent of t) Probabilistic Reasoning over Time:Temporal Inference Instructor: Umbrella Example Instructor: Probabilistic Reasoning over Time:Temporal Inference Filtering Example Update Prediction 􏳌 􏳏􏳎 􏳍􏳌 􏳏􏳎 􏳍 P(Xt+1|e1:t+1) = α P(et+1|Xt+1) P(Xt+1|e1:t ) = αP(et+1|Xt+1) 􏳇 P(Xt+1|xt )P(xt |e1:t ) On Day 0, no observations so P(R0) = ⟨0.5, 0.5⟩ On Day 1, umbrella appears so U1 = T and prediction term is: P(R1) = 􏳇 P(R1|r0)P(r0) r0 = ⟨0.7, 0.3⟩ × 0.5 + ⟨0.3, 0.7⟩ × 0.5 = ⟨0.5, 0.5⟩ Update the prediction with evidence gives P(R1|u1) = αP(u1|R1)P(R1) = α⟨0.9, 0.2⟩ × ⟨0.5, 0.5⟩ ≈ ⟨0.818, 0.182⟩ Probabilistic Reasoning over Time:Temporal Inference Instructor: Filtering Example (cont.) Instructor: Probabilistic Reasoning over Time:Temporal Inference Prediction Prediction is similar to filtering Without new evidence Filtering does one step prediction For prediction P(Xt+k+1|e1:t) = 􏳇P(Xt+k+1|xt+k)P(xt+k|e1:t) xt +k How far in the future can we prediction? After evidence stops, prediction is running a Markov chain limk→∞ P(Xt+k|e1:t) converges to the stationary distribution Probabilistic Reasoning over Time:Temporal Inference Instructor: Umbrella Example Instructor: Probabilistic Reasoning over Time:Temporal Inference Prediction Example On Day 2, umbrella appears so U2 = T and the prediction probability is: P(R2|u1) = 􏳇 P(R2|r1)P(r1|u1) r1 = ⟨0.7, 0.3⟩ × 0.818 + ⟨0.3, 0.7⟩ × 0.182 ≈ ⟨0.627, 0.373⟩ Updating prediction with evidence gives: P(R2|u1, u2) = αP(u2|R2)P(R2|u1) = α⟨0.9, 0.2⟩ × ⟨0.627, 0.373⟩ = α⟨0.565, 0.075⟩ ≈ ⟨0.883, 0.117⟩ Probabilistic Reasoning over Time:Temporal Inference Instructor: Prediction Example (cont.) Instructor: Probabilistic Reasoning over Time:Temporal Inference Divide evidence e1:t into e1:k, ek+1:t P(Xk|e1:t) = P(Xk|e1:k,ek+1:t) = αP(Xk|e1:k)P(ek+1:t|Xk,e1:k) = αP(Xk|e1:k)P(ek+1:t|Xk) = αf1:kbk+1:t Forward message f1:k is filtering Probabilistic Reasoning over Time:Temporal Inference Instructor: Smoothing (cont.) Backward message computed by a backwards recursion: P(ek+1:t|Xk) = 􏳇P(ek+1:t|Xk,xk+1)P(xk+1|Xk) xk +1 = 􏳇P(ek+1:t|xk+1)P(xk+1|Xk) xk +1 = 􏳇P(ek+1|xk+1)P(ek+2:t|xk+1) P(xk+1|Xk) xk+1􏳎 􏳍􏳌 􏳏􏳎 􏳍􏳌 􏳏􏳎 􏳍􏳌 􏳏 Sensor Model Recursion Transition Model bk+1:t = P(ek+1:t|Xk) = αBackward(bk+2:t,ek+1) The smoothed probability P(Xk|e1:t) = αf1:kbk+1:t Probabilistic Reasoning over Time:Temporal Inference Instructor: Umbrella Example Instructor: Probabilistic Reasoning over Time:Temporal Inference Smoothing Example After 2 days, the smoothed probability P(R1|u1, u2) = αP(R1|u1)P(u2|R1) We already know P(R1|u1) = ⟨0.818, 0.182⟩ from filtering step The backward recursion P(u2|R1) = 􏳇 P(u2|r2)P(|r2)P(r2|R1) r2 = (0.9 × 1 × ⟨0.7, 0.3⟩) + (0.2 × 1 × ⟨0.3, 0.7⟩) = ⟨0.69, 0.41⟩ Plugging back the value, the smoothed probability P(R1|u1, u2) = α⟨0.818, 0.182⟩ × ⟨0.69, 0.41⟩ ≈ ⟨0.883, 0.117⟩ Probabilistic Reasoning over Time:Temporal Inference Instructor: Smoothing Example (cont.) Forward-Backward algorithm: Cache forward messages along the way Time linear in t (polytree inference), space O(t|f|) Probabilistic Reasoning over Time:Temporal Inference Instructor: Most Likely Sequence Most likely sequence ̸= sequence of most likely states Most likely path to state xt+1 consists of most likely path to There is recursive relationship between most likely paths to each state xt+1 and xt We will use recursive property to construct message passing algorithm Probabilistic Reasoning over Time:Temporal Inference Instructor: Most Likely Sequence Most likely path to each Xt+1 maxP(x1:t,Xt+1,e1:t+1) = maxP(et+1|x1:t,Xt+1,e1:t)P(x1:t,Xt+1,e1:t) = P(et+1|Xt+1)maxP(Xt+1|xt) max P(x1:t−1,xt,e1:t) xt x1:t −1 Note last term maxx1:t−1 P(x1:t−1,xt,e1:t) is recursive entry for state xt in message vector Identical to filtering, except summation replaced by maxx1:t Computes the probability of the most likely path to state i To find actual sequence of states, must record, for each state, best state that leads to it Algorithm called the Viterbi algorithm Probabilistic Reasoning over Time:Temporal Inference Instructor: Viterbi Example Optimal sequence found by following bold arrows backwards from best final state Probabilistic Reasoning over Time:Temporal Inference Instructor: 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com