abstract:  The MAP (maximum a posteriori hypothesis) problem in Bayesian networks is to find the most likely states of a set of variables given partial evidence on the complement of that set. Standard structurebased inference methods for finding exact solutions to MAP, such as variable elimination and jointree algorithms, have complexities that are exponential in the <em>constrained</em> treewidth of the network. A more recent algorithm, proposed by Park and Darwiche, is exponential only in the treewidth and has been shown to handle networks whose constrained treewidth is quite high. In this paper we present a new algorithm for exact MAP that is not necessarily limited in scalability even by the treewidth. This is achieved by leveraging recent advances in compilation of Bayesian networks into arithmetic circuits, which can circumvent treewidthimposed limits by exploiting the local structure present in the network. Specifically, we implement a branchandbound search where the bounds are computed using lineartime operations on the compiled arithmetic circuit. On networks with local structure, we observe ordersofmagnitude improvements over the algorithm of Park and Darwiche. In particular, we are able to efficiently solve many problems where the latter algorithm runs out of memory because of high treewidth.
