August 11, 2009

(Aug 13 3-5pm) Pre-meeting Overview: Wainwright / Jordan, ch 8, p214-233

Filed under: Uncategorized — umassliving @ 3:49 pm
Tags: ,

Section 8.4.3 till 8.5

The main points that will be covered in these subsections are

(1) Extending the LP view of mode finding that we saw for max-product on tree graphs to reweighted-max-product.

(2) Examples of first order LP relaxations.

(3) Higher order LP approximations and how they can be more accurate.

Section 8.4.3 extends the arguments from earlier subsections in this chapter to show that reweighted max-product (and tree-reweighted Bethe variational problem) can be thought of as an LP problem. Conditions 8.23 have to be met for the max-product solution and LP problem solution to be dual of one another.

Section 8.4.4 discusses examples where an LP problem is formulated from a graph problem. Example 8.3 shows how the Error-control coding problem may be thought of as an LP problem. Example 8.4 shows the same for the (a) Ising model, (b) (Maximum Weight) Independent Set problem, (c) (Minimum Weight) Vertex Cover problem, (d) Max-cut problem. These are all examples of intractable problems, but a first oder LP approximate solution is possible. Example 8.5 is another classic graph problem, Maximum Weight Matching problem, solved using an LP.

Section 8.5 discusses higher order LP relaxations by using the marginal polytopes defined on hypergraphs (rather than the polytopes defined by pairwise interactions in a tree). The main claim and proof in this section is that higher order relaxation LPs are more accurate the lower order relaxation LPs for the same graphical model. The t^{th} relaxation LP solution, where t is the tree-width of the hypergraph for the graphical model, is the same as the exact solution on the original polytope \mathbb{M}(G).

Finally, example 8.6 shows how the second order relaxation adds additional constraints that makes the solution “tighter” than in a first order relaxation. This is done by solving the same problem solved earlier in Example 8.3 by the two methods, and comparing the constraints and considering one solution \tilde{\tau} = (1, \frac{1}{2}, \frac{1}{2}, 0).

We will be reading papers next week, so please come with suggestions for papers you think are interesting.



  1. A minor thing to think about: on page 223, a definition is given for supermodular and submodular interactions. If you look at the definition of \theta_{st} for the vertex cover problem (second equation on page 222), it is clearly submodular, yet the bottom of page 223 says that the vertex cover problem involves supermodular potentials. What accounts for this discrepancy?

    Comment by Gary — August 11, 2009 @ 3:52 pm | Reply

  2. Potential papers to read next week:

    M. J. Wainwright. Estimating the “wrong” graphical model: Benefits in the computation-limited setting. –

    M. J. Wainwright, T. Jaakkola and A. S. Willsky. Tree-based reparameterization framework for analysis of sum-product and related algorithms. –

    Globally Optimal Solutions for Energy Minimization in Stereo Vision using Reweighted Belief Propagation
    Talya Meltzer, Chen Yanover, Yair Weiss –

    A Global Perspective on MAP Inference for Low-Level Vision
    Oliver J. Woodford, Carsten Rother and Vladimir Kolmogorov. –

    Comment by Gary — August 12, 2009 @ 5:12 pm | 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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

Blog at

%d bloggers like this: