Probabilistic Decision Graphs

Probabilistic Decision Graphs (PDGs) combine elements of probabilistic graphical
models and ordered binary decision diagrams (OBDDs). PDGs were first
proposed by M. Bozga and O. Maler in the context of probabilistic verification.
We have introduced a slightly generalized version of PDGs, and investigated
their properties from a reasoning under uncertainty point of view. Special
focus of this work is a comparison with Bayesian networks with regard to
efficiency of probabilistic inference, and with regard to the probabilistic independence
models that can be represented by the graphical structures in the
two frameworks. The results show that PDGs and Bayesian networks represent
different kinds of independence structures: whereas independence structures encoded
by Bayesian networks are given in terms of subsets of random variables,
the independence structures encoded by PDGs are given in terms of partitions
of the state space. For probability distributions exhibiting the latter type of
independence patterns, one can obtain significantly more efficient representations
(with regard to complexity of probabilistic inference) with PDGs than
with Bayesian networks.

We also have developed and implemented a learning algorithm for PDGs. We have conducted experiments in which both PDG and Bayesian network
models were learned from real-life data sets. Goal of the experiments was to
determine whether for some types of data the learning algorithms for the two
frameworks would produce models with significantly different inference complexity.
Somewhat surprisingly, the results showed that the learned models in the
two representation languages exhibited quite similar complexity characteristics.