Algorithms for Bayesian belief-network precomputation

Abstract

Bayesian belief networks provide an intuitive and concise means of representing probabilistic relationships among the variables in expert systems. A major drawback to this methodology is its computational complexity. We present an introduction to belief networks, and describe methods for precomputing, or caching, part of a belief network based on metrics of probability and expected utility. These algorithms are examples of a general method for decreasing expected running time for probabilistic inference. We first present the necessary background, and then present algorithms for producing caches based on metrics of expected probability and expected utility. We show how these algorithms can be applied to a moderately complex belief network, and present directions for future research.