On Message-Passing, MAP Estimation in Graphical Models and DCOPs

Akshat Kumar, William Yeoh, and Shlomo Zilberstein. On Message-Passing, MAP Estimation in Graphical Models and DCOPs. International Workshop on Distributed Constraint Reasoning (DCR), 57-70, Barcelona, Spain, 2011.

Abstract

The maximum a posteriori (MAP) estimation problem in graphical models is a problem common in many applications such as computer vision and bioinformatics. For example, they are used to identify the most likely orientation of proteins in protein design problems. As such, researchers in the machine learning community have developed a variety of approximate algorithms to solve them. On the other hand, distributed constraint optimization problems (DCOPs) are well-suited for modeling many multi-agent coordination problems such as the coordination of sensors in a network and the coordination of power plants. In this paper, we show that MAP estimation problems and DCOPs bear strong similarities and, as such, some approximate MAP algorithms such as iterative message passing algorithms can be easily tailored to solve DCOPs as well.

Bibtex entry:

@inproceedings{KYZdcr11,
  author	= {Akshat Kumar and Shlomo Zilberstein},
  title		= {On Message-Passing, {MAP} Estimation in Graphical Models and {DCOP}s}
  booktitle     = {International Workshop on Distributed Constraint Reasoning},
  year		= {2011},
  pages		= {57-70},
  address       = {Barcelona, Spain},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/KYZdcr11.html}
}

shlomo@cs.umass.edu