`

Timezone: »

Oral
MAP estimation in Binary MRFs via Bipartite Multi-cuts
Sashank Jakkam Reddi · Sunita Sarawagi · Sundar Vishwanathan

Tue Dec 07 04:40 PM -- 05:00 PM (PST) @ Regency Ballroom
We propose a new LP relaxation for obtaining the MAP assignment of a
binary MRF with pairwise potentials. Our relaxation is derived from reducing the MAP assignment problem to an instance of a recently
proposed Bipartite Multi-cut problem where the LP relaxation is guaranteed to provide an $O(\log k)$ approximation where $k$ is the
number of vertices adjacent to non-submodular edges in the MRF. We then propose a combinatorial algorithm to efficiently solve the LP and
also provide a lower bound by concurrently solving its dual to within
an $\epsilon$ approximation. The algorithm is up to an order of
magnitude faster and provides better MAP scores and bounds than the
state of the art message passing algorithm that
tightens the local marginal polytope with third-order marginal constraints.