Context-Specific Independence in Bayesian Networks

C. Boutilier, N. Friedman, M. Goldszmidt, and D. Koller

In Proc. Twelfth Conf. on Uncertainty in Artificial Intelligence (UAI 96).

Postscript version (168K) PDF version.


Abstract

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.


Back to Nir's publications page


nir@cs.huji.ac.il