The paper studies the computational complexity of abductive reasoning in Bayesian belief networks, which are directed acyclic graphs augmented with conditional probability distributions residing in each node. Such networks can be modeled by finding posterior distribution given some evidence, by finding a maximum a-posterori probability (MAP) instantiation of all of the variables (representing nodes) in the network, or by other schemes. This paper is primarily concerned with complexity issues of finding a maximum a-posteori probability, called the MAP problem. The latter is defined as follows: Given a probability distribution over a set of variables \(V\), the evidence \(E\) which is an instantiation of a set of variables \(E \subseteq V\), find value assignment \(A\) to all of the variables \(V\) that maximizes \(P(A | E)\). It is shown that finding a maximum a-posterori probability is NP-hard in the general case, even if the size of the network is linear. To prove this result, a related problem called MAPBNETD is considered. The latter is defined as follows: Given a belief network, find whether there is an instantiation of variables such that its probability is at least \(P\). The result about the complexity of the MAP problem is extended to belief networks with several topological restrictions. The MAP problem is also discussed for other graph representations, and it is shown that the proof presented in this paper can be used to improve the results stated by [\textit{G. F. Cooper} [Artif. Intell. 42, No. 2/3, 393-405 (1990; Zbl 0717.68080)].
- A linear constraint satisfaction approach to cost-based abduction
- Approximating probabilistic inference in Bayesian belief networks is NP- hard
- Finding MAPs for belief networks is NP-hard
- scientific article; zbMATH DE number 19872 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 4121482 (Why is no real title available?)
- Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
- The computational complexity of probabilistic inference using Bayesian belief networks
- Exploiting case-based independence for approximating marginal probabilities
- Approximating MAPs for belief networks is NP-hard and other theorems
- Finding MAPs for belief networks is NP-hard
- Implicitly preserving semantics during incremental knowledge base acquisition under uncertainty.
- The complexity of approximating MAPs for belief networks with bounded probabilities
- Evaluation of Bayesian networks with flexible state-space abstraction methods
- Rational analysis, intractability, and the prospects of `as if'-explanations
- Conditional random fields for pattern recognition applied to structured data
- The role of relevance in explanation. II: Disjunctive assignments and approximate independence
- Hybrid algorithms for approximate belief updating in Bayes nets
- Complexity results for structure-based causality.
- Cost-based temporal reasoning
- Variable neighborhood search for graphical model energy minimization
- Energy distribution view for monotonic dual decomposition
- The Bayesian ontology language \(\mathcal {BEL}\)
- Understanding the role of noise in stochastic local search: analysis and experiments
- Portfolios in stochastic local search: efficiently computing most probable explanations in Bayesian networks
- A computational-level explanation of the speed of goal inference
- A review on evolutionary algorithms in Bayesian network learning and inference tasks
- Controlled generation of hard and easy Bayesian networks: Impact on maximal clique size in tree clustering
- Coherence measures and inference to the best explanation
- Most frugal explanations in Bayesian networks
- Finding the maximum a posteriori probability (MAP) in a Bayesian taxonomic key is NP-hard
- The computational complexity of probabilistic inference using Bayesian belief networks
- On some properties of the low-dimensional Gumbel perturbations in the perturb-and-MAP model
- The complexity of finding \(k\)th most probable explanations in probabilistic networks
- Cycle-based cluster variational method for direct and inverse inference
- DIRECTING GENETIC ALGORITHMS FOR PROBABILISTIC REASONING THROUGH REINFORCEMENT LEARNING
- Multi-classifiers of small treewidth
- Use of explanation trees to describe the state space of a probabilistic-based abduction problem
- scientific article; zbMATH DE number 19872 (Why is no real title available?)
- scientific article; zbMATH DE number 124280 (Why is no real title available?)
- Most probable explanations in Bayesian networks: complexity and tractability
- A framework for building knowledge-bases under uncertainty
- scientific article; zbMATH DE number 1983173 (Why is no real title available?)
- Train and test tightness of LP relaxations in structured prediction
- Hinge-loss Markov random fields and probabilistic soft logic
- Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing
- scientific article; zbMATH DE number 2243356 (Why is no real title available?)
- An algorithm for finding MAPs for belief networks through cost-based abduction
- Bayesian model-based diagnosis
- Monitoring of perception systems: deterministic, probabilistic, and learning-based fault detection and identification
- On Imperfect Recall in Multi-Agent Influence Diagrams
- Multi-dimensional classification with Bayesian networks
- Maximum a posteriori inference for factor graphs via Benders' decomposition
- Theoretical foundations for parent divorcing transformations in Bayesian networks
- Complexity of probabilistic reasoning in directed-path singly-connected Bayes networks
- Complexity results for explanations in the structural-model approach
- Approximating cost-based abduction is NP-hard
- Approximate belief updating in max-2-connected Bayes networks is NP-hard
- Understanding the scalability of Bayesian network inference using clique tree growth curves
This page was built for publication: Finding MAPs for belief networks is NP-hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1332845)
