An Importance Sampling Algorithm Based on Evidence Pre-propagation
Changhe Yuan, Marek Druzdzel
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.
Keywords: Importance Sampling Algorithm Based Evidence Pre-propagation
PS Link: null
PDF Link: /papers/03/p624-yuan.pdf
AUTHOR = "Changhe Yuan
and Marek Druzdzel",
TITLE = "An Importance Sampling Algorithm Based on Evidence Pre-propagation",
BOOKTITLE = "Proceedings of the Nineteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "2003",
PAGES = "624--631"