Context-Specific Independence in Bayesian Networks
Craig Boutilier, Nir Friedman, Moises Goldszmidt, Daphne Koller
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.
Keywords: Conditional independence, decision trees, probabilistic inference,
PS Link: http://robotics.stanford.edu/~koller/papers/uai96.ps
PDF Link: /papers/96/p115-boutilier.pdf
AUTHOR = "Craig Boutilier
and Nir Friedman and Moises Goldszmidt and Daphne Koller",
TITLE = "Context-Specific Independence in Bayesian Networks",
BOOKTITLE = "Proceedings of the Twelfth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-96)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1996",
PAGES = "115--123"