Dynamic weighting A* search-based MAP algorithm for Bayesian networks

Authors:

Xiaoxun Sun
Computer Science Department
University of Southern California
Los Angeles, CA 90089
e-mail: xiaoxuns@usc.edu

Marek J. Druzdzel
Decision Systems Laboratory
School of Information Sciences
and Intelligent Systems Program
University of Pittsburgh
135 North Bellefield Avenue
Pittsburgh, PA 15260, U.S.A.
e-mail: marek@sis.pitt.edu

Changhe Yuan
Department of Computer Science and Engineering
Mississippi State University
Mississippi State, MS 39762
e-mail: cyuan@cse.msstate.edu

Abstract:

In this paper we propose the Dynamic Weighting A* (DWA*) search algorithm for solving MAP problems in Bayesian networks. By exploiting asymmetries in the distribution of MAP variables, the algorithm is able to greatly reduce the search space and offer excellent performances both in terms of accuracy and efficiency.