Probabilistic Decision Graphs

Titel: Probabilistic Decision Graphs

The need for the compact representation and efficient manipulation of
probability distributions
has arisen both in Artificial Intelligence and in the field of
verification of probabilistic
systems. In AI, Bayesian networks have been developed, and today are
almost universally employed for tasks that involve reasoning under
uncertainty.
In verification, on the other hand, probabilistic versions of binary
decision diagrams
have been developed.

In this lecture I will introduce Probabilistic Decision Graphs -- a BDD
based representation
framework adapted from work by Bozga and Maler -- and explore their
properties from
an AI point of view. It turns out that PDGs are highly
competitive with Bayesian networks for AI applications, as the basic
inference tasks
there needed can be performed with PDGs always as efficiently as with
Bayesian networks,
and sometimes more efficiently.

I will discuss the problem of learning PDGs from data, and argue that
their greatest
potential advantage over Bayesian networks lies in the fact that
learning methods for
PDGs can be developed that score a potential model structure directly
according to
the efficiency of inference with this model structure, rather than the
size of
representation using this model structure.