M. Studeny:
Characterization of inclusion neighbourhood in terms of the
essential graph: upper neighbours.
In Symbolic and Quantitative Approaches to Reasoning with Uncertainty
(T. D. Nielsen, L. N. Zhang eds.), Lecture Notes in Artificial Intelligence 2711, Springer-Verlag,
Berlin - Heidelberg 2003, pp. 161-172.
- Abstract
- The problem of efficient characterization of inclusion neighbourhood
is crucial in some methods for learning (equivalence classes) of Bayesian
networks. In this paper, neighbouring equivalence classes of a given
equivalence class of Bayesian networks are characterized efficiently by means
of the respective essential graph. The characterization reveals hidden
internal structure of the inclusion neighbourhood. More exacly,
upper neighbours, that is, those neighbouring equivalence classes which
describe more independencies, are completely characterized here.
First, every upper neighbour is characterized by a pair ([a,b],C)
where [a,b] is an edge in the essential graph and C
a disjoint set of nodes. Second, if [a,b] is fixed, the class
of sets C which characterize the respective neighbours is a
tuft of sets determined by its least set and the list of its maximal
sets. These sets can be read directly from the essential graph.
- AMS classification 68T30, 62H05
- Keywords
- (Markov) equivalence of Bayesian networks
- learning Bayesian networks
- essential graph
- inclusion neighbourhood
- upper neighbours
- tuft of sets
- A
pdf copy (converted postscript) of an extended version (255kB) 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.