Premium
A Bayesian analysis of simulation algorithms for inference in belief networks
Author(s) -
Dagum Paul,
Horvitz Eric
Publication year - 1993
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230230506
Subject(s) - bayesian network , inference , algorithm , computer science , posterior probability , probabilistic logic , bayesian inference , representation (politics) , bayesian probability , weighting , probability distribution , randomized algorithm , mathematics , artificial intelligence , statistics , law , radiology , medicine , politics , political science
A belief network is a graphical representation of the underlying probabilistic relationships in a complex system. Belief networks have been employed as a representation of uncertain relationships in computer‐based diagnostic systems. These diagnostic systems provide assistance by assigning likelihoods to alternative explanatory hypotheses in response to a set of findings or observations. Approximation algorithms have been used to compute likelihoods of hypotheses in large networks. We analyze the performance of leading Monte Carlo approximation algorithms for computing posterior probabilities in belief networks. The analysis differs from earlier attempts to characterize the behavior of simulation algorithms in our explicit use of Bayesian statistics: We update a probability distribution over target probabilities of interest with information from randomized trials. For real ϵ, δ < 1 and for a probabilistic inference Pr[ x | e ], the output of an inference approximation algorithm in an (ϵ, δ)‐ estimate of Pr[ x | e ] if with probability at least 1 – δ the output is within relative error ϵ of Pr[ x | e ]. We construct a stopping rule for the number of simulations required by logic sampling, randomized approximation schemes , and likelihood weighting to provide (ϵ, δ)‐estimates of Pr[ x | e ]. With Probability 1 – δ, the stopping rule is optimal in the sense that the algorithm performs the minimum number of required simulations. We prove that our stopping rules are insensitive to the prior probability distribution on Pr[ x | e ]. © 1993 by John Wiley & Sons, Inc.