Optimal Monte Carlo Estimation of Belief Network Inference

2013/02/13 by Malcolm Pradhan, Paul Dagum, Pradhan, Malcolm +1
Computer Science · #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #Machine Learning and Algorithms #cs.AI

paper · pdf · doi:10.48550/arxiv.1302.3598

Appears in Proceedings of the Twelfth Conference on Uncertainty in Artificial Intelligence (UAI1996)

arxiv created 2013/02/13 · openalex publication_date 2013/02/13 · arxiv updated 2013/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present two Monte Carlo sampling algorithms for probabilistic inference that guarantee polynomial-time convergence for a larger class of network than current sampling algorithms provide. These new methods are variants of the known likelihood weighting algorithm. We use of recent advances in the theory of optimal stopping rules for Monte Carlo simulation to obtain an inference approximation with relative error epsilon and a small failure probability delta. We present an empirical evaluation of the algorithms which demonstrates their improved performance.

Citations

• Approximating probabilistic inference in Bayesian belief networks is NP-hard

Related

• Simulation Approaches to General Probabilistic Inference on Belief Networks
• A Randomized Approximation Algorithm of Logic Sampling
• An Implementation of a Method for Computing the Uncertainty in Inferred Probabilities in Belief Networks
• Stochastic Simulation of Bayesian Belief Networks
• A Stratified Simulation Scheme for Inference in Bayesian Belief Networks