Relax then compensate: on max-product belief propagation and more
Arthur Choi, Adnan Y. Darwiche · 2009
We introduce a new perspective on approximations to the maximum a posteriori (MAP)taskinprobabilisticgraphicalmodels,thatisbasedonsimplifyingagiven instance, and then tightening the approximation. First, we start with a structural relaxation of the original model. We then infer from the relaxation its deficiencies, and compensate for them. This perspective allows us to identify two distinct classes of approximations. First, we find that max-product belief propagation can beviewedasawaytocompensateforarelaxation,basedonaparticularidealized case for exactness. We identify a second approach to compensation that is based on a more refined idealized case, resulting in a new approximation with distinct properties. We go on to propose a new class of algorithms that, starting with a relaxation, iteratively seeks tighter approximations. 1