2012/01/01 by Adrian Weller, Weller, Adrian, Tony Jebara +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Error Correcting Code Techniques #FOS: Computer and information sciences #Genomics and Chromatin Dynamics #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · pdf · doi:10.48550/arxiv.1301.0015
openalex publication_date 2012/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Inference in general Markov random fields (MRFs) is NP-hard, though identifying the maximum a posteriori (MAP) configuration of pairwise MRFs with submodular cost functions is efficiently solvable using graph cuts. Marginal inference, however, even for this restricted class, is in #P. We prove new formulations of derivatives of the Bethe free energy, provide bounds on the derivatives and bracket the locations of stationary points, introducing a new technique called Bethe bound propagation. Several results apply to pairwise models whether associative or not. Applying these to discretized pseudo-marginals in the associative case we present a polynomial time approximation scheme for global optimization provided the maximum degree is O(log n), and discuss several extensions.