A new criterion for choosing planar subproblems in MAP-MRF inference

We propose an efficient algorithm for finding the maximum a posteriori (MAP) configuration in Markov random fields (MRFs) under the framework of dual decomposition. In the framework, tractable subproblems like binary planar subproblems (BPSPs) have been introduced to obtain more accurate solutions than that of tree-structured subproblems. However, since there are exponentially many BPSPs and they have very different effects on tightening the linear programming (LP) relaxation, the choice of the best BPSPs becomes an important open problem. In this paper, we find that cycles of BPSPs have the equivalent potential structure with the cycles where k-ary cycle inequalities are defined. We further prove that adding a BPSP in the dual decomposition is equivalent to enforcing a set of k-ary cycle inequalities in the LP relaxation, which gives a new insight to the procedure of adding BPSPs. In addition, a new criterion for choosing BPSPs is proposed by first selecting the violated k-ary cycle inequalities and then packing as many of these violated cycles as possible into a BPSP. Experimental results show the effectiveness of our criterion.