Architectures and approximation algorithms for probabilistic expert systems
R. Martin Chavez · 1990
Within the discipline of medical informatics, researchers have considered many methodologies for encoding the knowledge of expert clinicians as computational artifacts. I address the computational complexity of algorithms that perform approximate inference in formal probabilistic models. In addition, I design and implement the sc KNET architecture, which embeds those approximation algorithms in a general-purpose environment for constructing medical expert systems based on belief networks. My research demonstrates that the belief-network representation supports the principled design of tools for building expert systems based on probability theory. More important, my work illuminates the computational properties of approximate probabilistic inference. My results characterize the numerical and topological properties that hinder approximate inference on belief networks. The core of my theoretical work establishes the following thesis: There exists a randomized approximation scheme sc BN-RAS (Belief Network Randomized Approximation Scheme), based on Markov-blanket stochastic simulation, for the ${\cal NP}$-hard problem of probabilistic inference in belief networks (sc PIBNET). With high probability, sc BN-RAS computes posterior probabilities to within a prespecified relative or absolute error. The algorithm specifies a formula that places an a priori upper bound on the required computation time. I define a conductance property for belief networks, and show that conductances near 1.0 guarantee efficient inference. I offer evidence that better bounds probably do not exist, for arbitrary networks. I employ graph-theoretic arguments to derive nearly tight bounds for the running time of sc BN-RAS on a subclass of belief networks. I then apply similar techniques to the design of a related algorithm sc BN-LS, based on logic sampling, for forward propagation of evidence in belief networks. The analytic methods developed in this work typically yield bounds that are far too pessimistic for everyday use. Nevertheless, the empirically acceptable performance of sc BN-RAS on probabilistic models of realistic size suggests that specialized analytic techniques, which exploit fully the numerical and topological properties of particular belief networks, may eventually lead to better bounds on the approximation scheme's convergence. The simplicity of sc BN-RAS renders the algorithm a particularly attractive target for further analysis.