Adaptive Importance Sampling for Estimation in Structured Domains
This work addresses the need for more efficient estimation in probabilistic models like belief networks, though it appears incremental as it builds on existing stochastic gradient descent techniques.
The paper tackles the problem of improving variance in importance sampling for high-dimensional structured domains by introducing adaptive methods that update the sampling distribution based on sample information, and it demonstrates these methods empirically on action evaluation in influence diagrams with concrete performance comparisons.
Sampling is an important tool for estimating large, complex sums and integrals over high dimensional spaces. For instance, important sampling has been used as an alternative to exact methods for inference in belief networks. Ideally, we want to have a sampling distribution that provides optimal-variance estimators. In this paper, we present methods that improve the sampling distribution by systematically adapting it as we obtain information from the samples. We present a stochastic-gradient-descent method for sequentially updating the sampling distribution based on the direct minization of the variance. We also present other stochastic-gradient-descent methods based on the minimizationof typical notions of distance between the current sampling distribution and approximations of the target, optimal distribution. We finally validate and compare the different methods empirically by applying them to the problem of action evaluation in influence diagrams.