Abstract

A standard graphical representative of a Bayesian network structure is a special chain graph, known as an essential graph. An alternative algebraic approach to the mathematical description of this statistical model uses instead a certain integer-valued vector, known as a standard imset. We give a direct formula for the translation of any chain graph describing a Bayesian network structure into the standard imset. Moreover, we present a two-stage algorithm which makes it possible to reconstruct the essential graph on the basis of the standard imset. The core of this paper is the proof of the correctness of the algorithm.

AMS classification 68T30, 05C90

Keywords

Bayesian network structure

chain graph

essential graph

standard imset

A pdf version of the published paper (708kB) is already open-access available.

The paper is (quite a lot) extended version of the conference paper:

• M. Studeny, J. Vomlel: Transition between graphical and algebraic representatives of Bayesian network models. In Proceedings of the 2nd European Workshop on Probabilistic Graphical Models (P. Lucas ed.), University of Nijmegen 2004, pp. 193-200.

• M. Studeny: Probabilistic Conditional Independence Structures. Springer-Verlag, London, 2005.
• S.A. Andersson, D. Madigan, M.D. Perlman: A characterization of Markov equivalence classes for acyclic digraphs. Annals of Statistics 25 (1997), pp. 505-541.

Moreover, it uses some of the results of a parallel paper:

• M. Studeny, A. Roverato, S. Stepanova: Two operations of merging and splitting components in a chain graph. Kybernetika 45 (2009), n. 2, pp. 208-248.