PostScript

Bayesian networks provide a language for qualitatively representing the
conditional independence properties of a distribution. This allows a
natural and compact representation of the distribution, eases knowledge
acquisition, and supports effective inference algorithms. It is well-known,
however, that there are certain independencies that we cannot capture
qualitatively within the Bayesian network structure: independencies that hold
only in certain * contexts*, i.e., given a specific assignment of
values to certain variables. In this paper, we
propose a formal notion of * context-specific independence*, based on
regularities in the conditional probability tables (CPTs) at
a node. We present a technique, analogous to (and based on) d-separation,
for determining when such an independence holds in a given network. We then
focus on one particular qualitative representation scheme ---
tree-structured CPTs --- for capturing context-based irrelevance. We
suggest ways in which this representation can be used to support effective
inference algorithms, both exact and approximate. In particular, we present
a structural decomposition of the resulting network which can improve
the performance of clustering algorithms, and an alternative algorithm based
on cutset conditioning. We also show how the ideas of context-specific
independence can be used to support approximate probabilistic
inference.

nir@cs.huji.ac.il