 |
Center for Nonlinear Studies |
Computing the MAP assignment in graphical models is generally intractable. 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. I'll describe how graph covers can be used to provide necessary and sufficient conditions for continuous MAP relaxations to be tight. This characterization can be used to give simple proofs that the relaxation is tight for log-concave decomposable and log- supermodular decomposable models. I'll discuss the relationship between these two seemingly distinct classes of functions, providing specific conditions under which the MAP relaxation can and cannot be tight. Finally, I'll discuss the challenges, and theoretical gaps that remain in the study of continuous graphical models.
Host: Michael Chertkov