Learning Equivalence Classes of Bayesian-Network Structures
David Maxwell Chickering;
2(Feb):445-498, 2002.
Abstract
Two Bayesian-network structures are said to be
equivalent if the set of distributions that can be represented with
one of those structures is identical to the set of distributions that
can be represented with the other. Many scoring criteria that are used
to learn Bayesian-network structures from data are
score
equivalent; that is, these criteria do not distinguish among networks
that are equivalent. In this paper, we consider using a score
equivalent criterion in conjunction with a heuristic search algorithm
to perform model selection or model averaging. We argue that it is
often appropriate to search among equivalence classes of network
structures as opposed to the more common approach of searching among
individual Bayesian-network structures. We describe a convenient
graphical representation for an equivalence class of structures, and
introduce a set of operators that can be applied to that
representation by a search algorithm to move among equivalence
classes. We show that our equivalence-class operators can be scored
locally, and thus share the computational efficiency of traditional
operators defined for individual structures. We show experimentally
that a greedy model-selection algorithm using our representation
yields slightly higher-scoring structures than the traditional
approach without any additional time overhead, and we argue that more
sophisticated search algorithms are likely to benefit much more.
[abs]
[pdf]
[ps.gz]
[ps]
errata: [pdf]
[ps.gz]
[ps]
