Approximating probabilistic inference in Bayesian belief networks is NP- hard

DOI10.1016/0004-3702(93)90036-BzbMath0781.68105OpenAlexW1999432334WikidataQ56158129 ScholiaQ56158129MaRDI QIDQ685336

Paul Dagum, Michael Luby

Publication date: 17 February 1994

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0004-3702(93)90036-b

zbMATH Keywords

upper boundNP-completeconditional probabilitiesbelief networks

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Knowledge representation (68T30)

Related Items (60)

FAST FACTORISATION OF PROBABILISTIC POTENTIALS AND ITS APPLICATION TO APPROXIMATE INFERENCE IN BAYESIAN NETWORKS ⋮ Finding MAPs for belief networks is NP-hard ⋮ Efficient approximation of the conditional relative entropy with applications to discriminative learning of Bayesian network classifiers ⋮ Analysing risks in supply networks to facilitate outsourcing decisions ⋮ Diagnosis under compound effects and multiple causes by means of the conditional causal possibility approach ⋮ Efficient learning of Bayesian networks with bounded tree-width ⋮ Approximate belief updating in max-2-connected Bayes networks is NP-hard ⋮ Troubleshooting using probabilistic networks and value of information ⋮ DISTRIBUTED INFERENCE IN BAYESIAN NETWORKS ⋮ Importance sampling algorithms for the propagation of probabilities in belief networks ⋮ Exploiting case-based independence for approximating marginal probabilities ⋮ A modified simulation scheme for inference in Bayesian networks ⋮ Automatic emergence detection in complex systems ⋮ On the hardness of approximate reasoning ⋮ Probabilistic conflicts in a search algorithm for estimating posterior probabilities in Bayesian networks ⋮ Accelerating a continuous-time analog SAT solver using GPUs ⋮ Local conditioning in Bayesian networks ⋮ A scalable pairwise class interaction framework for multidimensional classification ⋮ Fuzzy functional dependencies and Bayesian networks ⋮ Implicitly preserving semantics during incremental knowledge base acquisition under uncertainty. ⋮ Interval-based reasoning over continuous variables using independent component analysis and Bayesian networks ⋮ An optimal approximation algorithm for Bayesian inference ⋮ Semantics and complexity of abduction from default theories ⋮ Incremental Junction Tree Inference ⋮ Axiomatic rationality and ecological rationality ⋮ Rational analysis, intractability, and the prospects of `as if'-explanations ⋮ Improved High Dimensional Discrete Bayesian Network Inference using Triplet Region Construction ⋮ Approximate inference in Bayesian networks: parameterized complexity results ⋮ On the complexity of inference about probabilistic relational models ⋮ Theoretical analysis and practical insights on importance sampling in Bayesian networks ⋮ A comparison of hybrid strategies for Gibbs sampling in mixed graphical models ⋮ A Tutorial on Learning with Bayesian Networks ⋮ Adaptive Cascade ⋮ Importance sampling algorithms for Bayesian networks: principles and performance ⋮ Dynamic importance sampling in Bayesian networks based on probability trees ⋮ Iterative state-space reduction for flexible computation ⋮ Principles and applications of continual computation ⋮ Anytime anyspace probabilistic inference ⋮ A general scheme for automatic generation of search heuristics from specification \(dependencies^{*}\) ⋮ Bounding probabilistic relationships in Bayesian networks using qualitative influences: methods and applications ⋮ MB-GNG: Addressing drawbacks in multi-objective optimization estimation of distribution algorithms ⋮ A framework for building knowledge-bases under uncertainty ⋮ Arc refractor methods for adaptive importance sampling on large Bayesian networks under evidential reasoning ⋮ A decision support system for vine growers based on a Bayesian network ⋮ Bounded recursive decomposition: A search-based method for belief-network inference under limited resources ⋮ Hybrid algorithms for approximate belief updating in Bayes nets ⋮ A compositional approach to probabilistic knowledge compilation ⋮ A Monte Carlo algorithm for probabilistic propagation in belief networks based on importance sampling and stratified simulation techniques ⋮ Approximating MAPs for belief networks is NP-hard and other theorems ⋮ Moment-based analysis of Bayesian network properties ⋮ Model-Based Diagnosis with Probabilistic Models ⋮ Learning tractable Bayesian networks in the space of elimination orders ⋮ Estimating the probability of meeting a deadline in schedules and plans ⋮ Importance sampling in Bayesian networks using probability trees. ⋮ The complexity of approximating MAPs for belief networks with bounded probabilities ⋮ Evaluation of Bayesian networks with flexible state-space abstraction methods ⋮ Recoverability from direct quantum correlations ⋮ Unnamed Item ⋮ Possibilistic causality consistency problem based on asymmetrically-valued causal model ⋮ Complexity of probabilistic reasoning in directed-path singly-connected Bayes networks

Uses Software

• NESTOR

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• Evidential reasoning using stochastic simulation of causal models
• The computational complexity of probabilistic inference using Bayesian belief networks
• A Probabilistic Causal Model for Diagnostic Problem Solving Part I: Integrating Symbolic Causal Inference with Numeric Probabilistic Inference
• A Probabilistic Causal Model for Diagnostic Problem Solving Part II: Diagnostic Strategy
• A randomized approximation algorithm for probabilistic inference on bayesian belief networks

This page was built for publication: Approximating probabilistic inference in Bayesian belief networks is NP- hard