Probabilistic Reasoning over Time:
CSci 5512: Artificial Intelligence II
Instructor:
February 8, 2022
Copyright By PowCoder代写 加微信 powcoder
Instructor:
Probabilistic Reasoning over Time:
Announcements
HW1 due in 2 days (Feb 10)
Probabilistic Reasoning over Time:
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:
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:
Instructor:
Hidden Markov Models
Xt is a single, discrete variable (usually Et is too) Domain of Xt is {1,…,S}
Transition matrix: Tij = P(Xt = j|Xt−1 = i), e.g., 0.7 0.3
Sensor matrix: Eih = P(Et = h|Xt = i) for each time step Message passing viewpoint:
Forward-Backward is a sum-product algorithm Viterbi is a max-product algorithm
Probabilistic Reasoning over Time:
Instructor:
Rain Network
Instructor:
Probabilistic Reasoning over Time:
Kalman filters
Xt and Et are (multi-variate) continuous variables Applications in Tracking and Control
Planes, Robots, Economies, etc. Key Assumptions
Gaussian prior P(X0)
Linear Gaussian transition model P(Xt+1|Xt) Linear Gaussian sensor model P(Et|Xt)
Probabilistic Reasoning over Time:
Instructor:
Multi-variate Gaussians
A r.v. has multi-variate Gaussian distribution if
1 1 ⊤−1 p(x|μ,Σ)= (2π)d/2|Σ|exp −2(x−μ) Σ (x−μ)
μ = E [X ] is the mean of the distribution Σ is the covariance matrix
Σ = E[(X − μ)(X − μ)⊤] In 1-dimension, the density function is
2 1 (x−μ)2 p(x|μ,σ)=√2πσexp − 2σ2
Probabilistic Reasoning over Time:
Instructor:
Updating Gaussian distributions
Prediction step: One step prediction of posterior P(Xt+1|e1:t) If P(Xt|e1:t) is Gaussian, then posterior is Gaussian
P(Xt+1|e1:t) =
Filtering: Posterior P(Xt+1|e1:t+1) based on evidence
If predicted posterior is Gaussian, then filtered posterior is Gaussian
P(Xt+1|e1:t+1) = αP(et+1|Xt+1)P(Xt+1|e1:t)
P(Xt|e1:t) is multi-variate Gaussian N(μt,Σt), ∀t General (non-linear, non-Gaussian) process
The posterior is intractable Inference is hard
P(Xt+1|xt)P(xt|e1:t)dxt
Probabilistic Reasoning over Time:
Instructor:
Simple 1-D example
Gaussian random walk on X-axis, s.d. σx, sensor s.d. σz
μ = (σt2 + σx2)zt+1 + σz2μt σ2 = (σt2 + σx2)σz2 t+1 σt2 +σx2 +σz2 t+1 σt2 +σx2 +σz2
Instructor:
Probabilistic Reasoning over Time:
General Kalman update
Transition and sensor models:
P(xt+1|xt) = N(xt+1;(Fxt,Σx)) P(zt|xt) = N(zt;(Hxt,Σz))
Transition parameters
F is the matrix for state transition Σx is the transition noise covariance
Sensor parameters
H is the matrix for sensor output Σz is the sensor noise covariance
Probabilistic Reasoning over Time:
Instructor:
General Kalman update (cont.)
Filter computes the following update
μt+1 =Fμt +Kt+1(zt+1 −HFμt) Σt+1 =(I −Kt+1H)(FΣtF⊤ +Σx)
The Kalman gain
Kt+1 =(FΣtF⊤ +Σx)H⊤(H(FΣtF⊤ +Σx)H⊤ +Σz)−1
Fμt ispredictedstateatt+1 HFμt is predicted observation
zt +1 − HF μt is error in predicted observation which is corrected by Kt+1
Kt+1 is measure of how seriously to take new observation Σt and Kt can be computed offline; they do not depend on observation sequence
Probabilistic Reasoning over Time:
Instructor:
2-D tracking example: Filtering
Instructor:
Probabilistic Reasoning over Time:
2-D tracking example: Smoothing
Instructor:
Probabilistic Reasoning over Time:
Where it breaks
Cannot be applied if the transition model is nonlinear Extended Kalman Filter: Locally linear transitions Fails if system is locally unsmooth
Probabilistic Reasoning over Time:
Instructor:
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com