Exploiting contextual independence in probabilistic inference
In Journal of Artificial
Intelligence Research, Volume 18, pages 263-313, 2003.
Bayesian belief networks have grown to prominence because they provide
compact representations for many problems for which probabilistic
inference is appropriate, and there are algorithms to exploit this
compactness. The next step is to allow compact representations of the
conditional probabilities of a variable given its parents. In this paper
we present such a representation that exploits contextual independence
in terms of parent contexts; which variables act as parents
may depend on the value of other variables. The internal representation
is in terms of contextual factors (confactors) that is simply a pair of
a context and a table. The algorithm, contextual variable
elimination, is based on the standard variable elimination
algorithm that eliminates the non-query variables in turn, but when
eliminating a variable, the tables that need to be multiplied can
depend on the context. This algorithm reduces to standard variable
elimination when there is no contextual independence structure to
exploit. We show how this can be much more efficient than variable
elimination when there is structure to exploit. We explain why this new
method can exploit more structure than previous methods for structured
belief network inference and an analogous algorithm that uses trees.
You can get the pdf or the postscript or the html.
Last updated 3 April 2003 - David Poole