Poster
Density Propagation and Improved Bounds on the Partition Function
Stefano Ermon · Carla Gomes · Ashish Sabharwal · Bart Selman

Tue Dec 4th 07:00 PM -- 12:00 AM @ Harrah’s Special Events Center 2nd Floor #None
in Poster Session »

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