An Importance Sampling Algorithm Based on Evidence Pre-propagation

Abstract

Precision achieved by stochastic sampling algorithms for Bayesian networks typically deteriorates in face of extremely unlikely evidence. To address this problem, we propose the Evidence Pre-propagation Importance Sampling algorithm (EPIS-BN), an importance sampling algorithm that computes an approximate importance function by the heuristic methods: loopy belief Propagation and e-cutoff. We tested the performance of e-cutoff on three large real Bayesian networks: ANDES, CPCS, and PATHFINDER. We observed that on each of these networks the EPIS-BN algorithm gives us a considerable improvement over the current state of the art algorithm, the AIS-BN algorithm. In addition, it avoids the costly learning stage of the AIS-BN algorithm.

Appears in Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence (UAI2003)

References in corpus (1)

• Loopy Belief Propagation for Approximate Inference: An Empirical Study

Cited by in corpus (3)

• Measuring the Hardness of Stochastic Sampling on Bayesian Networks with Deterministic Causalities: the k-Test
• Cutset Sampling with Likelihood Weighting
• Importance Sampling via Variational Optimization