Fixing Max-Product: Convergent Message Passing Algorithms for MAP LP-Relaxations
Abstract
We present a novel message passing algorithm for approximating the MAP problem in graphical models. The algorithm is similar in structure to max-product but unlike max-product it always converges, and can be proven to find the exact MAP solution in various settings. The algorithm is derived via block coordinate descent in a dual of the LP relaxation of MAP, but does not require any tunable parameters such as step size or tree weights. We also describe a generalization of the method to cluster based potentials. The new method is tested on synthetic and real-world problems, and compares favorably with previous approaches.
Cite
Text
Globerson and Jaakkola. "Fixing Max-Product: Convergent Message Passing Algorithms for MAP LP-Relaxations." Neural Information Processing Systems, 2007.Markdown
[Globerson and Jaakkola. "Fixing Max-Product: Convergent Message Passing Algorithms for MAP LP-Relaxations." Neural Information Processing Systems, 2007.](https://mlanthology.org/neurips/2007/globerson2007neurips-fixing/)BibTeX
@inproceedings{globerson2007neurips-fixing,
title = {{Fixing Max-Product: Convergent Message Passing Algorithms for MAP LP-Relaxations}},
author = {Globerson, Amir and Jaakkola, Tommi S.},
booktitle = {Neural Information Processing Systems},
year = {2007},
pages = {553-560},
url = {https://mlanthology.org/neurips/2007/globerson2007neurips-fixing/}
}