Bethe Bounds and Approximating the Global Optimum
Abstract
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.
Cite
Text
Weller and Jebara. "Bethe Bounds and Approximating the Global Optimum." International Conference on Artificial Intelligence and Statistics, 2013. doi:10.7916/D8SF34H5Markdown
[Weller and Jebara. "Bethe Bounds and Approximating the Global Optimum." International Conference on Artificial Intelligence and Statistics, 2013.](https://mlanthology.org/aistats/2013/weller2013aistats-bethe/) doi:10.7916/D8SF34H5BibTeX
@inproceedings{weller2013aistats-bethe,
title = {{Bethe Bounds and Approximating the Global Optimum}},
author = {Weller, Adrian and Jebara, Tony},
booktitle = {International Conference on Artificial Intelligence and Statistics},
year = {2013},
pages = {618-631},
doi = {10.7916/D8SF34H5},
url = {https://mlanthology.org/aistats/2013/weller2013aistats-bethe/}
}