Greedy importance sampling: A new Monte Carlo inference method
This paper presents a new Monte Carlo inference method that is a simple variation of importance sampling. It is well known that importance sampling fails when the proposal distribution concentrates samples in low density regions of the target distribution, which leads to high variance in the estimates. The method we propose attempts to mitigate this difficulty by explicitly searching for high density regions in the target distribution given starting points drawn from the proposal distribution. We prove that a version of this technique yields unbiased (“fair”) samples of the target distribution, and demonstrate that the proposed approach can reduce the variance of the resulting estimates by concentrating samples in more important regions of the space. The paper then presents an application of the greedy method to inferring hidden state in dynamic probabilistic models. Here we demonstrate improvements over standard likelihood weighting approaches, while maintaining some useful advantages over the recently developed “survival of the fittest” (condensation) methods.