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 , and so the main source of difficulty is in characterizing the space of mean parameters, 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 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.

### Like this:

Like Loading...

*Related*

One thing that I think is worth doing is taking the second form of the dual function in equation (8.9), plugging in the definition of 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 are missing. Why?

Also, I believe there is a typo on page 203 in the definition of , and that the in front of the term should be the free parameter .

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