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:

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

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.



  1. A General Scheme for Automatic Generation of Search Heuristics from Specification Dependencies –

    This paper describes Bucket Elimination and the Mini-bucket heuristic. Bucket Elimination is, I believe, another name for variable elimination, e.g. pick an ordering over the variables and move in the sum/max over each variable as much as possible.

    Mini-bucket elimination is an approximation to bucket elimination that generates an upper bound to the true MPE, by breaking apart the functions within one particular max into mini-groups, and computes the max over each mini-group separately (an upper bound since max_x (f(x)g(x)) \leq (max_x f(x))(max_x g(x))).

    I think mini-bucket elimination can be seen as bucket elimination on an auxiliary graph containing multiple copies of each node corresponding to the different mini-buckets, and essentially breaking apart some of the dependencies.

    The intermediary functions produced by mini-bucket can be used as heuristics, when using a search order equivalent to the order used in the elimination.

    Comment by Gary — September 14, 2009 @ 3:29 pm | Reply

  2. Folks might want to read chapters 4 and 5 of Artificial Intelligence, A Modern Approach by Russell and Norvig to refresh their memories on search and constraint based techniques

    Comment by Erik — September 17, 2009 @ 10:44 am | Reply

  3. I was having a bit of a problem understanding how AND/OR search spaces are sensitive to independencies in the model whereas typical (OR) search spaces are not. The example on page 11 of their paper on AND/OR search spaces ( was helpful in clarifying this point.

    Comment by David — September 18, 2009 @ 10:43 am | Reply

RSS feed for comments on this post.

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

Create a free website or blog at

%d bloggers like this: