The approximation methods we’ve covered in chapters 4 and 5 have both been nonconvex. This chapter addresses the issue of how to create convex approximations, where both the set that we use is convex and the objective function that we seek to maximize is concave.

7.1 deals with the generic framework for the convex approximations. 7.2 shows how to convexify the algorithms we saw in chapter 4, while 7.3 shows how to create new algorithms that are convex, not based on using convex combinations. 7.4 shows a separate benefit of convexity in terms of algorithmic stability, and 7.5 discusses how the convex approximations for inference fit in to learning.

Errata:

- There is a missing subscript in equation (7.1) on page 167, the expectation should be .
- There should be (I believe) a in front of the second inner product in the second equation on page 176.

Important things to follow and think about:

- Why is the Bethe approximation to the entropy not generally concave?
- On page 167, in the discussion of the projection operation , how do we know that ?
- Understand 7.2.1. In particular, consider the distribution over spanning trees that places all its mass on one specific spanning tree. This seems very similar to structured mean field, where we just use the one spanning tree as the tractable subfamily we optimize over. Yet structured mean field gives us a lower bound on whereas tree-reweighted Bethe gives us an upper bound. What accounts for this difference? For instance, why does structured mean field give a lower bound when we know that , and we are subtracting off in the objective function?
- Convince yourself that you can obtain the tree-reweighted sum-product updates in equation (7.12) on page 172 by following the Lagrangian formulation of ordinary sum-product in chapter 4, and using the new messages .
- Understand the general ideas in 7.2.2 and 7.2.3, the exact details are not as important. For instance, understand why is generally not concave, but why using the re-weighting subject to gives a concave function.
- Understand the general idea in 7.3.1. The details are not as important, although for the interested, I have put some notes on this section below.
- Understand the benefit of the convexified algorithms for algorithmic stability and what it means for an algorithm to be globally Lipschitz stable, why that is important, and how Figure 7.3 suggests that ordinary sum-product is not globally Lipschitz stable.
- Understand how the convexified algorithms can be used within learning in 7.5. We use the fact that when upper bounds the true cumulant function, then the surrogate likelihood lower bounds the true likelihood. Yet in chapter 6, we saw how using mean field within EM also gives us a lower bound on the true likelihood, despite the fact that mean field gives a lower bound on the cumulant function. What accounts for this discrepancy?
- Understand the intuitative interpretation of example 7.3.

Slightly more esoteric details:

- On page 184, why do show up along the diagonal of ? Hint: each random variable is binary valued.
- On page 184, why is the constraint imply the constraint ? Use the Schur complement formula and the stated fact that if is symmetric and positive-definite, then so is the Schur complement of in .
- Here is a quick proof of that fact: we want to show that, if for all , , then, for all , where is the Schur complement of . Split into two components, and , with matching the size of , and matching the size of . Then we have, . Now substitute in since is symmetric, and assign . Putting that in and simplifying, we get , where was arbitrary, thus proving that is positive-definite.
- Now, how can we apply that to prove that implies ? If we let the single element 1 in the top left of be , and in the bottom right be , and take the Schur complement of , we get the fact that, if , then , and the second term is exactly , thus proving the implication.

- One thing I am unsure of is whether you can go the other direction, and show that implies . The wording in Wainwright seems to imply that you can, but it’s not clear to me how to do that using the Schur complement formula as they claim.
- The important thing is that we know that the constraint is an outer bound to the marginal polytope . To show this, we use the fact that if there is a distribution that realizes mean parameter , then letting be the random vector , we have for any vector , , proving that .
- So right now, we have is outer bounded by the constraint which in turn is outer bounded by the constraint , and uncertain as to whether the two constraints are equivalent or not.
- Why is it valid to replace the quantity within the determinant on page 184, to , as in equation (7.22) on page 185? Again we use the Schur complement formula, and the property that where is the Schur complement of in (see properties of determinant). Using this and the fact above that by setting as the single element 1 in the top right corner of , the Schur complement of is shows that the substitution is valid.
- Why does setting canonical parameters as in (7.28) lead to mean parameters matching the empirical mean parameters? The paper Tree-reweighted belief propagation algorithms and approximate ML estimation by pseudo-moment matching gives a proof that the optimal returned by the modified sum-product algorithm satisfies an admissibility condition that . Using the given in (7.28), we can see that satisfies this condition, and since the solution is unique, we have .
- On page 193, how do we know that ? From Holder’s inequality.

“Convince yourself that setting canonical parameters as in 7.28 leads to mean parameters matching the empirical mean parameters.”

This is actually more difficult than I thought at first glance, so I moved it to the slightly more esoteric details section and replaced it with something easier.

Comment by Gary — July 27, 2009 @ 1:04 pm |