CUED Publications database

Bethe Bounds and Approximating the Global Optimum

Weller, A and Jebara, T Bethe Bounds and Approximating the Global Optimum. (Unpublished)

Full text not available from this repository.


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.

Item Type: Article
Uncontrolled Keywords: cs.LG cs.LG stat.ML
Divisions: Div F > Computational and Biological Learning
Depositing User: Cron Job
Date Deposited: 15 Nov 2017 20:14
Last Modified: 18 Feb 2021 18:14