AnnealedMAP-UniversityofPittsburgh.PDFVIP

628 YUAN ET AL. UAI 2004 Annealed MAP Changhe Yuan Tsai-Ching Lu Marek J. Druzdzel Decision Systems Laboratory HRL Laboratories, LLC Decision Systems Laboratory Intelligent Systems Program Malibu, CA 90265 School of Information Sciences and University of Pittsburgh tlu@ Intelligent Systems Program Pittsburgh, PA 15260 University of Pittsburgh cyuan@ Pittsburgh, PA 15260 marek@ Abstract instantiation of some target nodes1 given the states of some of the observable nodes in Bayesian networks. Researchers have proposed various approaches to solve Maximum a Posteriori assignment (MAP) is the MAP problem [6, 7, 8, 19, 20]. The state of the art the problem of finding the most probable in- MAP algorithm, proposed in a recent paper by Park stantiation of a set of variables given the and Darwiche [20], is a branch-and-bound depth-first partial evidence on the other variables in a search algorithm. It is an efficient algorithm, espe- Bayesian network. MAP has been shown to cially when the search spaces of the problems are not