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