Finding MAPs for Belief Networks is NP-Hard

By Solomon Eyal Shimony. 1994

Subfields: Probabilistic & Bayesian Methods

How researchers see this paper

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

In Probabilistic & Bayesian Methods

Citations in the corpus

Barrier Frank-Wolfe for Marginal Inference (2015, background): “Although MAP inference is in general NP hard (Shimony, 1994), it is often possible to find exact solutions to large real-world instances within reasonable running times (Sontag et al., 2008; Allouche et al., 2010; Kappes et al., 2013).”
Generalization in anti-causal learning (2018, positive): “…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): “Shimony [130] proved that the MAP inference problem (finding the mode of an MRF) is also NP-hard, and Abdelbar and Hedetniemi [1] showed that the MAP problem is likewise hard to approximate.”
Linear Programming Relaxations and Belief Propagation - An Empirical Study (2006, background): “For an arbitrary graph, this problem is known to be NP hard (Shimony, 1994) and various approximation lgorithms have been proposed [see. e.g (Marinescu et al., 2003) for a recent review].”
Distributed message passing for large scale graphical models (2011, methodology): “This integer linear program is equivalent to the MAP problem in (2), and is hence NP-hard [24].”
Turbo Decoding as an Instance of Pearl's "Belief Propagation" Algorithm (1998, background): “(See also [17] and [53] for more on the NP hardness of probabilistic inference in Bayesian networks.)”
Three Modern Roles for Logic in AI (2020, background): “The decision problem D-MPE is complete for the class NP [86].”
Bayesian Artificial Intelligence (2004, background): “NP hard [254], and more recently NP complete [213]; approximating MAPs is also NP hard [1].”
On the Partition Function and Random Maximum A-Posteriori Perturbations (2012, background): “Although the MAP problem is NP-hard in general (Shimony, 1994), it is easier than computing the partition function.”
An Unsupervised Model for Instance Level Subcategorization Acquisition (2014, background): “For most reasonable values of p+ and p− our graph still contains cycles even after it is pruned, which makes inference NP-hard (Shimony, 1994).”
Structured Attentions for Visual Question Answering (2017, background): “The inference problem in such a gird-structured factor graph, which aims to calculate the marginal probability p ( z i | X , q ; θ ) , is known to be NP-hard [32].”
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].”
Complexity results for structure-based causality (2001, background): “Only weaklyrelatedis work on thecomplexity of maximuma posterioriexplanations(MAPs) in Bayesiannetworks [34], which areassignmentsto all variablesextendinggivenpartialassignmentsuchthat theprobability is maximum.”
Structured Learning and Prediction in Computer Vision (2011, background): “Both inference problems are known to be NP-hard for general graphs and factors [Shimony, 1994] but can be tractable if suitably restricted.”
Slice-to-volume medical image registration: a survey (2017, unknown): “Discrete optimization of MRFs is, in general, an NP-hard problem (Shimony, 1994).”