=== p1 ===
Introduction to 
Artificial Intelligence
Chapter 14
Probabilistic Reasoning over Time
Wei-Ta Chu (朱威達)
1

=== p2 ===
• We have mentioned probabilistic reasoning in the context of static worlds. 
• Now consider a slightly different problem: treating a diabetic (糖尿病) patient. 
We have evidence such as recent insulin doses (胰島素劑量), food intake (攝
取), blood sugar measurements, and other physical signs. The task is to assess 
the current state of the patient, including the actual blood sugar level and 
insulin level. Given this information, we can make a decision about the 
patient’s food intake and insulin dose. 
• Blood sugar levels and measurements thereof can change rapidly over time. 
We must model these changes.
Time and Uncertainty
2

=== p3 ===
• We view the world as a series of snapshots, or time slices, each of which 
contains a set of random variables, some observable and some not. 
• We assume some subset of variables is observable in each time slice. We will 
use Xt to denote the set of state variables at time t, which are assumed to be 
unobservable, and Et to denote the set of observable evidence variables. The 
observation at time t is Et = et for some set of values et.
States and observations
3

=== p4 ===
• You are the security guard stationed at a secret underground installation. You 
want to know whether it’s raining today, but your only access to the outside 
world occurs each morning when you see the director coming in with, or 
without, an umbrella. 
• For each day t, the set Et thus contains a single evidence variable Umbrellat or 
Ut for short, and the set Xt contains a single state variable Raint or Rt for short. 
States and observations
4

=== p5 ===
• The interval between time slices also depends on the problem. For diabetes 
monitoring, a suitable interval might be an hour rather than a day. In this 
chapter we assume the interval between slices is fixed, so we can label times 
by integers. 
• Our umbrella world is represented by state variables R0, R1, R2, … and 
evidence variables U1, U2, ... We will use the notation a:b to denote the 
sequence of integers from a to b (inclusive), and the notation Xa:b to denote the 
set of variables from Xa to Xb. 
States and observations
5

=== p6 ===
• The transition model specifies the probability distribution over the latest state 
variables, given the previous values, that is, P(Xt | X0:t−1). 
• Now we face a problem: the set X0:t−1 is unbounded in size as t increases. We 
solve the problem by making a Markov assumption— that the current state 
depends on only a finite fixed number of previous states. 
• The simplest case: the first-order Markov process, in which the current state 
depends only on the previous state and not on any earlier states. 
Transition and sensor models
6

=== p7 ===
• With first-order Markov assumption, we have
• Hence, in a first-order Markov process, the transition model is the conditional 
distribution P(Xt | Xt−1). The transition model for a second-order Markov 
process is the conditional distribution P(Xt | Xt−2, Xt−1). 
• Figure 15.1 shows the Bayesian network structures corresponding to first-
order and second-order Markov processes.
Transition and sensor models
7

=== p8 ===
Transition and sensor models
8
[IMAGE-ONLY]

=== p9 ===
• Even with the Markov assumption there is still a problem: there are infinitely 
many possible values of t. Do we need to specify a different distribution for 
each time step? 
• We avoid this problem by assuming that changes in the world state are caused 
by a stationary process—that is, a process of change that is governed by laws 
that do not themselves change over time. (Don’t confuse stationary with static: 
in a static process, the state itself does not change.) 
• In the umbrella world, then, the conditional probability of rain, P(Rt | Rt−1), is 
the same for all t, and we only have to specify one conditional probability 
table.
Transition and sensor models
9

=== p10 ===
• The sensor model: The evidence variables Et could depend on previous 
variables as well as the current state variables. But, we make a sensor Markov 
assumption as follows:
Thus, P(Et | Xt) is our sensor model (sometimes called the observation 
model). 
• Figure 15.2 shows both the transition model and the sensor model for the 
umbrella example.
Transition and sensor models
10

=== p11 ===
Transition and sensor models
11
[IMAGE-ONLY]

=== p12 ===
• Further, we need to say how everything gets started—the prior probability 
distribution at time 0, P(X0). With that, we have a specification of the 
complete joint distribution over all the variables, using Equation (14.2). For 
any t,
The three terms on the right-hand side are the initial state model P(X0), the 
transition model P(Xi | Xi−1), and the sensor model P(Ei | Xi).
Transition and sensor models
12
(15.3)

=== p13 ===
• First-order Markov process—the probability of rain is assumed to depend only 
on whether it rained the previous day. Whether such an assumption is 
reasonable depends on the domain itself. Sometimes the assumption is exactly 
true.
Transition and sensor models
13

=== p14 ===
• Sometimes the assumption is only approximate. There are two ways to 
improve the accuracy of the approximation: 
• Increasing the order of the Markov process model. For example, we could 
make a second-order model by adding Raint−2 as a parent of Raint. 
• Increasing the set of state variables. For example, we could add Seasont 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.
Transition and sensor models
14

=== p15 ===
• We can formulate the basic inference tasks that must be solved:
• Filtering: This is the task of computing the belief state—the posterior 
distribution over the most recent state—given all evidence to date. 
Filtering is also called state estimation. In our example, we wish to 
compute P(Xt | e1:t). In the umbrella example, this would mean computing 
the probability of rain today, given all the observations of the umbrella 
carrier made so far. 
Inference in Temporal Models
15

=== p16 ===
• We can formulate the basic inference tasks that must be solved:
• Prediction: This is the task of computing the posterior distribution over 
the future state, given all evidence to date. That is, we wish to compute 
P(Xt+k | e1:t) for some k > 0. In the umbrella example, this might mean 
computing the probability of rain three days from now, given all the 
observations to date. 
Inference in Temporal Models
16

=== p17 ===
• We can formulate the basic inference tasks that must be solved:
• Smoothing: This is the task of computing the posterior distribution over a 
past state, given all evidence up to the present. That is, we wish to 
compute P(Xk | e1:t) for some k such that 0 ≤ k < t. In the umbrella 
example, it might mean computing the probability that it rained last 
Wednesday, given all the observations of the umbrella carrier made up to 
today. Smoothing provides a better estimate of the state than was available 
at the time, because it incorporates more evidence. 
Inference in Temporal Models
17

=== p18 ===
• We can formulate the basic inference tasks that must be solved:
• Most likely explanation: Given a sequence of observations, we might 
wish to find the sequence of states that is most likely to have generated 
those observations. That is, we wish to compute argmaxx1:t P(x1:t | e1:t). 
For example, if the umbrella appears on each of the first three days and is 
absent on the fourth, then the most likely explanation is that it rained on 
the first three days and did not rain on the fourth. Algorithms for this task 
are useful in many applications, including speech recognition—where the 
aim is to find the most likely sequence of words, given a series of sounds.
Inference in Temporal Models
18

=== p19 ===
• In addition to these inference tasks, we also have
• Learning: The transition and sensor models can be learned from 
observations.  
The overall process is an instance of the expectation-maximization 
or EM algorithm. 
Inference in Temporal Models
19

=== p20 ===
• A useful filtering algorithm needs to maintain a current state estimate and 
update it, rather than going back over the entire history of percepts for each 
update. 
• In other words, given the result of filtering up to time t, the agent needs to 
compute the result for t + 1 from the new evidence et+1,
for some function f. 
Filtering and prediction
20

=== p21 ===
• This process is called recursive estimation. We can view the calculation as 
being composed of two parts: first, the current state distribution is projected 
forward from t to t+1; then it is updated using the new evidence et+1. This two-
part process emerges quite simply when the formula is rearranged: 
Filtering and prediction
21

=== p22 ===
• α is a normalizing constant used to make probabilities sum up to 1. The second 
term, P(Xt+1 | e1:t) represents a one-step prediction of the next state, and 
P(et+1 | Xt+1) is obtainable directly from the sensor model. Now we obtain the 
one-step prediction for the next state by conditioning on the current state Xt: 
Filtering and prediction
22

=== p23 ===
• Within the summation, the first factor comes from the transition model and the 
second comes from the current state distribution. Hence, we have the desired 
recursive formulation. We can think of the filtered estimate P(Xt | e1:t) as a 
“message” f1:t that is propagated forward along the sequence, modified by each 
transition and updated by each new observation. The process is given by
where FORWARD implements the update described in Equation (15.5) and the 
process begins with f1:0 = P(X0). 
Filtering and prediction
23

=== p24 ===
Filtering and prediction
24
[IMAGE-ONLY]

=== p25 ===
Filtering and prediction
25
Intuitively, the probability of rain increases from day 1 to day 2 because rain persists.

=== p26 ===
• The task of prediction can be seen simply as filtering without the addition of 
new evidence. In fact, the filtering process already incorporates a one-step 
prediction, and it is easy to derive the following recursive computation for 
predicting the state at t + k + 1 from a prediction for t + k:
Naturally, this computation involves only the transition model and not the 
sensor model.
Filtering and prediction
26

=== p27 ===
• Smoothing is the process of computing the distribution over past states given 
evidence up to the present; that is, P(Xk | e1:t) for 0 ≤ k < t. (See Figure 15.3.) 
In anticipation of another recursive message-passing approach, we can split 
the computation into two parts—the evidence up to k and the evidence from 
k + 1 to t,
where “×” represents pointwise multiplication of vectors.
Smoothing
28

=== p28 ===
Smoothing
29
[IMAGE-ONLY]

=== p29 ===
• Here we have defined a “backward” message bk+1:t = P(ek+1:t | Xk ), analogous 
to the forward message f1:k. The forward message f1:k can be computed by 
filtering forward from 1 to k. It turns out that the backward message bk+1:t can 
be computed by a recursive process that runs backward from t:
Smoothing
30

=== p30 ===
• The last step follows by the conditional independence of ek+1 and ek+2:t, given 
Xk+1. Of the three factors in this summation, the first and third are obtained 
directly from the model, and the second is the “recursive call.” Using the 
message notation, we have
where BACKWARD implements the update described in Equation (15.9). 
Smoothing
31

=== p31 ===
• We can now see that the two terms in Equation (15.8) can both be computed 
by recursions through time, one running forward from 1 to k and using the 
filtering equation (15.5) and the other running backward from t to k + 1 and 
using Equation (15.9). 
• The backward phase is initialized with bt+1:t = P(et+1:t | Xt) = P( | Xt)1, where 1
is a vector of 1s. (Because et+1:t is an empty sequence, the probability of 
observing it is 1.)
Smoothing
32

=== p32 ===
Smoothing
33
[IMAGE-ONLY]

=== p33 ===
• Thus, the smoothed estimate for rain on day 1 is higher than the filtered 
estimate (0.818) in this case. This is because the umbrella on day 2 makes it 
more likely to have rained on day 2; in turn, because rain tends to persist, that 
makes it more likely to have rained on day 1. 
• Both the forward and backward recursions take a constant amount of time per 
step; hence, the time complexity of smoothing with respect to evidence e1:t is 
O(t). This is the complexity for smoothing at a particular time step k. If we 
want to smooth the whole sequence, one obvious method is simply to run the 
whole smoothing process once for each time step to be smoothed. This results 
in a time complexity of O(t2). 
Smoothing
34

=== p34 ===
• A better approach uses dynamic programming to reduce the complexity to O(t). 
• The key to the linear-time algorithm is to record the results of forward filtering 
over the whole sequence. Then we run the backward recursion from t down to 
1, computing the smoothed estimate at each step k from the computed back-
ward message bk+1:t and the stored forward message f1:k. The algorithm is 
called the forward–backward algorithm.
Smoothing
35

=== p35 ===
• Suppose that [true, true, false, true, true] is the umbrella sequence for the 
security guard’s first five days on the job. 
• In all, there are 25 possible weather sequences we could pick. Is there a way to 
find the most likely one, short of enumerating all of them?
• We could try this linear-time procedure: use smoothing to find the posterior 
distribution for the weather at each time step; then construct the sequence, 
using at each step the weather that is most likely according to the posterior. 
Finding the most likely sequence
38

=== p36 ===
• View each sequence as a path through a graph whose nodes are the possible 
states at each time step. Such a graph is shown for the umbrella world in 
Figure 15.5(a). 
• Consider the task of finding the most likely path through this graph, where the 
likelihood of any path is the product of the transition probabilities along the 
path and the probabilities of the given observations at each state. 
Finding the most likely sequence
39

=== p37 ===
Finding the most likely sequence
40
[IMAGE-ONLY]

=== p38 ===
• Let’s focus on paths that reach the state Rain5 =true. Because of the Markov 
property, the most likely path to the state Rain5 =true consists of the most 
likely path to some state at time 4 followed by a transition to Rain5 =true; and 
the state at time 4 that will become part of the path to Rain5 =true is whichever 
maximizes the likelihood of that path. In other words, there is a recursive 
relationship between most likely paths to each state xt+1 and most likely paths 
to each state xt.
Finding the most likely sequence
41

=== p39 ===
• Equation (15.11) is identical to the filtering equation (15.5) except that 
Finding the most likely sequence
42

=== p40 ===
• Thus, the algorithm for computing the most likely sequence is similar to 
filtering: it runs forward along the sequence, computing the m message at each 
time step, using Equation (15.11). The progress of this computation is shown 
in Figure 15.5(b). At the end, it will have the probability for the most likely 
sequence reaching each of the final states. One can thus easily select the most 
likely sequence overall (the states outlined in bold). 
•
The optimal sequence is identified by following these bold arrows backwards 
from the best final state.
Finding the most likely sequence
43

=== p41 ===
• The algorithm we have just described is called the Viterbi algorithm. Like the 
filtering algorithm, its time complexity is linear in t, the length of the sequence. 
Unlike filtering, which uses constant space, its space requirement is also linear 
in t. This is because the Viterbi algorithm needs to keep the pointers that 
identify the best sequence leading to each state.
Finding the most likely sequence
44

=== p42 ===
• An HMM is a temporal probabilistic model in which the state of 
the process is described by a single discrete random variable. The 
possible values of the variable are the possible states of the world. 
• The umbrella example described in the preceding section is 
therefore an HMM, since it has just one state variable: Raint. 
Hidden Markov Models
45

=== p43 ===
• Here we make the vacuum problem slightly more realistic by including a 
simple probability model for the robot’s motion and by allowing for noise in 
the sensors. The state variable Xt represents the location of the robot on the 
discrete grid; the domain of this variable is the set of empty squares {s1, . . . , 
sn}. Let NEIGHBORS(s) be the set of empty squares that are adjacent to s and 
let N(s) be the size of that set. Then the transition model for Move action says 
that the robot is equally likely to end up at any neighboring square:
HMM example: Localization
58

=== p44 ===
• We don’t know where the robot starts, so we will assume a uniform 
distribution over all the squares; that is, P(X0 = i) = 1/n. For the particular 
environment we consider (Figure 15.7), n = 42 and the transition matrix T has 
42 × 42 = 1764 entries.
HMM example: Localization
59

=== p45 ===
HMM example: Localization
60
[IMAGE-ONLY]

=== p46 ===
• The sensor variable Et has 16 possible values, each a four-bit sequence giving 
the presence or absence of an obstacle in a particular compass direction. 
• Suppose that each sensor’s error rate is ε and that errors occur independently 
for the four sensor directions. In that case, the probability of getting all four 
bits right is (1 − ε)4 and the probability of getting them all wrong is ε4 . 
• Furthermore, if dit is the discrepancy—the number of bits that are different—
between the true values for square i and the actual reading et, then the 
probability that a robot in square i would receive a sensor reading et is
HMM example: Localization
61

=== p47 ===
• For example, the probability that a square with obstacles to the north and south 
would produce a sensor reading NSE is (1−ε)3ε1. 
• Given the matrices T and Ot, the robot can compute the posterior distribution 
over locations to work out where it is. 
• Figure 15.7 shows the distributions P(X1 |E1 =NSW) and P(X2 |E1 =NSW, E2
=NS). 
HMM example: Localization
62

=== p48 ===
• In addition to filtering to estimate its current location, the robot can use 
smoothing to work out where it was at any given past time and it can use the 
Viterbi algorithm to work out the most likely path it has taken to get where it is 
now. 
• Figure 15.8 shows the localization error and Viterbi path accuracy for various 
values of the per-bit sensor error rate ε. Even when ε is 20%—which means 
that the overall sensor reading is wrong 59% of the time—the robot is usually 
able to work out its location within two squares after 25 observations. 
HMM example: Localization
63

=== p49 ===
HMM example: Localization
64
[IMAGE-ONLY]

=== p50 ===
• This is because of the algorithm’s ability to integrate evidence over time and to 
take into account the probabilistic constraints imposed on the location 
sequence by the transition model. When ε is 10%, the performance after a half-
dozen observations is hard to distinguish from the performance with perfect 
sensing. 
• Broadly speaking, high levels of localization and path accuracy are maintained 
even in the face of substantial errors in the models used.
HMM example: Localization
65

=== p51 ===
• Imagine watching a small bird flying through dense jungle foliage at dusk: you 
glimpse brief, intermittent flashes of motion; you try hard to guess where the 
bird is and where it will appear next so that you don’t lose it. Or imagine that 
you are a World War II radar operator peering at a faint, wandering blip that 
appears once every 10 seconds on the screen. 
• In all these cases, you are doing filtering: estimating state variables (here, 
position and velocity) from noisy observations over time. If the variables were 
discrete, we could model the system with a hidden Markov model. This 
section examines methods for handling continuous variables, using an 
algorithm called Kalman filtering.
Kalman Filters
66

=== p52 ===
• The bird’s flight might be specified by six continuous variables at each time 
point; three for position (Xt, Yt, Zt) and three for velocity (Xt, Yt, Zt). We will 
need suitable conditional densities to represent the transition and sensor 
models: linear Gaussian distributions. The next state Xt+1 must be a linear 
function of the current state Xt, plus some Gaussian noise. 
• Consider the X-coordinate of the bird. Let the time interval between 
observations be Δ, and assume constant velocity during the interval; then the 
position update is given by Xt+Δ = Xt +XtΔ. Adding Gaussian noise, we obtain a 
linear Gaussian transition model:
Kalman Filters
67

=== p53 ===
• The Bayesian network structure for a system with position vector Xt and 
velocity Xt is shown in Figure 15.9. 
• A multivariate Gaussian distribution for d variables is specified by a d-element 
mean μ and a d × d covariance matrix Σ.
Kalman Filters
68

=== p54 ===
• A key property of the linear Gaussian family of distributions: it remains closed 
under the standard Bayesian network operations. 
Updating Gaussian distributions
69

=== p55 ===
• Thus, the FORWARD operator for Kalman filtering takes a Gaussian forward 
message f1:t, specified by a mean μt and covariance matrix Σt, and produces a 
new multivariate Gaussian forward message f1:t+1, specified by a mean μt+1 and 
covariance matrix Σt+1. 
• So, if we start with a Gaussian prior f1:0 = P(X0) = N(μ0, Σ0), filtering with a 
linear Gaussian model produces a Gaussian state distribution for all time. 
Updating Gaussian distributions
70

=== p56 ===
• The temporal model we consider describes a random walk of a single 
continuous state variable Xt with a noisy observation Zt. 
• An example might be the “consumer confidence” index, which can be 
modeled as undergoing a random Gaussian-distributed change each month and 
is measured by a random consumer survey that also introduces Gaussian 
sampling noise.
A simple one-dimensional example
71

=== p57 ===
A simple one-dimensional example
72
[IMAGE-ONLY]

=== p58 ===
A simple one-dimensional example
73
[IMAGE-ONLY]

=== p59 ===
A simple one-dimensional example
74
(15.19)
• To complete the update step, we need to condition on the observation at the 
first time step, namely, z1. From Equation (15.18), this is given by
• Once again, we combine the exponents and complete the square, obtaining
Thus, after one update cycle, we have a new Gaussian distribution for the state 
variable.

=== p60 ===
• From the Gaussian formula in Equation (15.19), we see that the new mean and 
standard deviation can be calculated from the old mean and standard deviation 
as follows:
• Figure 15.10 shows one update cycle for particular values of the transition and 
sensor models.
A simple one-dimensional example
75
(15.20)

=== p61 ===
A simple one-dimensional example
76
[IMAGE-ONLY]

=== p62 ===
• Equation (15.20) has some interesting additional properties. 
• First, we can interpret the calculation for the new mean μt+1 as simply a 
weighted mean of the new observation zt+1 and the old mean μt. If the 
observation is unreliable, then σz2 is large and we pay more attention to the old 
mean; if the old mean is unreliable (σt2 is large) or the process is highly 
unpredictable (σx2 is large), then we pay more attention to the observation. 
A simple one-dimensional example
77

=== p63 ===
• Second, notice that the update for the variance σt+12 is independent of the 
observation. We can therefore compute in advance what the sequence of 
variance values will be. 
• Third, the sequence of variance values converges quickly to a fixed value that 
depends only on σx2 and σz2, thereby substantially simplifying the subsequent 
calculations. 
A simple one-dimensional example
78

=== p64 ===
• The preceding derivation illustrates the key property of Gaussian distributions 
that allows Kalman filtering to work: the fact that the exponent is a quadratic 
form. This is true not just for the univariate case; the full multivariate Gaussian 
distribution has the form
• Multiplying out the terms in the exponent makes it clear that the exponent is 
also a quadratic function of the values xi in x. As in the univariate case, the 
filtering update preserves the Gaussian nature of the state distribution.
The general case
79

=== p65 ===
• Let us first define the general temporal model used with Kalman filtering. 
Both the transition model and the sensor model allow for a linear 
transformation with additive Gaussian noise. Thus, we have
• where F and Σx are matrices describing the linear transition model and 
transition noise covariance, and H and Σz are the corresponding matrices for 
the sensor model.  
The general case
80

=== p66 ===
The general case
81
• Now the update equations for the mean and covariance are
where
is called the Kalman gain matrix.  
• Consider the update for the mean state estimate μ. The term Fμt is the 
predicted state at t+1, so HFμt is the predicted observation. Therefore, the 
term zt+1 − HFμt represents the error in the predicted observation. This is 
multiplied by Kt+1 to correct the predicted state; hence, Kt+1 is a measure of 
how seriously to take the new observation relative to the prediction.

=== p67 ===
•
To illustrate these equations at work, we have applied them to the problem of 
tracking an object moving on the X–Y plane. The state variables are X = (X, Y, 
X, Y)T , so F, Σx, H, and Σz are 4×4 matrices. 
•
Figure 15.11(a) shows the true trajectory, a series of noisy observations, and 
the trajectory estimated by Kalman filtering, along with the covariances 
indicated by the one-standard-deviation contours. The filtering process does a 
good job of tracking the actual motion, and, as expected, the variance quickly 
reaches a fixed point.
The general case
82

=== p68 ===
The general case
83
[IMAGE-ONLY]

=== p69 ===
•
We can also derive equations for smoothing as well as filtering with linear 
Gaussian models. The smoothing results are shown in Figure 15.11(b). Notice 
how the variance in the position estimate is sharply reduced, except at the 
ends of the trajectory, and that the estimated trajectory is much smoother.
The general case
84

=== p70 ===
•
The “classical” application is in radar tracking of aircraft and missiles. 
Related applications include acoustic tracking of submarines and ground 
vehicles and visual tracking of vehicles and people. 
•
The range of application is much larger than just the tracking of motion: any 
system characterized by continuous state variables and noisy measurements 
will do. Such systems include pulp mills, chemical plants, nuclear reactors, 
plant ecosystems, and national economies.
Applicability of Kalman filtering
85