CEC Theses and Dissertations


Approximation of Marginal Probabilities While Learning Bayesian Networks

Date of Award


Document Type


Degree Name

Doctor of Philosophy (PhD)


Graduate School of Computer and Information Sciences


Sumitra Mukherjee

Committee Member

Maxine S. Cohen

Committee Member

Junping Sun


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.

This document is currently not available here.

  Link to NovaCat