MAP Complexity Results and Approximation Methods
  MAP is the problem of finding a most probable instantiation of a set of
nvariables in a Bayesian network, given some evidence. MAP appears to be a
significantly harder problem than the related problems of computing the
probability of evidence Pr, or MPE a special case of MAP. Because of the
complexity of MAP, and the lack of viable algorithms to approximate it,MAP
computations are generally avoided by practitioners. This paper investigates
the complexity of MAP. We show that MAP is complete for NP. We also provide
negative complexity results for elimination based algorithms. It turns out that
MAP remains hard even when MPE, and Pr are easy. We show that MAP is NPcomplete
when the networks are restricted to polytrees, and even then can not be
effectively approximated. Because there is no approximation algorithm with
guaranteed results, we investigate best effort approximations. We introduce a
generic MAP approximation framework. As one instantiation of it, we implement
local search coupled with belief propagation BP to approximate MAP. We show how
to extract approximate evidence retraction information from belief propagation
which allows us to perform efficient local search. This allows MAP
approximation even on networks that are too complex to even exactly solve the
easier problems of computing Pr or MPE. Experimental results indicate that
using BP and local search provides accurate MAP estimates in many cases.
