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.

1 Comment »

  1. One thing that I think is worth doing is taking the second form of the dual function \mathcal{Q} in equation (8.9), plugging in the definition of \nu in (8.10), and verifying that it matches the form of the dual function given in Proposition 8.2.

    If you do that, you’ll find that one set of the Lagrange multipliers \lambda_{ts} are missing. Why?

    Also, I believe there is a typo on page 203 in the definition of \gamma_s(x_s), and that the \theta_s in front of the x^2 term should be the free parameter \gamma_s.

    Comment by Gary — August 6, 2009 @ 10:12 am | Reply

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at

%d bloggers like this: