Exploiting Contextual Independence In Probabilistic Inference
  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.
