Exploiting Contextual Independence In Probabilistic Inference

David Poole poole@cs.ubc.ca
Department of Computer Science,
University of British Columbia,
2366 Main Mall, Vancouver, B.C., Canada V6T 1Z4
http://www.cs.ubc.ca/spider/poole/
Nevin Lianwen Zhang lzhang@cs.ust.hk
Department of Computer Science,
Hong Kong University of Science and Technology, Hong Kong,
http://www.cs.ust.hk/~lzhang/

April 3, 2003

Journal of Artificial Intelligence Research, 18, 263-313, 2003.

Abstract

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.


David Poole and Nevin Lianwen Zhang,Exploiting Contextual Independence In Probabilistic Inference, Journal of Artificial Intelligence Research, 18, 2003, 263-313.