Importance sampling algorithms for Bayesian networks: Principles and performance

Authors:

Changhe Yuan and Marek J. Druzdzel
Decision Systems Laboratory
School of Information Sciences
and Intelligent Systems Program
University of Pittsburgh
135 North Bellefield Avenue
Pittsburgh, PA 15260, U.S.A.
e-mail: cyuan@sis.pitt.edu, marek@sis.pitt.edu

Abstract:

Precision achieved by stochastic sampling algorithms for Bayesian networks typically deteriorates in face of extremely unlikely evidence. In addressing this problem, importance sampling algorithms seems to be most successful. We discuss the principles behind the importance sampling algorithms. We describe the Evidence Pre-propagation Importance Sampling (EPIS-BN), an importance sampling algorithm that computes an approximate importance function using two techniques: loopy belief propagation [1, 2] and epsilon-cutoff heuristic [3]. We test the performance of EPIS-BN on three large real Bayesian networks and observe that on three very large real Bayesian networks the EPIS-BN it outperforms AIS-BN [3], the current state of the art algorithm, while avoiding its costly learning stage. We also compare importance sampling to Gibbs sampling and discuss the role of the epsilon-cutoff heuristic in importance sampling for Bayesian networks.