Convergent decomposition solvers for tree-reweighted free energies

Jeremy Jancsary and Gerald Matz
14th International Conference on Artificial Intelligence and Statistics (AISTATS)
April 2011, Ft. Lauderdale, FL, USA

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.  

Article & supp. material

 

 

 

 


Note: The reference implementation in Scala is available on sourceforge.net.

Please cite as:

@INPROCEEDINGS{Jancsary2011d,
author = {Jeremy Jancsary and Gerald Matz},
title = {Convergent decomposition solvers for tree-reweighted free energies},
booktitle = {14th International Conference on Artificial Intelligence and Statistics (AISTATS)},
year = {2011}
}