How Heavy Should the Tails Be

Importance sampling-based inference algorithms have shown excellent performance on reasoning tasks in Bayesian networks (Cheng & Druzdzel 2000; Moral & Salmeron 2003; Yuan & Druzdzel 2005). 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. Introduction Importance sampling is used in several areas of modern statistics and econometrics to approximate unsolvable integrals. It has become the basis for several successful Monte Carlo sampling-based inference algorithms for Bayesian networks (Cheng & Druzdzel 2000; Moral & Salmeron 2003; Yuan & Druzdzel 2005), for which inference is known to be NP-hard (Cooper 1990; Dagum & Luby 1993). This paper argues that all the improvements of these algorithms come from the same source, the improvement on the quality of the importance function. A good importance function can lead importance sampling to yield excellent results in a reasonable time. It is well understood that we should focus on sampling in the areas where the value of the target function is relatively large (Rubinstein 1981). Thus, the importance function should concentrate its mass on the important parts of the target density. However, unimportant areas should by no means be neglected. Several authors pointed out that a good importance function should possess heavy tails (Geweke 1989; MacKay 1998). In other Copyright c © 2005, American Association for Artificial Intelligence (www.aaai.org). All rights reserved. words, we should increase the sampling density in those unimportant areas. These two requirements seem to contradict one another. Why heavy tails are important and how heavy they should be are not well understood. This paper addresses these questions by studying the properties of importance sampling and discussing what conditions an admissible importance function should satisfy. We also try to illustrate why heavy tails are important by examining an example in which the conditions can be verified analytically. When analytical verification is impossible, we recommend to use two techniques to estimate how good an importance function is. 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 in Bayesian networks, including -cutoff (Cheng & Druzdzel 2000; Ortiz & Kaelbling 2000; Yuan & Druzdzel 2005), if-tempering (Yuan & Druzdzel 2004), rejection control (Liu 2001), and dynamic tuning (Shachter & Peot 1989; Ortiz & Kaelbling 2000; Moral & Salmeron 2003). Importance Sampling In our notation, a regular upper case letter, such as X , denotes a single variable, and x denotes its state. A bold upper case letter, such as X, denotes a set of variables. Their states are denoted by x. Now, let p(X) be a probability density of n variables X = (X1, ..., Xn) over domain Ω ⊂ R. Consider the problem of estimating the multiple integral