  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.
