Context-Specific Independence in Bayesian Networks

Craig Boutilier, Nir Friedman, Moisés Goldszmidt, Daphne Koller

arXiv (Cornell University) · 2013 · 557 citations · 8 references

DOIFull text

Open access

Concepts

TL;DR

Bayesian networks qualitatively represent conditional independence, but cannot capture context‑specific independencies that hold only under particular variable assignments. The paper proposes a formal notion of context‑specific independence (CSI) based on CPT regularities, focuses on tree‑structured CPTs to capture CSI, and suggests how this representation can support inference. The authors develop a d‑separation‑like technique to identify CSI in a network, employ tree‑structured CPTs to represent it, and outline how this representation can aid inference. The proposed CSI framework yields a natural, compact representation that eases knowledge acquisition, supports inference, and enables structural decomposition that improves clustering performance and offers an alternative cutset‑conditioning algorithm.

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 (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.

References

8