2013/03/27 by R. Martin Chavez, Chavez, R. Martin, Gregory F. Cooper +1
Computer Science · Decision Sciences · #AI-based Problem Solving and Planning #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Data Quality and Management #Explainable Artificial Intelligence (XAI) #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1304.1498
openalex publication_date 2013/03/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In recent years, researchers in decision analysis and artificial intelligence\n(Al) have used Bayesian belief networks to build models of expert opinion.\nUsing standard methods drawn from the theory of computational complexity,\nworkers in the field have shown that the problem of probabilistic inference in\nbelief networks is difficult and almost certainly intractable. K N ET, a\nsoftware environment for constructing knowledge-based systems within the\naxiomatic framework of decision theory, contains a randomized approximation\nscheme for probabilistic inference. The algorithm can, in many circumstances,\nperform efficient approximate inference in large and richly interconnected\nmodels of medical diagnosis. Unlike previously described stochastic algorithms\nfor probabilistic inference, the randomized approximation scheme computes a\npriori bounds on running time by analyzing the structure and contents of the\nbelief network. In this article, we describe a randomized algorithm for\nprobabilistic inference and analyze its performance mathematically. Then, we\ndevote the major portion of the paper to a discussion of the algorithm's\nempirical behavior. The results indicate that the generation of good trials\n(that is, trials whose distribution closely matches the true distribution),\nrather than the computation of numerous mediocre trials, dominates the\nperformance of stochastic simulation. Key words: probabilistic inference,\nbelief networks, stochastic simulation, computational complexity theory,\nrandomized algorithms.\n