Dynamic Weighting A*Search-Based MAP Algorithm for Bayesian Networks

title: Dynamic Weighting A*Search-Based MAP Algorithm for Bayesian Networks
author: Xiaoxun Sun
published in: August 2005
appeared as: Master of Science thesis
Man-machine interaction group
Delft University of Technology
thesis PDF (295 KB)
paper PDF (200 KB)

Abstract

Maximum a Posteriori assignment (MAP) is the most probable instantiation of a set of variables given partial evidence on the remaining variables in a Bayesian network. Finding MAP has been proven to be an NP-hard problem, and it is not only exponential in the network treewidth, but also in the constrained treewidth. Exact approaches often fail to yield any results for MAP problems in very large Bayesian networks, and even approximate approaches may not yield acceptable solutions. We introduce the Dynamic Weighting A*(DWA*) search algorithm for solving MAP. By exploiting asymmetries in the distribution of MAP variables, the algorithm is able to greatly reduce the search space, yielding very good quality MAP solutions. Experimental results demonstrate that my algorithm finds solutions generally faster and with a lower variance in search time than existing algorithms.

 
blue line
University logo