Reference: Chavez, M. R. & Cooper, G. F. An Empirical Evaluation of a Randomized Algorithm for Probabilistic Inference. Elsevier Science Publishers B.V., North-Holland, 1989.
Abstract: An empirical evaluation of a randomized algorithm for probabilistic inference KNET is an environment for constructing probabilistic, knowledge-based systems within the axiomatic framework of decision theory. The KNET architecture defines a complete separation between the hypermedia user interface on the one hand, and the representation and management of expert opinion on the other. KNET offers a choice of algorithms for probabilistic inference, including exact and approximate methods. In our laboratory, we have used KNET to build consultation sysstems for lymph-node pathology, bone-marrow transplantation therapy, clinical epidemiology, and alarm management in the intensive-care unit. Most important, KNET contains a fully polynomial randomized approximation scheme (fpras) for the difficult and almost certainly intractable problem of Bayesian inference. The algorithm can, in many circumstances, perform efficient approximate inference in large and richly interconnected models of medical diagnosis. In this article, we summarize a randomized algorithm for probabilistic inference and analyze its performance mathematically. Then, we devote the major portion of the paper to a discussion of the algorithm's empirical behavior. The results indicate that the generation of good samples (that is, samples whose distribution closely matches the true distribution), rather than the computation of numerous mediocre samples, dominates the performance of stochastic simulation.