Exactness of Approximate MAP Inference in Continuous MRFs
Computing the MAP assignment in graphical models is generally intractable. As a result, for discrete graphical models, the MAP problem is often approximated using linear programming relaxations. Much research has focused on characterizing when these LP relaxations are tight, and while they are relatively well-understood in the discrete case, only a few results are known for their continuous analog. In this work, we use graph covers to provide necessary and sufficient conditions for continuous MAP relaxations to be tight. We use this characterization to give simple proofs that the relaxation is tight for log-concave decomposable and logsupermodular decomposable models. We conclude by exploring the relationship between these two seemingly distinct classes of functions and providing specific conditions under which the MAP relaxation can and cannot be tight.
This paper provides a theoretical study of tightness of the LP relaxations for MRFs with continuous variables. The paper provides the following contributions: - Generalization of the results of [13] to the case of continuous MRFs: formulation of the value of the LP relaxation via graph covers (theorem 3.1) - Formulation of the two special cases when the LP relaxation is tight (log-concave decomposable and log-supermodular decomposable models). Proofs are based on theorem 3.1. The paper introduces the family of log-supermodular decomposable functions. - Condition allowing to identify cases when the MAP relaxation is not tight (theorem 4.7). The paper is relatively well written, although some parts are quite hard to follow. The derivations presented in the paper seem to be correct. I have several comments related to correctness/clarity: 1) Proof of theorem 3.3 is based on the repeated application of the definition of log-supermodularity (line 222) to the l.h.s. of line 233. This definition allows to upper bound the product of function values at different point by product of the function values at the point-wise maximum and minimum. At the same time the r.h.s line 233 contains only point-wise maximum (z^m) and not the point-wise minimums. Is this error critical for the result to hold? 2) Section 4.1 should be explaining relation of the two families of the functions in case of Gaussian MRFs. I could not get the relation based on the provided explanation. Lines 280-282 were not enough for my understanding. 3) I did not understand why section 4.2 was included into section 4, because it seemed to provide a separate result. The presented results seem to be original. The connections to other existing results are explained although sometimes are not reader-friendly (e.g. lines 354-355).