Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Planar Cycle Covering Graphs
Julian Yarkony, Alexander Ihler, Charless Fowlkes
Abstract:
We describe a new variational lower-bound on the minimum energy configuration of a planar binary Markov Random Field (MRF). Our method is based on adding auxiliary nodes to every face of a planar embedding of the graph in order to capture the effect of unary potentials. A ground state of the resulting approximation can be computed efficiently by reduction to minimum-weight perfect matching. We show that optimization of variational parameters achieves the same lower-bound as dual-decomposition into the set of all cycles of the original graph. We demonstrate that our variational optimization converges quickly and provides high-quality solutions to hard combinatorial problems 10-100x faster than competing algorithms that optimize the same bound.
Keywords:
Pages: 761-769
PS Link:
PDF Link: /papers/11/p761-yarkony.pdf
BibTex:
@INPROCEEDINGS{Yarkony11,
AUTHOR = "Julian Yarkony and Alexander Ihler and Charless Fowlkes",
TITLE = "Planar Cycle Covering Graphs",
BOOKTITLE = "Proceedings of the Twenty-Seventh Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-11)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2011",
PAGES = "761--769"
}


hosted by DSL   •   site info   •   help