CCE Theses and Dissertations
Approximation of Marginal Probabilities While Learning Bayesian Networks
Date of Award
2000
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Department
Graduate School of Computer and Information Sciences
Advisor
Sumitra Mukherjee
Committee Member
Maxine S. Cohen
Committee Member
Junping Sun
Abstract
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.
NSUWorks Citation
Joseph E. Cannon. 2000. Approximation of Marginal Probabilities While Learning Bayesian Networks. Doctoral dissertation. Nova Southeastern University. Retrieved from NSUWorks, Graduate School of Computer and Information Sciences. (444)
https://nsuworks.nova.edu/gscis_etd/444.