Approximating MAP Using Local Search

Abstract

MAP is the problem of finding a most probable instantiation of a set of variables in a Bayesian network, given (partial) evidence about the complement of that set. Unlike computing priors, posteriors, and MPE (a special case of MAP), the time and space complexity of MAP is not only exponential in the network treewidth, but also 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 priors, posteriors or MPE. For this reason, MAP computations are generally avoided or approximated by practitioners. We have investigated the approximation of MAP using local search. The local search method has a space complexity which is exponential only in the network treewidth, as is the complexity of each step in the search process. Our experimental results show that local search provides a very good approximation of MAP, while requiring a small number of search steps. Practically, this means that the average case complexity of local search is often exponential only in treewidth as opposed to the constrained treewidth, making approximating MAP as efficient as other computations.