Abstract: 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.
Introduction
Finding the Maximum A Posteriori (MAP) configuration in Markov Random Fields (MRFs) is a fundamental but NP-hard challenge in machine learning and computer vision. Standard approaches often relax this combinatorial problem into a Linear Program (LP). While tree-based relaxations are efficient, they frequently fail to find optimal solutions in graphs with cycles. Adding cycle constraints can resolve this, but the exponential number of possible cycles makes traditional cutting-plane methods slow and often unable to close the duality gap—the difference between the lower bound and the energy of the best-found solution.
Methodology
The authors introduce Planar Subproblems (PSP), a dual-decomposition framework that breaks the MAP inference problem into tractable subproblems. The core innovation lies in using binary planar MRFs as subproblems. Unlike general MRFs, binary planar models can be solved exactly in polynomial time. For multi-state problems, the authors employ a "one-versus-all" projection, creating binary subproblems that ask if a variable belongs to a specific state or not, based on a current "best guess" solution.
By incorporating these planar subproblems, the algorithm can enforce consistency over large collections of cycles simultaneously, rather than one by one. This "batch" constraint enforcement is optimized using a projected subgradient method (specifically a Bundle Trust solver) to align parameters across subproblems until a consistent global solution is reached.
Experimental Results
The method was evaluated on synthetic $N \times N$ grids with two potential types: Type-I (Random), representing general unstructured problems, and Type-II (Layered), simulating structured real-world constraints (e.g., image labeling where certain states cannot touch). Type-II models are particularly challenging as they induce long-range dependencies that typically confuse standard solvers.
On these "hard" Type-II problems, PSP significantly outperformed the Max-Product Linear Programming (MPLP) baseline. It not only found exact solutions more frequently but also did so up to 15x faster when "hot-started" with initial planar subproblems. In Type-I problems, while MPLP often improved its lower bound faster initially, PSP ultimately solved a higher percentage of instances.
Conclusion
PSP offers a powerful "sweet spot" in complexity, leveraging the tractability of planar binary MRFs to enforce complex cycle consistencies efficiently. While subgradient descent can be slower than coordinate descent for high-precision convergence, the ability to close the duality gap on structured, hard problems marks a significant advancement. Future work may explore extending these subproblems to non-planar or higher-dimensional graphs and optimizing performance for larger state spaces.
Summary updated