Approximation of Marginal Probabilities While Learning Bayesian Networks

Computation of marginal probabilities in Bayesian Belief Networks is central to many probabilistic reasoning systems and automatic decision making systems. The process of belief updating in Bayesian Belief Networks (BBN) is a well-known computationally hard problem that has recently been approximated by several deterministic algorithms and by various randomized approximation algorithms. Although the deterministic algorithms usually provide probability bounds, they have exponential runtimes. Some of the randomized schemes have a polynomial runtime, but do not exploit the causal independence in BBNs to reduce the complexity of the problem. This dissertation presents a computationally efficient and deterministic approximation scheme for this NP-hard problem that recovers approximate posterior probabilities given a large multiply connected BBN. The scheme presented utilizes recent work in belief updating for BBNs by Santos and Shimony (1998) and Bloemeke (1998). The scheme employs the Independence-based (IB) assignments proposed by Santos and Shimony to reduce the graph connectivity and the number of variables in the BBN by exploiting causal independence. It recovers the desired posterior probabilities by means of Netica™, a commercially available application for Belief Networks and Influence Diagrams