Beyond Log-Supermodularity: Lower Bounds and the Bethe Partition Function

2013/09/26 by Nicholas Ruozzi, Ruozzi, Nicholas · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1309.6859

Appears in Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence (UAI2013)

arxiv created 2013/09/26 · arxiv updated 2013/09/27

Abstract

A recent result has demonstrated that the Bethe partition function always lower bounds the true partition function of binary, log-supermodular graphical models. We demonstrate that these results can be extended to other interesting classes of graphical models that are not necessarily binary or log-supermodular: the ferromagnetic Potts model with a uniform external field and its generalizations and special classes of weighted graph homomorphism problems.

Cited by

• Graph-Cover-based Characterization of the Bethe Partition Function of Double-Edge Factor Graphs

Related

• The Bethe Partition Function of Log-supermodular Graphical Models
• Understanding the ratio of the partition sum to its Bethe approximation via double covers
• The replica symmetric solution for Potts models on d-regular graphs
• Graph-Cover-based Characterization of the Bethe Partition Function of Double-Edge Factor Graphs
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results