Convergent Decomposition Solvers for Tree-reweighted Free Energies

Jeremy Jancsary, Gerald Matz
Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, PMLR 15:388-398, 2011.

Abstract

We investigate minimization of tree-reweighted free energies for the purpose of obtaining approximate marginal probabilities and upper bounds on the partition function of cyclic graphical models. The solvers we present for this problem work by directly tightening tree-reweighted upper bounds. As a result, they are particularly efficient for tree-reweighted energies arising from a small number of spanning trees. While this assumption may seem restrictive at first, we show how small sets of trees can be constructed in a principled manner. An appealing property of our algorithms, which results from the problem decomposition, is that they are embarassingly parallel. In contrast to the original message passing algorithm introduced for this problem, we obtain global convergence guarantees.

Cite this Paper

BibTeX
@InProceedings{pmlr-v15-jancsary11a, title = {Convergent Decomposition Solvers for Tree-reweighted Free Energies}, author = {Jancsary, Jeremy and Matz, Gerald}, booktitle = {Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics}, pages = {388--398}, year = {2011}, editor = {Gordon, Geoffrey and Dunson, David and Dudík, Miroslav}, volume = {15}, series = {Proceedings of Machine Learning Research}, address = {Fort Lauderdale, FL, USA}, month = {11--13 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v15/jancsary11a/jancsary11a.pdf}, url = {https://proceedings.mlr.press/v15/jancsary11a.html}, abstract = {We investigate minimization of tree-reweighted free energies for the purpose of obtaining approximate marginal probabilities and upper bounds on the partition function of cyclic graphical models. The solvers we present for this problem work by directly tightening tree-reweighted upper bounds. As a result, they are particularly efficient for tree-reweighted energies arising from a small number of spanning trees. While this assumption may seem restrictive at first, we show how small sets of trees can be constructed in a principled manner. An appealing property of our algorithms, which results from the problem decomposition, is that they are embarassingly parallel. In contrast to the original message passing algorithm introduced for this problem, we obtain global convergence guarantees.} }
Endnote
%0 Conference Paper %T Convergent Decomposition Solvers for Tree-reweighted Free Energies %A Jeremy Jancsary %A Gerald Matz %B Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2011 %E Geoffrey Gordon %E David Dunson %E Miroslav Dudík %F pmlr-v15-jancsary11a %I PMLR %P 388--398 %U https://proceedings.mlr.press/v15/jancsary11a.html %V 15 %X We investigate minimization of tree-reweighted free energies for the purpose of obtaining approximate marginal probabilities and upper bounds on the partition function of cyclic graphical models. The solvers we present for this problem work by directly tightening tree-reweighted upper bounds. As a result, they are particularly efficient for tree-reweighted energies arising from a small number of spanning trees. While this assumption may seem restrictive at first, we show how small sets of trees can be constructed in a principled manner. An appealing property of our algorithms, which results from the problem decomposition, is that they are embarassingly parallel. In contrast to the original message passing algorithm introduced for this problem, we obtain global convergence guarantees.
RIS
TY - CPAPER TI - Convergent Decomposition Solvers for Tree-reweighted Free Energies AU - Jeremy Jancsary AU - Gerald Matz BT - Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics DA - 2011/06/14 ED - Geoffrey Gordon ED - David Dunson ED - Miroslav Dudík ID - pmlr-v15-jancsary11a PB - PMLR DP - Proceedings of Machine Learning Research VL - 15 SP - 388 EP - 398 L1 - http://proceedings.mlr.press/v15/jancsary11a/jancsary11a.pdf UR - https://proceedings.mlr.press/v15/jancsary11a.html AB - We investigate minimization of tree-reweighted free energies for the purpose of obtaining approximate marginal probabilities and upper bounds on the partition function of cyclic graphical models. The solvers we present for this problem work by directly tightening tree-reweighted upper bounds. As a result, they are particularly efficient for tree-reweighted energies arising from a small number of spanning trees. While this assumption may seem restrictive at first, we show how small sets of trees can be constructed in a principled manner. An appealing property of our algorithms, which results from the problem decomposition, is that they are embarassingly parallel. In contrast to the original message passing algorithm introduced for this problem, we obtain global convergence guarantees. ER -
APA
Jancsary, J. & Matz, G.. (2011). Convergent Decomposition Solvers for Tree-reweighted Free Energies. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 15:388-398 Available from https://proceedings.mlr.press/v15/jancsary11a.html.

Related Material