Approximating probabilistic inference in Bayesian belief networks is NP-hard

1993/03/01 by Paul Dagum, Michael Luby · 31 citations
Computer Science · #Bayesian Modeling and Causal Inference #Machine Learning and Algorithms #AI-based Problem Solving and Planning

paper · doi:10.1016/0004-3702(93)90036-b

Cited by

• Generative Model for Heterogeneous Inference
• Exact MAP inference in general higher-order graphical models using linear programming
• Correlated Equilibria for Approximate Variational Inference in MRFs
• On the Detection of Commutative Factors in Factor Graphs: Necessary and Sufficient Conditions
• Generalization in anti-causal learning
• Plausibility and probability in deductive reasoning
• Bayesian Intractability Is Not an Ailment That Approximation Can Cure
• On the Complexity of Solving Markov Decision Problems
• Determinantal Point Processes for Machine Learning
• Efficient Search-Based Inference for Noisy-OR Belief Networks:\n TopEpsilon
• Approximating MAP using Local Search
• DODO: Causal Structure Learning with Budgeted Interventions
• FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation
• Belief Updating by Enumerating High-Probability Independence-Based\n Assignments
• Mathematical Programs for Belief Propagation and Consensus
• Iterative Join-Graph Propagation
• State-space Abstraction for Anytime Evaluation of Probabilistic Networks
• Loopy Belief Propagation for Approximate Inference: An Empirical Study
• A high-performance analog Max-SAT solver and its application to Ramsey numbers
• Bayesian networks in neuroscience: a survey. [europepmc]
• A Factor Graph Approach to Automated GO Annotation. [europepmc]
• The blessing of Dimensionality: Feature Selection outperforms functional connectivity-based feature transformation to classify ADHD subjects from EEG patterns of phase synchronisation. [europepmc]
• Biological plausibility and stochasticity in scalable VO 2 active memristor neurons. [europepmc]
• A continuous-time MaxSAT solver with high analog performance. [europepmc]
• Uncertainty and computational complexity. [europepmc]
• Polynomial-Time Algorithm for Learning Optimal BFS-Consistent Dynamic Bayesian Networks. [europepmc]
• Structure Learning of Bayesian Network Based on Adaptive Thresholding. [europepmc]
• Universal Target Learning: An Efficient and Effective Technique for Semi-Naive Bayesian Learning. [europepmc]
• Dynamic Bayesian Networks for Integrating Multi-omics Time Series Microbiome Data. [europepmc]
• Gated recurrence enables simple and accurate sequence prediction in stochastic, changing, and structured environments. [europepmc]
• Does supply chain matter for environmental firm performance: mediating role of financial development in China [europepmc]