Timezone: »
Spotlight
Accelerated Adaptive Markov Chain for Partition Function Computation
Stefano Ermon · Carla Gomes · Ashish Sabharwal · Bart Selman
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.
Author Information
Stefano Ermon (Stanford University)
Carla Gomes (Cornell University)
Ashish Sabharwal (IBM Watson Research Center)
Bart Selman (Cornell University)
Related Events (a corresponding poster, oral, or spotlight)
-
2011 Poster: Accelerated Adaptive Markov Chain for Partition Function Computation »
Tue Dec 13th 04:45 -- 10:59 PM Room None
More from the Same Authors
-
2020 Poster: A Novel Automated Curriculum Strategy to Solve Hard Sokoban Planning Instances »
Dieqiao Feng · Carla Gomes · Bart Selman -
2018 Poster: Understanding Batch Normalization »
Nils Bjorck · Carla Gomes · Bart Selman · Kilian Weinberger -
2016 Poster: Solving Marginal MAP Problems with NP Oracles and Parity Constraints »
Yexiang Xue · zhiyuan li · Stefano Ermon · Carla Gomes · Bart Selman -
2013 Workshop: Machine Learning for Sustainability »
Edwin Bonilla · Thomas Dietterich · Theodoros Damoulas · Andreas Krause · Daniel Sheldon · Iadine Chades · J. Zico Kolter · Bistra Dilkina · Carla Gomes · Hugo P Simao -
2013 Poster: Embed and Project: Discrete Sampling with Universal Hashing »
Stefano Ermon · Carla Gomes · Ashish Sabharwal · Bart Selman -
2012 Poster: Density Propagation and Improved Bounds on the Partition Function »
Stefano Ermon · Carla Gomes · Ashish Sabharwal · Bart Selman -
2008 Poster: Counting Solution Clusters Using Belief Propagation »
Lukas Kroc · Ashish Sabharwal · Bart Selman -
2006 Poster: Near-Uniform Sampling of Combinatorial Spaces Using XOR Constraints »
Carla Gomes · Ashish Sabharwal · Bart Selman