An importance sampling algorithm based on evidence pre-propagation

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. 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 using two techniques: loopy belief propagation [19, 25] and epsilon-cutoff heuristic [2]. We tested the performance of EPIS-BN on three large real Bayesian networks: ANDES [3], CPCS [21], and PathFinder [11]. We observed that on each of these networks the EPIS-BN algorithm outperforms AIS-BN [2], the current state of the art algorithm, while avoiding its costly learning stage.