# 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/
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/

## 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.

## 1. Introduction

Probabilistic inference is important for many applications in diagnosis, perception, user modelling, and anywhere there is uncertainty about the state of the world from observations. Unfortunately general probabilistic inference is difficult both computationally and in terms of the number of probabilities that need to be specified. Belief (Bayesian) networks (Pearl, 1988) are a representation of independence amongst random variables. They are of interest because the independence is useful in many domains, they allow for compact representations for many practical problems, and there are algorithms to exploit the compact representations. Note that even approximate inference is computationally difficult in the worst case (Dagum and Luby, 1993).

Recently there has been work to extend belief networks by allowing more structured representations of the conditional probability of a variable given its parents (D'Ambrosio, 1995). This has been in terms of either causal independencies (Heckerman and Breese, 1994; Zhang and Poole, 1996), parametric forms such as sigmoidal Bayesian networks (Neal, 1992; Saul, Jaakkola and Jordan, 1996), or by exploiting contextual independencies inherent in stating the conditional probabilities in terms of rules (Poole, 1993) or trees (Smith, Holtzman and Matheson, 1993; Boutilier, Friedman, Goldszmidt and Koller, 1996). In this paper we show how an algorithm that exploits conditional independence