Importance Sampling Algorithms for Bayesian Networks: Principles and Performance

Changhe Yuan, Marek J. Druzdzel

Abstract

Precision achieved by stochastic sampling algorithms for Bayesian networks typically deteriorates in face of extremely unlikely evidence. In addressing this problem, importance sampling algorithms seem to be most successful. We discuss the principles underlying the importance sampling algorithms in Bayesian networks. After that, we describe the Evidence Pre-propagation Importance Sampling (EPIS-BN), an importance sampling algorithm that computes an importance function using two techniques: loopy belief propagation and epsilon-cutoff heuristic. We test the performance of EPIS-BN on three large real Bayesian networks and observe that on all three networks it outperforms AIS-BN, the current state of the art algorithm, while avoiding its costly learning stage. We also compare importance sampling to Gibbs sampling and discuss the role of the epsilon-cutoff heuristic in importance sampling for Bayesian networks.

PDF

Bibtex

@ARTICLE{Yuan06importance,
author = {C. Yuan and M. J. Druzdzel},
title = {Importance Sampling Algorithms for {B}ayesian Networks: Principles and Performance},
journal = {Mathematical and Computer Modelling},
year = {2006},
volume = {43},
pages = {1189--1207}
}