M. Studeny:
Characterization of inclusion neighbourhood in terms of the
essential graph: lower neighbours.
In Proceedings of WUPES'2003 (J. Vejnarova ed.),
School of Economics Prague 2003, pp. 243-262.
- Abstract
- The topic of the contribution is to characterize the inclusion
neighbourhood of a given equivalence class of Bayesian networks
in terms of the respective essential graph so that it can be used
efficiently in a method of local search for maximization of a quality
criterion. One can distinguish two kinds of neighbours: upper and lower
ones. This paper gives a characterization of the lower inclusion
neighbourhood.
It is shown that each lower inclusion neighbour is uniquely described by
a pair ([a,b],C) where [a,b] is an unordered pair
of distinct nodes which is not an edge in the essential graph and
C a disjoint set of nodes. The second basic result is that,
for given [a,b], the
collection of those sets C which correspond to lower inclusion
neigbours has a special form. More specifically, given [a,b],
the respective collection of sets is the union of at most
two tufts of sets. The least and maximal sets of these two tufts,
which determine them, can also be read from the essential graph.
- AMS classification 68T30, 62H05
- Keywords
- (Markov) equivalence of Bayesian networks
- learning Bayesian networks
- essential graph
- inclusion neighbourhood
- lower neighbours
- tuft of sets
-
A
pdf copy (converted postscript version) (312kB) is available.
The paper partially builds on the following papers:
- V. Auvrey, L. Wehenkel: On the construction
of the inclusion boundary neighbourhood for Markov equivalence classes
of Bayesian networks.
In Uncertainty in Artificial Intelligence 18
(A. Darwiche, N. Friedman eds.) Morgan Kaufmann 2002, pp. 26-35.
- D. M. Chickering:
Optimal structure indentification with greedy search.
Journal of Machine Learning Research 3 (2002), pp. 507-554.