Abstract

The question 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 in terms of the respective essential graph. One can distinguish two kinds of inclusion neighbours: upper and lower ones. This paper reveals the hidden internal structure of both parts of the inclusion neighbourhood. It is shown here that each inclusion neighbour is uniquely described by a pair ([a,b],C) where [a,b] is an unordered pair of distinct nodes and C a disjoint set nodes in the essential graph. Upper neighbours correspond to edges in the essential graph, while lower neighbours correspond to pairs of nodes that are not edges in the essential graph. Given a pair [a,b] of distinct nodes in the essential graph, the class of those sets C that ([a,b],C) encodes an inclusion neighbour is characterized. The class has a special form; it is uniquely determined by certain distinguished sets. These distinguished sets of the class can be read directly from the essential graph.

AMS classification 68T30, 62H05

Keywords

learning Bayesian networks

inclusion neighbourhood

essential graph

A scanned pdf copy (478kB) is available.

The paper is an extended version of two conference papers:

• 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.
• 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.

• D. M. Chickering: Optimal structure identification with greedy search. Journal of Machine Learning Research 3 (2002), pp. 507-554.
• V. Auvray, L. Wehenkel: On the construction of the inclusion boundary neighbourhood for Markov equivalence clases of Bayesian network structures. In Uncertainty in Artificial Intelligence 18 (A. Darwiche, N. Friedman eds.), Morgan Kaufmann (2002), pp. 26-35.
• Chapter 8 in M. Studeny: Probabilistic Conditional Independence Structures. Springer-Verlag, London, 2005.