Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Negative Tree Reweighted Belief Propagation
Qiang Liu, Alexander Ihler
We introduce a new class of lower bounds on the log partition function of a Markov random field which makes use of a reversed Jensen's inequality. In particular, our method approximates the intractable distribution using a linear combination of spanning trees with negative weights. This technique is a lower-bound counterpart to the tree-reweighted belief propagation algorithm, which uses a convex combination of spanning trees with positive weights to provide corresponding upper bounds. We develop algorithms to optimize and tighten the lower bounds over the non-convex set of valid parameter values. Our algorithm generalizes mean field approaches (including naive and structured mean field approximations), which it includes as a limiting case.
Pages: 332-339
PS Link:
PDF Link: /papers/10/p332-liu.pdf
AUTHOR = "Qiang Liu and Alexander Ihler",
TITLE = "Negative Tree Reweighted Belief Propagation",
BOOKTITLE = "Proceedings of the Twenty-Sixth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-10)",
ADDRESS = "Corvallis, Oregon",
YEAR = "2010",
PAGES = "332--339"

hosted by DSL   •   site info   •   help