  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 (CSI),
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 independence holds in a given network. We then focus on a
particular qualitative representation scheme - tree-structured CPTs - for
capturing CSI. We suggest ways in which this representation can be used to
support effective inference algorithms. 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.
