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.

Advertisements