Annealed MAP
Changhe Yuan, TsaiChing Lu, Marek Druzdzel
Abstract:
Maximum a Posteriori assignment (MAP) is the problem of finding the most probable instantiation of a set of variables given the partial evidence on the other variables in a Bayesian network. MAP has been shown to be a NPhard problem [22], even for constrained networks, such as polytrees [18]. Hence, previous approaches often fail to yield any results for MAP problems in large complex Bayesian networks. To address this problem, we propose AnnealedMAP algorithm, a simulated annealingbased MAP algorithm. The AnnealedMAP algorithm simulates a nonhomogeneous Markov chain whose invariant function is a probability density that concentrates itself on the modes of the target density. We tested this algorithm on several real Bayesian networks. The results show that, while maintaining good quality of the MAP solutions, the AnnealedMAP algorithm is also able to solve many problems that are beyond the reach of previous approaches.
Keywords: null
Pages: 628635
PS Link:
PDF Link: /papers/04/p628yuan.pdf
BibTex:
@INPROCEEDINGS{Yuan04,
AUTHOR = "Changhe Yuan
and TsaiChing Lu and Marek Druzdzel",
TITLE = "Annealed MAP",
BOOKTITLE = "Proceedings of the Twentieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI04)",
PUBLISHER = "AUAI Press",
ADDRESS = "Arlington, Virginia",
YEAR = "2004",
PAGES = "628635"
}

