Craig Boutilier
Department of Computer Science
University of British Columbia
Vancouver, BC, CANADA, V6T 1Z4
email: cebly@cs.ubc.ca
Nir Friedman
Department of Computer Science
Stanford University
Stanford, CA 94305-9010, USA
email: nir@cs.stanford.edu
Moises Goldszmidt
RI International
333 Ravenswood Way, EK32
Menlo Park, CA 94025, USA
email: moises@erg.sri.com
Daphne Koller
Department of Computer Science
Stanford University
Stanford, CA 94305-9010, USA
email: daphne@cs.stanford.edu
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.
To appear, UAI-96
Return to List of Papers