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/

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.

- Introduction
- Background
- Contextual Independence
- Contextual Variable Elimination
- Multiplying Contextual Factors
- Summing Out A Variable That Appears In The Table
- Summing Out A Variable In The Body Of Confactors
- Confactor Splitting
- Examples of Eliminating Variables
- When to Split
- Evidence
- Extracting the Answer
- The Abstract Contextual Variable Elimination Algorithm
- Ones
- Multi-Valued Variables
- Why CVE Does More Than Representing Factors As Trees
- CVE Compared To VE

- Avoiding Splitting
- Empirical Results
- Comparison With Other Proposals
- Conclusion
- Acknowledgements
- Details of the experiments
- References
- Footnotes
- Navigation

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