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 relaxation LP solution, where is the tree-width of the hypergraph for the graphical model, is the same as the exact solution on the original polytope .

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 .

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

### Like this:

Like Loading...

*Related*

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 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 |

Potential papers to read next week:

M. J. Wainwright. Estimating the “wrong” graphical model: Benefits in the computation-limited setting. – http://www.eecs.berkeley.edu/~wainwrig/Papers/Wainwright06_JMLR.pdf

M. J. Wainwright, T. Jaakkola and A. S. Willsky. Tree-based reparameterization framework for analysis of sum-product and related algorithms. – http://www.eecs.berkeley.edu/~wainwrig/Papers/WaiJaaWil2003_trp.pdf

Globally Optimal Solutions for Energy Minimization in Stereo Vision using Reweighted Belief Propagation

Talya Meltzer, Chen Yanover, Yair Weiss – http://www.eecs.berkeley.edu/~wainwrig/Papers/WaiJaaWil2003_trp.pdf

A Global Perspective on MAP Inference for Low-Level Vision

Oliver J. Woodford, Carsten Rother and Vladimir Kolmogorov. – http://www.cs.ucl.ac.uk/staff/V.Kolmogorov/papers/MPF.html

Comment by Gary — August 12, 2009 @ 5:12 pm |