An optimal approximation algorithm for Bayesian inference

DOI10.1016/S0004-3702(97)00013-1MaRDI QIDQ1402716zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Paul Dagum, Michael Luby

Publication date 28 August 2003

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0004-3702(97)00013-1

zbMATH Keywords

Bayesian inferenceApproximationBelief networks

Mathematics Subject Classification ID

Bayesian inference (62F15) Knowledge representation (68T30)

Recommendations

• Approximating probabilistic inference in Bayesian belief networks is NP- hard
• A Bayesian analysis of simulation algorithms for inference in belief networks
• The complexity of approximating MAPs for belief networks with bounded probabilities
• Modeling and Reasoning with Bayesian Networks
• A randomized approximation algorithm for probabilistic inference on bayesian belief networks

Cites work

• scientific article; zbMATH DE number 4178809 (Why is no real title available?)
• scientific article; zbMATH DE number 4060768 (Why is no real title available?)
• scientific article; zbMATH DE number 19872 (Why is no real title available?)
• scientific article; zbMATH DE number 1261816 (Why is no real title available?)
• scientific article; zbMATH DE number 4121482 (Why is no real title available?)
• scientific article; zbMATH DE number 4189218 (Why is no real title available?)
• scientific article; zbMATH DE number 4189220 (Why is no real title available?)
• scientific article; zbMATH DE number 4189232 (Why is no real title available?)
• A Bayesian analysis of simulation algorithms for inference in 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
• Approximating probabilistic inference in Bayesian belief networks is NP- hard
• Evidential reasoning using stochastic simulation of causal models
• Monte-Carlo approximation algorithms for enumeration problems
• Pseudorandom bits for constant depth circuits
• The computational complexity of probabilistic inference using Bayesian belief networks

Cited in

(39)

• Recursive conditioning
• scientific article; zbMATH DE number 1424387 (Why is no real title available?)
• scientific article; zbMATH DE number 1467487 (Why is no real title available?)
• Importance sampling in Bayesian networks using probability trees.
• The complexity of approximating MAPs for belief networks with bounded probabilities
• Reasoning with BKBs -- algorithms and complexity
• scientific article; zbMATH DE number 19874 (Why is no real title available?)
• Relax, compensate and then recover: a theory of anytime, approximate inference
• Approximating global optimum for probabilistic truth discovery
• Bounding probabilistic relationships in Bayesian networks using qualitative influences: methods and applications
• The necessity of bounded treewidth for efficient inference in Bayesian networks
• scientific article; zbMATH DE number 1983173 (Why is no real title available?)
• A sufficiently fast algorithm for finding close to optimal clique trees
• Quantifying the uncertainty of a belief net response: Bayesian error-bars for belief net inference
• Anytime anyspace probabilistic inference
• Approximating probabilistic inference in Bayesian belief networks is NP- hard
• scientific article; zbMATH DE number 2096817 (Why is no real title available?)
• Evaluation of Bayesian networks with flexible state-space abstraction methods
• Inverse sampling for nonasymptotic sequential estimation of bounded variable means
• Approximate Bayesian Inference by Adaptive Quantization of the Hypothesis Space
• Dynamic importance sampling in Bayesian networks based on probability trees
• Optimal polynomial-time estimators: a Bayesian notion of approximation algorithm
• Ordered valuation algebras: A generic framework for approximating inference
• A Bayesian analysis of simulation algorithms for inference in belief networks
• Exact and efficient inference for partial Bayes problems
• Divergence measures and approximate algorithms for valuation based systems
• Bayes networks for estimating the number of solutions of constraint networks
• Approximate inference in Bayesian networks: parameterized complexity results
• A Simple Proof for the Optimality of Randomized Posterior Matching
• Probabilistic inference in multiply connected belief networks using loop cutsets
• Approximations of Bayes decision problems: The epigraphical approach
• Mini-buckets: a general scheme for bounded inference
• Computing the execution probability of jobs with replication in mixed-criticality schedules
• Lazy evaluation in penniless propagation over join trees
• Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu
• A randomized approximation algorithm for probabilistic inference on bayesian belief networks
• scientific article; zbMATH DE number 4189218 (Why is no real title available?)
• Barker's algorithm for Bayesian inference with intractable likelihoods
• Approximate Bayesian inference for simulation and optimization

Describes a project that uses

Uses Software

• NESTOR

This page was built for publication: An optimal approximation algorithm for Bayesian inference

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