Estimating MAP-configurations in graphical models by exploiting structure

The max-product algorithm can be used to obtain approximate MAP-assignments of the probability distribution defined by a graphical model. On tree-structured graphical models the MAP-assignment is exact and the max-product algorithm is equivalent to the Viterbi-algorithm. On general models one may run into the following problems: 1. The algorithm does not converge; 2. the single node marginals are not unique. The first problem can be solved by using a provably convergent double loop algorithm. In the second case it is not straightforward how to obtain a global assignment from the locally defined marginals, due to loops in the graph. An obvious solution to the second problem is to use the approximate marginals for pairs (or any tractable number) of nodes and use the correlations to estimate a global MAP-assignment. A simple strategy is to define a satisfiability problem which entails that the global MAP-assignment should be a MAP-assignment of each local marginal. This should in principle solve the problem of non-unique marginals. However, this satisfiability problem is not guaranteed to have a solution. The existence of a solution depends critically on the nature of the interactions between the nodes in the graphical model.