How heavy should the tails be?

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-based inference algorithms (e.g., Cheng & Druzdzel 2000; Moral & Salmeron 2003; Yuan & Druzdzel 2004b; 2004c) have shown excellent performance on reasoning tasks in Bayesian networks. In this paper, we argue that all the improvements of these algorithms come from the same source, the improvement on the quality of the importance function. We also explain the requirements that a good importance function should satisfy, namely, it should concentrate its mass on the important parts of the target density and it should possess heavy tails. While the first requirement is subject of a theorem due to Rubinstein (1981), the second requirement is much less understood. We attempt to illustrate why heavy tails are desirable by studying the properties of importance sampling and examining a specific example. The study also leads to a theoretical insight into the desirability of heavy tails for importance sampling in the context of Bayesian networks, which provides a common theoretical basis for several successful heuristic methods.