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)
Carla Gomes (Cornell University)
Ashish Sabharwal (IBM Watson Research Center)
Bart Selman (Cornell University)
More from the Same Authors
-
2021 : Gaussian Mixture Variational Autoencoder with Contrastive Learning for Multi-Label Classification »
Junwen Bai · Shufeng Kong · Carla Gomes -
2021 : Gaussian Mixture Variational Autoencoder with Contrastive Learning for Multi-Label Classification »
Junwen Bai · Shufeng Kong · Carla Gomes -
2021 : Resolving Super Fine-Resolution SIF via Coarsely-Supervised U-Net Regression »
Joshua Fan · Di Chen · Jiaming Wen · Ying Sun · Carla Gomes -
2021 : A GNN-RNN Approach for Harnessing Geospatial and Temporal Information: Application to Crop Yield Prediction »
Joshua Fan · Junwen Bai · Zhiyun Li · Ariel Ortiz-Bobea · Carla Gomes -
2022 : Xtal2DoS: Attention-based Crystal to Sequence Learning for Density of States Prediction »
Junwen Bai · Yuanqi Du · Yingheng Wang · Shufeng Kong · John Gregoire · Carla Gomes -
2022 : Structure-based Drug Design with Equivariant Diffusion Models »
Arne Schneuing · Yuanqi Du · Charles Harris · Arian Jamasb · Ilia Igashov · weitao Du · Tom Blundell · Pietro Lió · Carla Gomes · Max Welling · Michael Bronstein · Bruno Correia -
2022 Workshop: AI for Science: Progress and Promises »
Yi Ding · Yuanqi Du · Tianfan Fu · Hanchen Wang · Anima Anandkumar · Yoshua Bengio · Anthony Gitter · Carla Gomes · Aviv Regev · Max Welling · Marinka Zitnik -
2022 Poster: Left Heavy Tails and the Effectiveness of the Policy and Value Networks in DNN-based best-first search for Sokoban Planning »
Dieqiao Feng · Carla Gomes · Bart Selman -
2021 : A GNN-RNN Approach for Harnessing Geospatial and Temporal Information: Application to Crop Yield Prediction »
Joshua Fan · Junwen Bai · Zhiyun Li · Ariel Ortiz-Bobea · Carla Gomes -
2021 : Resolving Super Fine-Resolution SIF via Coarsely-Supervised U-Net Regression »
Joshua Fan · Di Chen · Jiaming Wen · Ying Sun · Carla Gomes -
2021 : Cooperative Multi-Agent Fairness and Equivariant Policies »
Niko Grupen · Bart Selman · Daniel Lee -
2021 Poster: Towards Deeper Deep Reinforcement Learning with Spectral Normalization »
Nils Bjorck · Carla Gomes · Kilian Weinberger -
2021 Poster: Contrastively Disentangled Sequential Variational Autoencoder »
Junwen Bai · Weiran Wang · Carla Gomes -
2020 Poster: A Novel Automated Curriculum Strategy to Solve Hard Sokoban Planning Instances »
Dieqiao Feng · Carla Gomes · Bart Selman -
2019 : AI and Sustainable Development »
Fei Fang · Carla Gomes · Miguel Luengo-Oroz · Thomas Dietterich · Julien Cornebise -
2019 : Carla Gomes (Cornell) »
Carla Gomes -
2019 : Climate Change: A Grand Challenge for ML »
Yoshua Bengio · Carla Gomes · Andrew Ng · Jeff Dean · Lester Mackey -
2019 : Computational Sustainability: Computing for a Better World and a Sustainable Future »
Carla Gomes -
2018 Poster: Understanding Batch Normalization »
Johan 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