arXiv (Cornell University) · 2013 · 557 citations · 8 references
ComputingComputer ScienceKnowledge RepresentationProbability TheoryStatistical ModelingBayesian InferenceBayesian ModelingBayesian StatisticsNetwork InferenceProbabilistic ModelingStatistical InferenceBayesian Graphical ModelsBayesian NetworksConditional IndependenceConditional Independence ModelsConditional Probability ModelsContext IndependenceStructural DecompositionStructural Decomposition Analysis
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.
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.
8
Graph-Based Algorithms for Boolean Function Manipulation
Bryant · IEEE Transactions on Computers · 1986 · 8.9K citations · Full text
Probabilistic Horn abduction and Bayesian networks
David Poole · Artificial Intelligence · 1993 · 593 citations
Exploiting Structure in Policy Construction
Craig Boutilier, Richard Dearden, Moisés Goldszmidt · 1995 · 360 citations