UMass LIVING

September 19, 2009

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