nips nips2002 nips2002-174 nips2002-174-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Finnegan Southey, Dale Schuurmans, Ali Ghodsi
Abstract: Greedy importance sampling is an unbiased estimation technique that reduces the variance of standard importance sampling by explicitly searching for modes in the estimation objective. Previous work has demonstrated the feasibility of implementing this method and proved that the technique is unbiased in both discrete and continuous domains. In this paper we present a reformulation of greedy importance sampling that eliminates the free parameters from the original estimator, and introduces a new regularization strategy that further reduces variance without compromising unbiasedness. The resulting estimator is shown to be effective for difficult estimation problems arising in Markov random field inference. In particular, improvements are achieved over standard MCMC estimators when the distribution has multiple peaked modes.
[1] D. Ackley, G. Hinton, and T. Sejnowski. A learning algorithm for Boltzmann machines. Cognitive Science, 9:147–169, 1985.
[2] P. Dagum and M. Luby. Approximating probabilistic inference in Bayesian belief networks is NP-hard. Artificial Intelligence, 60:141–153, 1993.
[3] P. Dagum and M. Luby. An optimal approximation algorithm for Bayesian inference. Artificial Intelligence, 93:1–27, 1997.
[4] J. Geweke. Baysian inference in econometric models using Monte Carlo integration. Econometrica, 57:1317–1339, 1989.
[5] W. Gilks, S. Richardson, and D. Spiegelhalter. Markov Chain Monte Carlo in Practice. Chapman and Hall, 1996.
[6] M. Jordan, Z. Ghahramani, T. Jaakkola, and L. Saul. An introduction to variational methods for graphical models. In Learning in Graphical Models. Kluwer, 1998.
[7] D. MacKay. Intro to Monte Carlo methods. In Learning in Graphical Models. Kluwer, 1998.
[8] R. Neal. Probabilistic inference using Markov chain Monte Carlo methods. Tech report, 1993.
[9] J. Propp and D. Wilson. Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures and Algorithms, 9:223–253, 1996.
[10] R. Rubinstein. Simulation and the Monte Carlo Method. Wiley, New York, 1981.
[11] D. Schuurmans. Greedy importance sampling. In Proceedings NIPS-12, 1999.
[12] D. Schuurmans and F. Southey. Monte Carlo inference via greedy importance sampling. In Proceedings UAI, 2000.
[13] R. Swendsen, J. Wang, and A. Ferrenberg. New Monte Carlo methods for improved efficiency of computer simulations in statistical mechanics. In The Monte Carlo Method in Condensed Matter Physics. Springer, 1992.
[14] M. Tanner. Tools for Statistical Inference: Methods for Exploration of Posterior Distributions and Likelihood Functions. Springer, New York, 1993.
[15] D. Wilson. Sampling configurations of an Ising system. In Proceedings SODA, 1999.