A Comparison of the Effectiveness of Two Heuristics for Importance Sampling

Changhe Yuan, Marek J. Druzdzel

Abstract

Given a good importance function, importance sampling is able to achieve satisfactory precisions within a reasonable time. In addition to the well known requirement that the importance function should have a similar shape to the target density, it is also highly recommended that the importance function possess heavy tails. To achieve this, the epsilon-cutoff heuristic was used to cut off extremely small probabilities in the importance function. However, epsilon-cutoff demonstrates inconsistent performance on different networks. In this paper, we analyze the underlying reasons and propose another heuristic, if-tempering, based on simulated tempering. We test the new heuristic on three large real Bayesian networks and observe that if-tempering consistently helps the EPIS-BN algorithm achieve better precisions than epsilon-cutoff.

PDF

Bibtex

@inproceedings{Yuan04c,
AUTHOR = "C. Yuan and M. J. Druzdzel",
TITLE = "A Comparison of the Effectiveness of Two Heuristics for Importance Sampling",
YEAR = "2004",
BOOKTITLE = "Proceedings of the Second European Workshop on Probabilistic Graphical Models (PGM'04)",
ADDRESS = "Leiden , The Netherlands ",
PAGES = "225-232"
}