|
Abstract : |
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 ffl; ffi! 1 and for a probabilistic inference Pr[xje], the output of an inference approximation algorithm is an (ffl; ffi)-estimate of Pr[xje] if with probability at least 1 \Gamma ffi the output is within relative error ffl of Pr[xje]. We 1 construct a stopping rule for the number of simulations required by logic sampling, randomized approximation schemes, and likelihood weighting to provide (ffl; ffi)-estimates of Pr[xje]. With probability 1 \Gamma ffi, 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[xje]. 2, |
