Timezone: »
Given a probabilistic graphical model, its density of states is a function that, for any likelihood value, gives the number of configurations with that probability. We introduce a novel message-passing algorithm called Density Propagation (DP) for estimating this function. We show that DP is exact for tree-structured graphical models and is, in general, a strict generalization of both sum-product and max-product algorithms. Further, we use density of states and tree decomposition to introduce a new family of upper and lower bounds on the partition function. For any tree decompostion, the new upper bound based on finer-grained density of state information is provably at least as tight as previously known bounds based on convexity of the log-partition function, and strictly stronger if a general condition holds. We conclude with empirical evidence of improvement over convex relaxations and mean-field based bounds.
Author Information
Stefano Ermon (Stanford University)
Carla Gomes (Cornell University)
Ashish Sabharwal (IBM Watson Research Center)
Bart Selman (Cornell University)
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 -
2011 Poster: Accelerated Adaptive Markov Chain for Partition Function Computation »
Stefano Ermon · Carla Gomes · Ashish Sabharwal · Bart Selman -
2011 Spotlight: Accelerated Adaptive Markov Chain for Partition Function Computation »
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