  Finding the most probable assignment (MAP) in a general graphical model is
known to be NP hard but good approximations have been attained with max-product
belief propagation (BP) and its variants. In particular, it is known that using
BP on a single-cycle graph or tree reweighted BP on an arbitrary graph will
give the MAP solution if the beliefs have no ties. In this paper we extend the
setting under which BP can be used to provably extract the MAP. We define
Convex BP as BP algorithms based on a convex free energy approximation and show
that this class includes ordinary BP with single-cycle, tree reweighted BP and
many other BP variants. We show that when there are no ties, fixed-points of
convex max-product BP will provably give the MAP solution. We also show that
convex sum-product BP at sufficiently small temperatures can be used to solve
linear programs that arise from relaxing the MAP problem. Finally, we derive a
novel condition that allows us to derive the MAP solution even if some of the
convex BP beliefs have ties. In experiments, we show that our theorems allow us
to find the MAP in many real-world instances of graphical models where exact
inference using junction-tree is impossible.
