Solving MAP Exactly using Systematic Search
  MAP is the problem of finding a most probable instantiation of a set of
variables in a Bayesian network given some evidence. Unlike computing posterior
probabilities, or MPE (a special case of MAP), the time and space complexity of
structural solutions for MAP are not only exponential in the network treewidth,
but in a larger parameter known as the "constrained" treewidth. In practice,
this means that computing MAP can be orders of magnitude more expensive than
computing posterior probabilities or MPE. This paper introduces a new, simple
upper bound on the probability of a MAP solution, which admits a tradeoff
between the bound quality and the time needed to compute it. The bound is shown
to be generally much tighter than those of other methods of comparable
complexity. We use this proposed upper bound to develop a branch-and-bound
search algorithm for solving MAP exactly. Experimental results demonstrate that
the search algorithm is able to solve many problems that are far beyond the
reach of any structure-based method for MAP. For example, we show that the
proposed algorithm can compute MAP exactly and efficiently for some networks
whose constrained treewidth is more than 40.
