Probabilistic Inference Using Partitioned Bayesian Networks: Introducing a Compositional Framework

Giso Dal

Research output: ThesisPhD Thesis - Research UT, graduation UT

31 Downloads (Pure)

Abstract

Probability theory offers an intuitive and formally sound way to reason in situations that involve uncertainty. The automation of probabilistic reasoning has many applications such as predicting future events or prognostics, providing decision support, action planning under uncertainty, dealing with multiple uncertain measurements, making a diagnosis, and so forth. Bayesian networks in particular have been used to represent probability distributions that model the various applications of uncertainty reasoning. However, present-day automated reasoning approaches involving uncertainty struggle when models increase in size and complexity to fit real-world applications.

In this thesis, we explore and extend a state-of-the-art automated reasoning method, called inference by Weighted Model Counting (WMC), when applied to increasingly complex Bayesian network models. WMC is comprised of two distinct phases: compilation and inference. The computational cost of compilation has limited the applicability of WMC. To overcome this limitation we have proposed theoretical and practical solutions that have been tested extensively in empirical studies using real-world Bayesian network models.

We have proposed a weighted variant of OBDDs, called Weighted Positive Binary Decision Diagrams (WPBDD), which in turn is based on the new notion of positive Shannon decomposition. WPBDDs are particularly well suited to represent discrete probabilistic models. The conciseness of WPBDDs leads to a reduction in the cost of probabilistic inference.

We have introduced Compositional Weighted Model Counting (CWMC), a language-agnostic framework for probabilistic inference that partitions a Bayesian network into subproblems. These subproblems are then compiled and subsequently composed in order to perform inference. This approach significantly reduces the cost of compilation, yet increases the cost of inference. The best results are obtained by seeking a partitioning that allows compilation to (barely) become feasible, but no more, as compilation cost can be amortized over multiple inference queries.

Theoretical concepts have been implemented in a readily available open-source tool called ParaGnosis. Further implementational improvements have been found through parallelism, by exploiting independencies that are introduced by CWMC. The proposed methods combined push the boundaries of WMC, allowing this state-of-the-art method to be used on much larger models than before.
Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • University of Twente
Supervisors/Advisors
  • Lucas, Peter J.F., Supervisor
  • Laarman, Alfons W., Co-Supervisor, External person
  • Hommersom, Arjen, Co-Supervisor, External person
Award date29 Feb 2024
Place of PublicationEnschede
Publisher
Print ISBNs978-90-365-5973-7
Electronic ISBNs978-90-365-5974-4
DOIs
Publication statusPublished - Feb 2024

Keywords

  • Probabilistic logic
  • Bayesian Networks
  • Weighted model counting
  • Parallel computation

Fingerprint

Dive into the research topics of 'Probabilistic Inference Using Partitioned Bayesian Networks: Introducing a Compositional Framework'. Together they form a unique fingerprint.

Cite this