Complexity Results and Approximation Strategies for MAP Explanations

Abstract

MAP is the problem of finding a most probable instantiation of a set of variables given evidence. MAP has always been perceived to be significantly harder than the related problems of computing the probability of a variable instantiation Pr, or the problem of computing the most probable explanation (MPE). This paper investigates the complexity of MAP in Bayesian networks. Specifically, we show that MAP is complete for NP^PP and provide further negative complexity results for algorithms based on variable elimination. We also show that MAP remains hard even when MPE and Pr become easy. For example, we show that MAP is NP-complete when the networks are restricted to polytrees, and even then can not be effectively approximated. Given the difficulty of computing MAP exactly, and the difficulty of approximating MAP while providing useful guarantees on the resulting approximation, we investigate best effort approximations. We introduce a generic MAP approximation framework. We provide two instantiations of the framework; one for networks which are amenable to exact inference Pr, and one for networks for which even exact inference is too hard. This allows MAP approximation on networks that are too complex to even exactly solve the easier problems, Pr and MPE. Experimental results indicate that using these approximation algorithms provides much better solutions than standard techniques, and provide accurate MAP estimates in many cases.

References in corpus (1)

• Loopy Belief Propagation for Approximate Inference: An Empirical Study

Cited by in corpus (20)

• Survey on Models and Techniques for Root-Cause Analysis
• Strategy Selection in Influence Diagrams using Imprecise Probabilities
• Constrained Sampling and Counting: Universal Hashing Meets SAT Solving
• Optimal Value of Information in Graphical Models
• Variational Algorithms for Marginal MAP
• Belief Updating and Learning in Semi-Qualitative Probabilistic Networks
• A Variational Approach for Approximating Bayesian Networks by Edge Deletion
• Decomposition Bounds for Marginal MAP
• The Computational Complexity of Sensitivity Analysis and Parameter Tuning
• The Complexity of Approximately Solving Influence Diagrams
• On the Complexity of Strong and Epistemic Credal Networks
• New Results for the MAP Problem in Bayesian Networks
• From influence diagrams to multi-operator cluster DAGs
• Solving Limited Memory Influence Diagrams
• Revisiting Algebra and Complexity of Inference in Graphical Models
• Exact Decoding on Latent Variable Conditional Models is NP-Hard
• Approximate MMAP by Marginal Search
• On Imperfect Recall in Multi-Agent Influence Diagrams
• Probabilistic Parameterized Polynomial Time
• A polynomial time algebraic solution to exact marginal inference in Markov Random Field models