Stochastic Sampling and Search in Belief Updating Algorithms Very Large Bayesian Networks
Yan Lin, Marek J. Drużdżel · 1999
Bayesian networks are gaining an increasing popularity as a modeling tool for complex problems involving reasoning under uncertainty. Since belief updating in very large Bayesian networks cannot be e#ectively addressed by exact methods, approximate inference schemes may be often the only computationally feasible alternative. There are two basic classes of approximate schemes: stochastic sampling and search-based algorithms. We summarize the basic ideas underlying each of the classes, show how they are inter-related, discuss briefly their advantages and disadvantages, and show examples on which each of the classes fail. Finally, we study properties of a large real network from the point of view of search-based algorithms. Introduction Bayesian networks (Pearl 1988) are increasingly popular representations of problems involving reasoning under uncertainty. Practical models based on Bayesian networks often reach the size of hundreds of variables (e.g., (Pradhan et al. 1994; Conati et al....