Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Tightening MRF Relaxations with Planar Subproblems
Julian Yarkony, Ragib Morshed, Alexander Ihler, Charless Fowlkes
We describe a new technique for computing lower-bounds on the minimum energy configuration of a planar Markov Random Field (MRF). Our method successively adds large numbers of constraints and enforces consistency over binary projections of the original problem state space. These constraints are represented in terms of subproblems in a dual-decomposition framework that is optimized using subgradient techniques. The complete set of constraints we consider enforces cycle consistency over the original graph. In practice we find that the method converges quickly on most problems with the addition of a few subproblems and outperforms existing methods for some interesting classes of hard potentials.
Pages: 770-777
PS Link:
PDF Link: /papers/11/p770-yarkony.pdf
AUTHOR = "Julian Yarkony and Ragib Morshed and Alexander Ihler and Charless Fowlkes",
TITLE = "Tightening MRF Relaxations with Planar Subproblems",
BOOKTITLE = "Proceedings of the Twenty-Seventh Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-11)",
ADDRESS = "Corvallis, Oregon",
YEAR = "2011",
PAGES = "770--777"

hosted by DSL   •   site info   •   help