Approximating Probabilistic Inference in Bayesian Belief Networks is NP-Hard

By P. Dagum, Michael Luby. 1993

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

Generalization in anti-causal learning (2018, neutral): “…probabilistic inference and ﬁnding maximum a posteriori probabilities in Bayesian belief networks or learning large-scale discrete Bayesian networks are all NP-hard (Dagum and Luby, 1993; Shimony, 1994; Chickering et al., 2004), consistent with our interpretation (see “NP problems” in section 3).”
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.”
Discrete Variational Autoencoders (2016, background): “2 However, sampling from undirected graphical models is generally intractable [14], as is sampling from the posterior of a directed graphical model conditioned on its leaf variables [15].”
An Introduction to Variational Methods for Graphical Models (1999, methodology): “A variety of Monte Carlo algorithms have been developed (see Neal, 1993) and applied to the inference problem in graphical models (Dagum & Luby, 1993; Fung & Favero, 1994; Gilks, Thomas, & Spiegelhalter, 1994; Jensen, Kong, & Kjaerulff, 1995; Pearl, 1988).”
Computing upper and lower bounds on likelihoods in intractable networks (1996, background): “Although theproblem of nding con dence intervals to a predescribedaccuracy is NP-hard (Dagum and Luby, 1993), boundsthat can be computed e ciently may nevertheless yieldcon dence intervals that are accurate enough to be use-ful in practice.”
How bad is incoherence (2016, background): “Checking for consistency within these networks is NP-hard (Cooper, 1990), as are approximations (Dagum & Luby, 1993).”
Why Heuristics Work (2008, background): “Dawes’s seminal work (1979) showed that the tallying heuristic (which does not pay attention to weights) can match and outperform multiple regression in prediction.”
Reinforcement learning for factored Markov decision processes (2002, background): “the problem of approximate inference within a given accuracy are known to be NP-hard [Shimony 1994; Dagum and Luby 1993].”
Learning Bayesian networks: approaches and issues (2011, background): “Dasgupta (1999) gives a good look at the field and mentions the NP-hardness of the problem, while showing a good approximation and de Campos (1998) looks at what properties a dependency model must have in order to be represented by a polytree.”