Symbolic Probabilistic Inference in Belief Networks

Abstract

The Symbolic Probabilistic Inference (SPI) Algorithm [D'Ambrosio, 1989] provides an efficient framework for resolving general queries on a belief network. It applies the concept of dependency-directed backward search to probabilistic inference, and is incremental with respect to both queries and observations. Unlike most belief network algorithms, SPI is goal directed, performing only those calculations that are required to respond to queries. The directed graph of the underlying belief network is used to develop a tree structure for recursive query processing. This allows effective caching of intermediate results and significant opportunities for parallel computation. A simple preprocessing step ensures that, given the search tree, the algorithm will include no unnecessary distributions. The preprocessing step eliminates dimensions from the intermediate results and prunes the search path.