Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).

6.5.3 Algorithms for Monitoring and Smoothing

You can use any standard belief-network algorithms, such as VE or particle filtering, to carry out monitoring or smoothing. However, you can take advantage of the fact that time moves forward and that you are getting observations in time and are interested in the state at the current time.

In belief monitoring or filtering, an agent computes the probability of the current state given the history of observations. In terms of the HMM of Figure 6.14, for each i, the agent wants to compute P(Si|o0,...,oi), which is the distribution over the state at time i given the particular observation of o0,...,oi. This can easily be done using VE:

P(Si|o0,...,oi) ∝ P(Si,o0,...,oi)
=P(oi|Si) P(Si,o0,...,oi-1)
=P(oi|Si) ∑Si-1P(Si,Si-1,o0,...,oi-1)
=P(oi|Si) ∑Si-1P(Si|Si-1) P(Si-1,o0,...,oi-1)
∝P(oi|Si) ∑Si-1P(Si|Si-1) P(Si-1|o0,...,oi-1).

Suppose the agent has computed the previous belief based on the observations received up until time i-1. That is, it has a factor representing P(Si-1|o0,...,oi-1). Note that this is just a factor on Si-1. To compute the next belief, it multiplies this by P(Si|Si-1), sums out Si-1, multiplies this by the factor P(oi|Si) , and normalizes.

Multiplying a factor on Si-1 by the factor P(Si|Si-1) and summing out Si-1 is matrix multiplication. Multiplying the result by P(oi|Si) is called the dot product. Matrix multiplication and dot product are simple instances of VE.

Example 6.30: Consider the domain of Example 6.28. An observation of a door involves multiplying the probability of each location L by P(door|Loc=L) and renormalizing. A move right involves, for each state, doing a forward simulation of the move-right action in that state weighted by the probability of being in that state.

For many problems the state space is too big for exact inference. For these domains, particle filtering is often very effective. With temporal models, resampling typically occurs at every time step. Once the evidence has been observed, and the posterior probabilities of the samples have been computed, they can be resampled.

Smoothing is the problem of computing the probability distribution of a state variable in an HMM given past and future observations. The use of future observations can make for more accurate predictions. Given a new observation it is possible to update all previous state estimates with one sweep through the states using VE; see Exercise 6.11.