Probabilistic Partial Evaluation: Exploiting rule structure in probabilistic inference

David Poole

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