Probabilistic Partial Evaluation:
Exploiting rule structure in probabilistic inference
In Proc. 15th International Joint
Conference on Artificial Intelligence (IJCAI-97), Nagoya,
Japan, August 1997.
Abstract
Bayesian belief networks have grown to prominence because they provide
compact representations of many domains, and there are algorithms to
exploit this compactness. The next step is to allow compact
representations of the conditional probability tables of a variable
given its parents. In this paper we present such a representation in
terms of parent contexts and provide an algorithm that exploits this
compactness. The representation is in terms of rules that provide
conditional probabilities in different contexts. The algorithm is
based on eliminating the variables not needed in an answer in
turn. The operations for eliminating a variable correspond to a form
of partial evaluation, where we are careful to maintain the
probabilistic dependencies necessary for correct probabilistic
inference. We show how this new method can exploit more structure
than previous methods for structured belief network inference.
You can get the
pdf or get the postscript.
You can also see the Slides
for the talk. This is in adobe
PDF format and can be read using the free acrobat reader.
Errata
Thanks to Nevin
Zhang for pointing put this error (or a way this can be simplified).
If you are eliminating e, and e appears in two rules,
the head of one is in the body of another, as in:
a <- b & c & e : p1
b <- c & e : p2
You do no split the second rule on b, but just multiple them
giving:
a & b <- c & e : p1*p2
This is because
P(a & b | c & e) = P(a | b & c & e) * P(b | c & e)
by the chain rule of probability theory.
Related Papers
D. Poole, Context-specific
approximation in probabilistic inference. This paper shows
how to approximate in the same framework, and presents empirical
evaluation of the approximation.
D. Poole, The Independent Choice Logic for
modelling multiple agents under uncertainty. This paper
pushes the rule-based representation to its logical extremes.
D. Poole, Exploiting the Rule Structure
for Decision Making within the Independent Choice Logic
. This paper shows how the rule structure can be exploited
to reduce the case analysis in dynamic programming.
Last updated 25 Apr 97 - David Poole