Estimating MAP-configurations in graphical models by exploiting structure

author: Kees Albers, Radboud University Nijmegen
published: Feb. 25, 2007,   recorded: January 2005,   views: 4300

Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


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.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: