#### Transcript Probabilistic Reasoning over Time Russell and Norvig: ch 15

Probabilistic Reasoning over Time Russell and Norvig: ch 15 Temporal Probabilistic Agent sensors ? environment agent actuators t1, t2, t3, … Time and Uncertainty The world changes, we need to track and predict it Examples: diabetes management, traffic monitoring Basic idea: copy state and evidence variables for each time step Xt – set of unobservable state variables at time t e.g., BloodSugart, StomachContentst Et – set of evidence variables at time t e.g., MeasuredBloodSugart, PulseRatet, FoodEatent Assumes discrete time steps States and Observations Process of change is viewed as series of snapshots, each describing the state of the world at a particular time Each time slice involves a set or random variables indexed by t: 1. 2. the set of unobservable state variables Xt the set of observable evidence variable Et The observation at time t is Et = et for some set of values et The notation Xa:b denotes the set of variables from Xa to Xb Stationary Process/Markov Assumption Markov Assumption: Xt depends on some previous Xis First-order Markov process: P(Xt|X0:t-1) = P(Xt|Xt-1) kth order: depends on previous k time steps Sensor Markov assumption: P(Et|X0:t, E0:t-1) = P(Et|Xt) Assume stationary process: transition model P(Xt|Xt-1) and sensor model P(Et|Xt) are the same for all t In a stationary process, the changes in the world state are governed by laws that do not themselves change over time Which mode is right is determined by domain. Eg. If a particle is executing a random walk along the x-axis, changing its position by +/-1 at each time step, then using the x-coordinate as the state gives a firstorder Markov process. Complete Joint Distribution Given: Transition model: P(Xt|Xt-1) Sensor model: P(Et|Xt) Prior probability: P(X0) Then we can specify complete joint distribution: t P( X 0 , X1 ,..., X t , E1 ,..., E t ) P( X 0 ) P( X i | X i 1 ) P( E i | X i ) i 1 Example Raint-1 Umbrellat-1 Rt-1 P(Rt|Rt-1) T F 0.7 0.3 Raint Raint+1 Umbrellat Umbrellat+1 Rt P(Ut|Rt) T F 0.9 0.2 Assumption modification first-order Markov process is used in previous example There are two possible fixes if the approximation proves too inaccurate: 1. Increasing the order of the Markov process model. Use second-order model by adding Raint-2 as a parent of Rain, which might give slightly more accurate predictions (for example, in Palo ,Alto it very rarely rains more than two days in a row). 2. Increasing the set of state variables. For example, we could add Season{ to allow us to incorporate historical records of rainy seasons, or we could add Temperaturet, Humidityt and Pressuret to allow us to use a physical model of rainy conditions. Note adding state variables might improve the system's predictive power but also increases the prediction requirements we now have to predict the new variables as well. add new sensors (Eg. measurements of temperature and pressure Example: robot wandering Problem: tracking a robot wandering randomly on the X-Y plane state variables: position and velocity the new position can be calculated by Newton's laws the velocity may change unpredictably Eg. battery-powered robot’s velocity may be effected by a battery exhaustion Example: robot wandering Battery exhaustion depends on how much power was used by all previous maneuvers, the Markov property is violated. Add charge level Batteryt as state variable new model to predict Batteryt from Batteryt-1 and the velocity New sensors for charge level Inference Tasks Filtering or monitoring: P(Xt|e1,…,et) computing current belief state, given all evidence to date Prediction: P(Xt+k|e1,…,et) computing prob. of some future state Smoothing: P(Xk|e1,…,et) computing prob. of past state (hindsight)(0≤k ≤t) Most likely explanation: arg maxx1,..xtP(x1,…,xt|e1,…,et) given sequence of observation, find sequence of states that is most likely to have generated those observations. Examples Filtering: What is the probability that it is raining today, given all the umbrella observations up through today? Prediction: What is the probability that it will rain the day after tomorrow, given all the umbrella observations up through today? Smoothing: What is the probability that it rained yesterday, given all the umbrella observations through today? Most likely explanation: if the umbrella appeared the first three days but not on the fourth, what is the most likely weather sequence to produce these umbrella sightings? Filtering & Prediction We use recursive estimation to compute P(Xt+1 | e1:t+1) as a function of et+1 and P(Xt | e1:t) We can write this as follows: P( X t 1 | e1:t 1 ) P( X t 1 | e1:t , et 1 )(dividing up the evidence) P (et 1 | X t 1 , e1:t ) P ( X t 1 | e1:t )(using Bayes' rule) P (et 1 | X t 1 ) P ( X t 1 | e1:t )(by the Markov property of evidence). P (et 1 | X t 1 ) P ( X t 1 | xt ) P ( xt | e1:t )(using the Markov property) xt P(et+l lXt+1) is obtainable directly from the sensor model This leads to a recursive definition f1:t+1 = FORWARD(f1:t:t,et+1) Example: rain & umbrella p. 543 Model,P(R0) =<0.5,0.5> Smoothing Compute P(Xk|e1:t) for 0<= k < t Using a backward message bk+1:t = P(Ek+1:t | Xk), we obtain P(Xk|e1:t) = f1:kbk+1:t The backward message can be computed using bk 1:t P(ek 1 | xk 1 )P(ek 2:t | xk 1 )P(xk 1 | Xk ) xk 1 (15.7) This leads to a recursive definition Bk+1:t = BACKWARD(bk+2:t,ek+1:t) bk 1:t P(ek 1 | xk 1 )P(ek 2:t | xk 1 )P(xk 1 | Xk ) Example from R&N: p. 545 xk 1 computing the smoothed estimate for the probability of rain at t = 1, given the umbrella observations on days 1 and 2. According to E.15.7 Pluged into E.15.8 Probabilistic Temporal Models Hidden Markov Models (HMMs) Kalman Filters Dynamic Bayesian Networks (DBNs) Hidden Markov Models (HMMs) Further simplification: Only one state variable. We can use matrices, now. Ti,j = P(Xt=j|Xt-1=i) Tij is the probability of a transition from state i to state j. transition matrix for the umbrella world: Hidden Markov Models (HMMs) sensor model:diagonal matrix Ot diagonal entries are given by the values P(et lXt = i) Other entried:0 Umbrella world Hidden Markov Models (HMMs) Example: speech recognition