The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks

By Gregory F. Cooper. 1990

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Determinantal Point Processes for Machine Learning (2012, background): “Cooper [30] showed that general probabilistic inference (conditioning and marginalization) in MRFs is NPhard, and this was later extended by Dagum and Luby [31], who showed that inference is NP-hard even to approximate.”
Mean Field Theory for Sigmoid Belief Networks (1996, background): “The problem of computing exact likelihoods in belief networks is NP-hard (Cooper, 1990); the same is true for approximating likelihoods to within a guaranteed degree of accuracy (Dagum & Luby, 1993).”
Loopy Belief Propagation for Approximate Inference: An Empirical Study (1999, background): “1 Introduction The task of calculating posterior marginals on nodes in an arbitrary Bayesian network is known to be NPhard [5].”
Bayesian Networks for Data Mining (2004, methodology): “Although we use conditional independence to simplify probabilistic inference, exact inference in an arbitrary Bayesian network for discrete variables is NP-hard (Cooper, 1990).”
Accuracy vs. efficiency trade-offs in probabilistic diagnosis (2002, methodology): “This approach is sometimes criticized as being too complex and computationally intractable; note, however, that updating the probability of a single node is also an NPhard problem (Cooper 1990) that can be (in the worst case) as time consuming as finding an MPE.”
Finding MAPs for Belief Networks is NP-Hard (1994, methodology): “AND or OR) nodes and follower nodes should also apply to the reduction of [2], thus extending the NP-hardness results for the probabilistic inference and for the approximation of probabilistic inference [3] problems to maximum in-degree and out-degree of 2.”
Graph based anomaly detection and description: a survey (2014, methodology): “All these algorithms are fast, iterative, approximate inference algorithms, since exact inference is known to be NP-hard in arbitrary networks (Cooper 1990).”
Bayesian Artificial Intelligence (2004, background): “Cooper [52] showed that the general problem of inference in belief networks is NP hard, while Dagum and Luby [64] showed the problem of approximating the new beliefs to within an arbitrary tolerance is also NP hard.”
Bayesian Networks (2008, unknown): “In particular, the decision version of MPE, PR, and MAP, are known to be NP-complete, PP-complete and NP PP -complete, respectively [32] [158] [145] [123].”
Turbo Decoding as an Instance of Pearl's "Belief Propagation" Algorithm (1998, unknown): “The efficiency of belief propagation on trees stands in sharp contrast to the situation for general DAG's since, in 1990, Cooper [16] showed that the inference problem in general DAG's is NP hard.”
How bad is incoherence (2016, background): “Checking for consistency within these networks is NP-hard (Cooper, 1990), as are approximations (Dagum & Luby, 1993).”
A new look at survey propagation and its generalizations (2004, background): “Of course, exact marginalization is computationally intractable in general [10, 12], which motivates the use of efficient algorithms for approximate marginalization.”
LOGARITHMIC MARKETS CORING RULES FOR MODULAR COMBINATORIAL INFORMATION AGGREGATION (2012, background): “The computational complexity of such updates can be large, being worse than polynomial in the worst case (i.e., is NP-complete) (Cooper, 1990).”
Nonparametric belief propagation (2003, background): “Although exact inference in general discrete graphs is NP hard [7], approximate inference algorithms such as loopy belief propagation (BP) [1, 8, 9] have been shown to produce good results for a wide range of interesting models [2, 5].”