Approximating probabilistic inference in Bayesian belief networks is NP- hard

DOI10.1016/0004-3702(93)90036-BzbMATH Open0781.68105DBLPjournals/ai/DagumL93OpenAlexW1999432334WikidataQ56158129 ScholiaQ56158129MaRDI QIDQ685336FDOQ685336

Authors: 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

Recommendations

• An optimal approximation algorithm for Bayesian inference
• The computational complexity of probabilistic inference using Bayesian belief networks
• Approximating MAPs for belief networks is NP-hard and other theorems
• The complexity of approximating MAPs for belief networks with bounded probabilities
• Approximate belief updating in max-2-connected Bayes networks is NP-hard

zbMATH Keywords

NP-completeupper boundconditional probabilitiesbelief networks

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Evidential reasoning using stochastic simulation of causal models
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• The computational complexity of probabilistic inference using Bayesian belief networks
• A randomized approximation algorithm for probabilistic inference on bayesian belief networks
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (67)

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

Uses Software

• NESTOR

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685336)