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

More later.