8.5.3 Algorithms for Monitoring and Smoothing

Any standard belief-network algorithms, such as variable elimination, can be used to carry out monitoring or smoothing. However, it is possible to take advantage of the fact that time moves forward and that the agent is getting observations in time and is interested in its 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 8.12, for each $i$, the agent wants to compute $P(S_{i}\mid o_{0},\dots,o_{i})$, which is the distribution over the state at time $i$ given the particular observation of $o_{0},\dots,o_{i}$. This is done using variable elimination:

 $\displaystyle P(S_{i}\mid o_{0},\dots,o_{i})\propto$ $\displaystyle P(S_{i},o_{0},\dots,o_{i})$ $\displaystyle=$ $\displaystyle P(o_{i}\mid S_{i})P(S_{i},o_{0},\dots,o_{i-1})$ $\displaystyle=$ $\displaystyle P(o_{i}\mid S_{i})\sum_{S_{i-1}}P(S_{i},S_{i-1},o_{0},\dots,o_{i% -1})$ $\displaystyle=$ $\displaystyle P(o_{i}\mid S_{i})\sum_{S_{i-1}}P(S_{i}\mid S_{i-1})P(S_{i-1},o_% {0},\dots,o_{i-1})$ $\displaystyle\propto$ $\displaystyle P(o_{i}\mid S_{i})\sum_{S_{i-1}}P(S_{i}\mid S_{i-1})P(S_{i-1}% \mid o_{0},\dots,o_{i-1}).$ (8.2)

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(S_{i-1}\mid o_{0},\dots,o_{i-1})$. This is just a factor on $S_{i-1}$. To compute the next belief, it multiplies this by $P(S_{i}\mid S_{i-1})$, sums out $S_{i-1}$, multiplies this by the factor $P(o_{i}\mid S_{i})$, and normalizes.

Multiplying a factor on $S_{i-1}$ by the factor $P(S_{i}\mid S_{i-1})$ and summing out $S_{i-1}$ is an instance of matrix multiplication. Multiplying the result by $P(o_{i}\mid S_{i})$ is called the dot product. Matrix multiplication and dot product are simple instances of variable elimination.

Example 8.33.

Consider the domain of Example 8.31. An observation of a door involves multiplying the probability of each location $L$ by $P(door\mid 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.

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 variable elimination; see Exercise 17.