Stochastic sampling and search in belief updating algorithms for very large Bayesian networks

Authors:

Yan Lin and Marek J. Druzdzel
Decision Systems Laboratory
School of Information Sciences
and Intelligent Systems Program
University of Pittsburgh
e-mail: yan@isp.pitt.edu, marek@sis.pitt.edu

Abstract:

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 effectively 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.