nips nips2011 nips2011-17 nips2011-17-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Stefano Ermon, Carla P. Gomes, Ashish Sabharwal, Bart Selman
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. 1
[1] Martin J Wainwright and Michael I Jordan. Graphical Models, Exponential Families, and Variational Inference. Now Publishers Inc., Hanover, MA, USA, 2008.
[2] N.N. Schraudolph and D. Kamenetsky. Efficient exact inference in planar Ising models. In Proc. of NIPS-08, 2008.
[3] F. Wang and DP Landau. Efficient, multiple-range random walk algorithm to calculate the density of states. Physical Review Letters, 86(10):2050–2053, 2001.
[4] M.J. Wainwright, T.S. Jaakkola, and A.S. Willsky. A new class of upper bounds on the log partition function. Information Theory, IEEE Transactions on, 51(7):2313–2335, 2005.
[5] Vibhav Gogate and Rina Dechter. SampleSearch: A Scheme that Searches for Consistent Samples. Journal of Machine Learning Research, 2:147–154, 2007.
[6] Mark Jerrum and Alistair Sinclair. The Markov chain Monte Carlo method: an approach to approximate counting and integration, pages 482–520. PWS Publishing Co., Boston, MA, USA, 1997.
[7] P. Domingos, S. Kok, H. Poon, M. Richardson, and P. Singla. Unifying logical and statistical ai. In Proc. of AAAI-06, pages 2–7, Boston, Massachusetts, 2006. AAAI Press.
[8] M. Richardson and P. Domingos. Markov logic networks. Machine Learning, 62(1):107–136, 2006.
[9] H. Poon and P. Domingos. Sound and efficient inference with probabilistic and deterministic dependencies. In Proc. of AAAI-06, pages 458–463, 2006.
[10] J.S. Yedidia, W.T. Freeman, and Y. Weiss. Constructing free-energy approximations and generalized belief propagation algorithms. Information Theory, IEEE Transactions on, 51(7):2282–2312, 2005.
[11] S. Ermon, C. Gomes, and B. Selman. Computing the density of states of Boolean formulas. In Proc. of CP-2010, 2010.
[12] B. Selman, H.A. Kautz, and B. Cohen. Local search strategies for satisfiability testing. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1996.
[13] C.P. Gomes, J. Hoffmann, A. Sabharwal, and B. Selman. From sampling to model counting. In Proc. of IJCAI-07, 2007.
[14] V. Gogate and R. Dechter. Approximate counting by sampling the backtrack-free search space. In Proc. of AAAI-07, pages 198–203, 2007. 9