NIPS Proceedingsβ

Accelerated Adaptive Markov Chain for Partition Function Computation

Part of: Advances in Neural Information Processing Systems 24 (NIPS 2011)

[PDF] [BibTeX] [Spotlights]

Authors

Abstract

We propose a novel Adaptive Markov Chain Monte Carlo algorithm to compute the partition function. In particular, we show how to accelerate a flat histogram sampling technique by significantly reducing the number of ``null moves'' in the chain, while maintaining asymptotic convergence properties. Our experiments show that our method converges quickly to highly accurate solutions on a range of benchmark instances, outperforming other state-of-the-art methods such as IJGP, TRW, and Gibbs sampling both in run-time and accuracy. We also show how obtaining a so-called density of states distribution allows for efficient weight learning in Markov Logic theories.