Reference: Dagum, P.; Shachter, R.; & Fagan, L. Modeling time in belief networks. Knowledge Systems Laboratory, November, 1991.
Abstract: This report addresses the problem of modeling time in dynamic domains given incomplete and uncertain information about the domain. Our first objective is to construct a dynamic model within a belief-network paradigm and to demonstrate how well-known time series concepts--such as backward smoothing, forward filtering and forecasting--are implemented in this model. The dynamic model is generated semiautomatically given a belief network that models the time-invariant relations of the domain. Thus we have a semiautomatic method for extending existing belief network models to dynamic belief-network models that can be used in applications where consideration of the time evolution of system variables is crucial to making valid inferences about the domain. The second objective is to design an efficient randomized approximation scheme (RAS) for probabilistic inference in belief networks to be employed by our dynamic model. Certain features unique to a RAS, compared to other stochastic simulation algorithms for probabilistic inference, make the RAS desirable as an inference algorithm for a dynamic model. For example, in dynamic domains, the time required to make a decision enters the utility of the decision when this time becomes comparable to the expected time in which the system changes sufficiently to outdate a decision. A RAS provides an a priori bound on the running time required to achieve a predefined level of accuracy in the output. This information can be used to reduce the loss of utility due to delayed decisions. Existing RASs for probabilistic inference in belief networks are known to have a poor worst-case behavior. The class of belief networks for which existing RASs run efficiently have been characterized in previous research. We optimize the RAS specifically for computing inferences in the dynamic models.