An Importance Sampling Algorithm Based on Evidence Pre-propagation

Changhe Yuan, Marek J. Druzdzel

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.

PDF

Bibtex

@INPROCEEDINGS{Yuan03,
AUTHOR = "Yuan Changhe and Druzdzel Marek",
TITLE = "An Importance Sampling Algorithm Based on Evidence Pre-propagation",
BOOKTITLE = "Proceedings of the 19th Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)",
PUBLISHER = "Morgan Kaufmann Publishers",
ADDRESS = "San Francisco, CA",
YEAR = "2003",
PAGES = "624--631"
}