Approximating Probabilistic Inference in Bayesian Belief Networks is NP-Hard

No abstract is available for this paper.

• Publication year

  1993

• Venue

  Artificial Intelligence

• Publication date

  1993-03-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0004-3702(93)90036-B
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Weighing and Integrating Evidence for Stochastic Simulation in Bayesian Networks

  2013cited by this paper
• Simulation Approaches to General Probabilistic Inference on Belief Networks

  2013cited by this paper
• A Tractable Inference Algorithm for Diagnosing Multiple Diseases

  2013cited by this paper
• Approximating Probabilistic Inference in Bayesian Belief Networks

  1993cited by this paper
• The history and status of the P versus NP question

  1992cited by this paper
• Reformulating Inference Problems Through Selective Conditioning

  1992cited by this paper
• A random polynomial-time algorithm for approximating the volume of convex bodies

  1991cited by this paper
• An Empirical Analysis of Likelihood-Weighting Simulation on a Large, Multiply-Connected Belief Network

  1991cited by this paper
• Search-Based Methods to Bound Diagnostic Probabilities in Very Large Belief Nets

  1991cited by this paper
• A randomized approximation algorithm for probabilistic inference on bayesian belief networks

  1990cited by this paper
• Architectures and approximation algorithms for probabilistic expert systems

  1990cited by this paper
• The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks

  1990cited by this paper
• Reflection and Action Under Scarce Resources: Theoretical Principles and Empirical Study

  1989cited by this paper
• A random polynomial time algorithm for approximating the volume of convex bodies

  1989cited by this paper
• Evidential Reasoning Using Stochastic Simulation of Causal Models

  1987cited by this paper
• A Probabilistic Causal Model for Diagnostic Problem Solving Part I: Integrating Symbolic Causal Inference with Numeric Probabilistic Inference

  1987cited by this paper
• A Probabilistic Causal Model for Diagnostic Problem Solving Part II: Diagnostic Strategy

  1987cited by this paper
• Bayesian Belief Network Inference Using Simulation

  1987cited by this paper
• Propagating uncertainty in bayesian networks by probabilistic logic sampling

  1986cited by this paper
• NESTOR: A Computer-Based Medical Diagnostic Aid That Integrates Causal and Probabilistic Knowledge.

  1984cited by this paper
• Monte-Carlo algorithms for enumeration and reliability problems

  1983cited by this paper
• Two theorems on random polynomial time

  1978cited by this paper

• Deep probabilistic circuits for efficient uncertainty handling in learning systems

  2026cites this paper
• Polynomial-Time Relational Probabilistic Inference in Open Universes

  2025cites this paper
• Off-switching not guaranteed

  2025cites this paper
• Speedup Chip Yield Analysis by Improved Quantum Bayesian Inference

  2025cites this paper
• On the Hardness of Approximating Distributions with Tractable Probabilistic Models

  2025influential citation
• AI on Small and Noisy Data is Ineffective for ICS Cyber Risk Management

  2025cites this paper
• DODO: Causal Structure Learning with Budgeted Interventions

  2025cites this paper
• Quantum Testing of Recommender Algorithms on GPU-Based Quantum Simulators

  2025cites this paper
• On the Hardness of Approximating Distributions with Probabilistic Circuits

  2025influential citation
• Probabilistic and Causal Satisfiability: Constraining the Model

  2025cites this paper
• Maximizing Truth Learning in a Social Network is NP-hard

  2025cites this paper
• Quantum inference for Bayesian networks: an empirical study

  2025cites this paper
• Local Gibbs sampling beyond local uniformity

  2025cites this paper
• Spectral Graph Compression in Deploying Recommender Algorithms on Quantum Simulators

  2025cites this paper
• Theoretical Analysis and Verification of Loop Cutsets in Bayesian Network Inference

  2025cites this paper
• Dynamic Detection and Debias of Bayesian Network Classifier (3D-BN)

  2025cites this paper
• Branch-and-bound method for calculating Viterbi path in triplet Markov models

  2025cites this paper
• A framework for the practical development of condition monitoring systems with application to the roller compactor

  2024cites this paper
• Probabilistic and Causal Satisfiability: the Impact of Marginalization

  2024cites this paper
• Artificial enactive inference in three-dimensional world

  2024cites this paper
• A Pair of Bayesian Network Structures has Undecidable Conditional Independencies

  2024cites this paper
• Fast-PGM: Fast Probabilistic Graphical Model Learning and Inference

  2024cites this paper
• Faster-BNI: Fast Parallel Exact Inference on Bayesian Networks

  2024cites this paper
• Guaranteed Bounds on Posterior Distributions of Discrete Probabilistic Programs with Loops

  2024cites this paper
• Urban transportation system long-term resilience assessment using multi-dimensional dynamic Bayesian network

  2024cites this paper
• Inquiry Under Bounds

  2024cites this paper
• Learning Reliable PDDL Models for Classical Planning from Visual Data

  2024cites this paper
• Limitations of the propensity scores approach: A simulation study

  2024cites this paper
• Flexible model weighting for one-dependence estimators based on point-wise independence analysis

  2023cites this paper
• Gibbs sampling the posterior of neural networks

  2023cites this paper
• Provable convergence guarantees for black-box variational inference

  2023cites this paper
• Scaling Probabilistic Inference Through Message Contraction Optimization

  2023cites this paper
• Joint Location Sensing and Channel Estimation for IRS-Aided mmWave ISAC Systems

  2023cites this paper
• Automatically Finding the Right Probabilities in Bayesian Networks

  2023cites this paper
• Exploring Regional Innovation Dynamics Using Directed Acyclic Graphs

  2023cites this paper
• Interval-based reasoning over continuous variables using independent component analysis and Bayesian networks

  2023cites this paper
• Understanding the Behavior of Belief Propagation

  2022cites this paper
• Why Reasoning Under Uncertainty Is Hard for Both Machines and People—and an Approach to Address the Problem

  2022cites this paper
• Mappings for Marginal Probabilities with Applications to Models in Statistical Physics

  2022cites this paper
• Amortized Variational Inference: A Systematic Review

  2022cites this paper
• Explainable Machine Learning for Longitudinal Multi-Omic Microbiome

  2022cites this paper
• A scalable algorithm for network reachability analysis with cyclic attack graphs

  2022cites this paper
• Master Thesis Proposal Exact Inference for Probabilistic Loops

  2022cites this paper
• Does supply chain matter for environmental firm performance: mediating role of financial development in China

  2022cites this paper
• A novel discrete firefly algorithm for Bayesian network structure learning

  2022cites this paper
• Amortized Variational Inference: Towards the Mathematical Foundation and Review

  2022cites this paper
• A Swarm Intelligence Based Community Detection Algorithm in Social Networks

  2022cites this paper
• Attack graph analysis: An explanatory guide

  2022cites this paper
• Matrix factorization based Bayesian network embedding for efficient probabilistic inferences

  2021cites this paper
• An Introduction to Variational Inference

  2021cites this paper
• Query Strategies for Directed Graphical Models and their Application to Adaptive Testing

  2021influential citation
• Hierarchical Independence Thresholding for learning Bayesian network classifiers

  2021cites this paper
• Self-Organized Polynomial-Time Coordination Graphs

  2021influential citation
• An Expert System Prototype for the Early Diagnosis of Pneumonia

  2021cites this paper
• An efficient approach for multiple probabilistic inferences with Deepwalk based Bayesian network embedding

  2021cites this paper
• Improving Bayesian inference efficiency for sensory anomaly detection and recovery in mobile robots

  2021cites this paper
• Multi-rate Gaussian Bayesian network soft sensor development with noisy input and missing data

  2021cites this paper
• Probabilistic analysis in DC grids

  2021cites this paper
• Good Guesses

  2021cites this paper
• Bayesian networks for interpretable machine learning and optimization

  2021cites this paper
• On the Convex Combination of Determinantal Point Processes

  2021cites this paper
• Scalable k-out-of-n models for dependability analysis with Bayesian networks

  2021cites this paper
• Gated recurrence enables simple and accurate sequence prediction in stochastic, changing, and structured environments

  2021cites this paper
• Enhancing Generative Models via Quantum Correlations

  2021cites this paper
• Inference and reasoning in a Bayesian knowledge-intensive CBR system

  2021cites this paper
• Using Bayesian networks to estimate bridge characteristics in early road designs

  2021cites this paper
• Multipartition clustering of mixed data with Bayesian networks

  2021cites this paper
• Variational inference with a quantum computer

  2021cites this paper
• Background

  2021cites this paper
• Post-Quantum Cryptosystems for Internet-of-Things: A Survey on Lattice-Based Algorithms

  2021cites this paper
• Error-Correcting and Verifiable Parallel Inference in Graphical Models

  2020cites this paper
• Bayesian attack graphs for platform virtualized infrastructures in clouds

  2020cites this paper
• Relaxed Scheduling for Scalable Belief Propagation

  2020cites this paper
• Machine Learning and Data Analytics for Design and Manufacturing of High-Entropy Materials Exhibiting Mechanical or Fatigue Properties of Interest

  2020cites this paper
• BayeSuites: An open web framework for massive Bayesian networks focused on neuroscience

  2020influential citation
• Discovery of Learning Path Based on Bayesian Network Association Rule Algorithm

  2020cites this paper
• Expected Runtime Analysis by Program Verification

  2020cites this paper
• Development of Clinical Decision Support Systems using Bayesian Networks: With an example of a Multi-Disciplinary Treatment Decision for Laryngeal Cancer

  2020cites this paper
• Directed probabilistic graphical models

  2020cites this paper
• An examination of firm size on intra-family business succession

  2020cites this paper
• On the Use of Bayesian Network in Crime Suspect Modelling and Legal Decision Support

  2020cites this paper
• Probabilistic logging lithology characterization with random forest probability estimation

  2020cites this paper
• Uncertain inference network in evidential reasoning

  2020cites this paper
• Automated reasoning and randomization in separation logic

  2020cites this paper
• Widened Machine Learning with Application to Bayesian Networks

  2020cites this paper
• Exact Symbolic Inference in Probabilistic Programs via Sum-Product Representations

  2020cites this paper
• Improved High Dimensional Discrete Bayesian Network Inference using Triplet Region Construction

  2020cites this paper
• FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation

  2020cites this paper
• Accelerating a continuous-time analog SAT solver using GPUs

  2020cites this paper
• Quantitative Evaluation of Systems: 17th International Conference, QEST 2020, Vienna, Austria, August 31 – September 3, 2020, Proceedings

  2020cites this paper
• Probabilistic Graphical Models: Part I

  2020cites this paper
• Optimizing Inference in Bayesian Networks: From Join Tree Propagation to Deep Learning

  2020cites this paper
• On the Complexity of Finding the Maximum Entropy Compatible Quantum State

  2020cites this paper
• Analysis of Bayesian Networks via Prob-Solvable Loops

  2020cites this paper
• Political Skill Improves the Effectiveness of Emotional Intelligence: Bayesian Network Analysis in the Construction Industry

  2020cites this paper
• Learning Non-Impeding Noisy-AND Tree Model Based Bayesian Networks From Data

  2020cites this paper
• SPPL: probabilistic programming with fast exact symbolic inference

  2020cites this paper
• Reliability Evaluation of a Disaster Airflow Emergency Control System Based on Bayesian Networks

  2020cites this paper
• Bayesian Inference by Symbolic Model Checking

  2020cites this paper
• Experimental Evaluation of Three Value Recommendation Methods in Interactive Configuration

  2020cites this paper