# UMass LIVING

## September 19, 2009

### (Sep 25 12-2pm) Pre-meeting Overview: Energy Minimization via Graph Cuts

Filed under: Uncategorized — umassliving @ 4:39 pm
Tags: ,

This week, continuing the theme of MAP inference, we’ll look at graph cut methods for energy minimization.

This will be the main paper: What Energy Functions Can Be Minimized via Graph Cuts? Komogorov, Zabih

This additional paper may help in understanding graph cuts: Fast Approximate Energy Minimization via Graph Cuts. Boykov, Veksler, Zabih.

There is no paper set yet for this week.  Some possibilities:

Variable Elimination, Constructing the Pseudo-tree, Min-fill, and Mini-bucket heuristic

A two week sequence of:

The first paper would be related to our previous reading, in that they do search with branch and bound.

Post your suggestions soon, with the aim of settling on a paper by mid-day Monday.

### (Sep 18 12-2pm) Meeting Summary: Best-First AND/OR Search for MPE (Marinescue, Dechter)

Filed under: Uncategorized — umassliving @ 4:31 pm
Tags: ,

We began with a discussion of MPE versus MAP and max-product versus sum-product.  MPE is concerned with the assignment to all variables that gives highest probability.  MAP is a generalization of MPE where we want the maximum assignment to a subset of variables, marginalizing out the remaining variables.  Due to the marginalization, MAP is more difficult.

Max-product can be used to compute the MPE.  However, when inference can also be done using sum-product and taking the value that gives you the maximum of the computed marginal distribution.  If our variables are letters in a particular word, then max-product gives us the word with highest probability, while sum-product gives us each individual letter with highest probability (marginalizing over the possible assignments to the other letters).

There was the question on the requirements of being a pseudo-tree and how to create a pseudo-tree.  The key was that edges in the original graph, but not in the pseudo-tree, must be back-arcs, that is, they must connect a node to its ancestor in the tree.  This is required so that it is possible to compute the relevant CPTs when traversing a single branch.

There was also the question of how AOBF differs from A*.  It appears that they are the same, the only difference being that AOBF provides the framework for taking advantage of conditional independencies in the original graph.

A subquestion came up in exactly how AOBF is done.  We noted that $h(\cdot)$ is the overestimate of the remaining probabilities to be set, and that the bottom-up propagation revises the initial overestimates $v(\cdot)$.  The marked arcs indicate, given the current estimates, which path is best and should be taken (although there will be ties, for instance when choosing which child to choose at an AND node), in which case a path can be chosen arbitrarily.  The key is that the marked arcs may change, if later choices revise the overestimates accordingly.

More later.

## September 14, 2009

### (Sep 18 12-2pm) Pre-meeting Overview: Best-First AND/OR Search for MPE (Marinescue, Dechter)

Filed under: Uncategorized — umassliving @ 11:57 am
Tags: ,

Here is the reading for this week:

http://www.ics.uci.edu/%7Ecsp/r144.pdf

The motivation for reading this paper is as follows. In our work on both OCR and on Scene Text Recognition, I have been somewhat less focused on parameter setting, and somewhat more focused on finding the MAP solution, or the Most Probable Explanation (MPE) solution.

There are many ways to do this, including:

1) Loopy Belief Propagation, or Max Product; (problems: convergence not guaranteed; if it converges, still don’t know if we have the right solution)

2) Linear programming on a relaxed version of the marginal polytope, using techniques of Wainwright, or the cutting plane inequalities we just read about in Jaakkola and Sontag, currently under investigation by Gary.

3) A* search as being investigated by David and Jackie at the moment.

4) Graph cut methods.  These work on binary labelings with submodular potentials, and can be extended to multi-class labelings using $\alpha$-expansion moves.  For instance, see http://www.cs.cornell.edu/~rdz/Papers/KZ-PAMI04.pdf

and probably others.

I’m trying to learn more about the A* version, and in particular, compare it to the Jaakkola Sontag approach. I’m hoping this paper illuminates graph-search type methods of solving the MAP assignment problem.

### (Sep 09 1-3pm) Meeting Summary: New Outer Bounds on the Marginal Polytope (Sontag, Jaakkola)

Filed under: Uncategorized — umassliving @ 11:53 am
Tags: ,

(place holder, to be filled in by Moe)

## September 5, 2009

### (Sep 09 1-3pm) Pre-meeting Overview: New Outer Bounds on the Marginal Polytope (Sontag, Jaakkola)

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

Meeting will be in room 243.

This week we’ll be covering the following paper from NIPS 2007 (best student paper) – Sontag and Jaakola, “New Outer Bounds on the Marginal Polytope“.

Aside from the paper, we will also need to deal with two organizational issues, when to have our regular meeting for the rest of fall semester, and what topics we want to cover (at least decide upon the first topic to cover).  See the previous organizational post for details.

Paper Overview:

This paper presents a new variational algorithm for inference in discrete (binary & non-binary) MRF’s. Recall that the main difficulty in exact inference is in explicitly characterizing the marginal polytope and in exactly computing the conjugate dual. The main contribution of this paper is a new [tighter] outer-bound on the marginal polytope. For the conjugate dual, their algorithm utilizes existing approximations such as the log-determinant and tree-reweighted (TRW) approximations.

A broader goal of this paper is in highlighting an emerging connection between polyhedral combinatorics and probabilistic inference. To this end, their outer-bound for the marginal polytope is based on a cutting-plane algorithm (Algorithm 1 on page 3). A key aspect cutting-plane algorithms is in having an efficient mechanism for detecting violated constraints (Step 5 of Algorithm 1). One contribution in this paper is in using the cycle inequalities for which efficient separation algorithms are known (Section 2, page 5). A second main contribution is extending these inequalities and the separation mechanism to non-binary MRF’s (Section 4). Notice that the extension to non-pairwise MRF’s is trivial since any non-pairwise MRF can be easily converted to a pairwise one by introducing auxiliary variables (as described in Appendix E.3 of Wainwright & Jordan). The first two pages of the paper provide a nice & succinct summary of most of the points we covered in Wainwright & Jordan.

The experiments in this paper show the improvement in their inference procedure on computing marginals and MAP estimation for protein side-chain prediction.

## September 3, 2009

### Fall 2009 Organization

Filed under: Uncategorized — umassliving @ 6:09 pm
Tags: ,

Please fill out this poll as soon as you roughly know your schedule: http://www.doodle.com/6s9wngy4g239wtvy (ignore the calendar dates).

Remember, only mark red=do not have time if it is absolutely a conflict you can’t change, like a class.  Otherwise mark less desirable choices with yellow=could make time if absolutely necessary.

The time for the meetings for the rest of fall semester will be Friday, 12-2pm.

To summarize the end of our last meeting, we’ve decided to search through relevant conferences (NIPS, ICML, CVPR, ICCV, ECCV, BMVC) for best papers, orals, or tutorials which we would like to cover over the fall.  For individual papers, we would first spend a few meetings covering the fundamental theory necessary to understand the papers as preparation.

One possible fall back if this doesn’t work out is to cover convex optimization.

One thing to keep in mind is that, if we feel like the min(two hours reading), two hour meeting format doesn’t leave enough time to prepare each week, we can move to a min(three hours reading), one hour meeting format, where, as Moe emphasized in the last meeting, two/three hours reading doesn’t need to mean read exclusively on your own.  Discussions with others in advance of the meeting is encouraged.

### (Sep 03 3-5pm) Meeting Summary: Convex Relaxations for MAP Estimation (Kumar, Kolmogorov, Torr)

Filed under: Uncategorized — umassliving @ 6:03 pm
Tags: ,

We discussed the various types of relaxations of the original IP for MAP estimation, where the two non-convex constraints are the integer constraint {1, -1} on the variables, and the constraint that $X = x x^T$.  In general, it was assumed that the tightest relaxation was the SDP relaxation (though also the most computational demanding), followed by SOCP and QP, with LP being the least tight of the relaxations.

However, this paper showed that, using only certain SOC constraints associated with edges of the MRF, that the SOCP was equivalent to the QP, and both were dominated by the LP.  We discussed the notion of dominance, and why it makes sense that, for the minimization problem, a relaxation dominates a second relaxation if the first has a greater minimum value than the second.  One key to understanding this is to see that every relaxation uses a feasible set that is a super set of the original problem, thus the original problem has a greater minimum value than every relaxation (why?) and hence dominates every relaxation, as would be expected.

It took me a little while to prove the facts stated in the paper regarding $z_{a;i}$, on page 95 below equation (46) and at the beginning of page 96.  The set on page 95 can be proved by considering the different cases of positive and negative $x$, for instance $x_{b;j} \geq 0 \geq x_{a;i}$, with $x_{b;j} \geq | x_{a;i} |$.  The first inequality on page 96 is easy to prove (in fact I think it’s an equality).  The second inequality can be proven by using the fact that the geometric average is always less than or equal to the arithmetic average.

The final section of the paper deals with ways of moving forward, given the theoretical results of the paper.  One thing to do is to simply add the linear marginalization constraints to the SOCP, rather than using the SOC constraints on edges.  Cycle inequality SOC constraints can be added to the SOCP (to get SOCP-C), but linear cycle inequalities can also be added to the LP.  The paper ends by giving additional SOC constraints on cliques (SOCP-Q), results in a feasible region that is not a super set of the corresponding LP feasible region.

The takeaway message is that, only using the straightforward SOC constraints on edges is actually dominated by the LP.  In general, SOCP is seen as a balance between LP and SDP, but in order to do better than LP, additional SOC constraints must be used.

The Ravikumar Lafferty QP paper is a good related paper on this general topic.  One thing that is not immediately clear is why, in the QP paper, the LP performs substantially worse, despite the results in the paper we read.  It could be that the LP or QP used in the Ravikumar paper do not match those in the paper we read.

Create a free website or blog at WordPress.com.