Information for topics

Topic Id:

ID topic:	501
Partner Email:	L.J.M.Rothkrantz@tudelft.nl
Project Title:	Dynamic Weighting A*Search-Based MAP Algorithm for Bayesian Networks
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.
Advisor:	Leon Rothkrantz
Link:
Degree:	Master
Keywords:
Computer Software
Algorithms & problem solving
Artificial intelligence & Neural networks
Data mining
Data modeling