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