AND/OR Importance Sampling
This addresses variance reduction in sampling methods for probabilistic graphical models, but appears incremental as it builds directly on importance sampling.
The paper tackles the problem of variance in importance sampling for probabilistic graphical models by introducing AND/OR importance sampling, which caches samples in AND/OR space and extracts a new sample mean, resulting in lower variance and far greater accuracy in many cases.
The paper introduces AND/OR importance sampling for probabilistic graphical models. In contrast to importance sampling, AND/OR importance sampling caches samples in the AND/OR space and then extracts a new sample mean from the stored samples. We prove that AND/OR importance sampling may have lower variance than importance sampling; thereby providing a theoretical justification for preferring it over importance sampling. Our empirical evaluation demonstrates that AND/OR importance sampling is far more accurate than importance sampling in many cases.