August 6, 2009

(Aug 06 3-5pm) Pre-meeting Overview: Wainwright / Jordan, ch 8, p195-213

Filed under: Uncategorized — umassliving @ 10:06 am
Tags: ,

Section 8 covers the problem of mode computation. That is given a probability distribution, compute the most probable configuration or the mode. It turns out that, this problem also has a variational representation as made explicit in Theorem 8.1 (see Appendix B.5. for the proof).  Similar to our treatment in chapter 4, this variational problem can be solved exactly for tree-structured and Gaussian graphical models. Some points to focus on for this week:

  • The objective function is simpler than the one for inference since it does not include A^*, and so the main source of difficulty is in characterizing the space of mean parameters, \mathcal{M} explicitly.¬†It should be clear that the optimization problem is an integer programming one (wikipedia).
  • Section 8.2 transforms the IP problem to a LP one over the set \mathbb{L}(G) for the case of tree-structured distributions and shows that a Lagrangian method for solving the dual of the LP are the max-product updates. Note that this result does not carry over to non-tree-structured graphs as shown in section 8.4.2.
  • Section 8.3 discusses the exact computation of the mode for Gaussian graphical models (see Appendix C).
  • Section 8.4.1 discusses first order LP relaxation for computing the mode of a discrete graphical model with cycles, and discusses the concept of strong and weak persistency.
« Previous Page

Blog at