A comparison on the effectiveness of two heuristics for importance sampling

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: Importance sampling has become the basis for many Monte Carlo sampling-based inference algorithms for Bayesian networks. These algorithms essentially differ in the methods by which they obtain an importance function. 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 (Rubinstein 1981), it is also highly recommended that the importance function possess heavy tails (Geweke 1989, Mackay 1998, Yuan & Druzdzel 2004}. To achieve this, the epsilon heuristic (Cheng & Druzdzel 2000, Yuan & Druzdzel 2003) was used to cut off extremely small probabilities in the importance function (Yuan & Druzdzel 2003). However, epsilon heuristic 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 (Yuan & Druzdzel 2003) achieve better precision than epsilon heuristic.