# UMass LIVING

## 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. 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$.