Abstract

The motivation for the paper is the geometric approach to learning Bayesian network (BN) structure. The basic idea of our approach is to represent every BN structure by a certain uniquely determined vector so that usual scores for learning BN structure become affine functions of the vector representative. The original proposal from (Studeny, Vomlel, Hemmecke 2010) was to use a special vector having integers as components, called the standard imset, as the representative. In this paper we introduce a new unique vector representative, called the characteristic imset, obtained from the standard imset by an affine transformation. Characteristic imsets are (shown to be) zero-one vectors and have many elegant properties, suitable for intended application of linear/integer programming methods to learning BN structure. They are much closer to the graphical description; we describe a simple transition between the characteristic imset and the essential graph, known as a traditional unique graphical representative of the BN structure. In the end, we relate our proposal to other recent approaches which apply linear programming methods in probabilistic reasoning.

AMS classification 68T30, 52B12, 62H05

Keywords

learning Bayesian network structure

essential graph

standard imset

characteristic imset

LP relaxation of a polytope

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

The paper is an extended version of the conference paper

• M. Studeny, R. Hemmecke, S. Lindner: Characteristic imset: a simple algebraic representative of a Bayesian network structure. In Proceedings of the 5th European Workshop on Probabilistic Graphical Models (P. Myllymaki, T. Roos and T. Jaakkola eds.), HIIT Publications 2010, pp. 257-264.

Moreover, it also builds on results from the following publications:

• M. Studeny (2005). Probabilistic Conditional Independence Structures. London: Springer-Verlag.
• M. Studeny, J. Vomlel, R. Hemmecke: Geometric view on learning Bayesian network structures. International Journal of Approximate Reasoning 51 (2010), n. 5, pp. 578-586.
• M. Studeny, J. Vomlel: On open questions in the geometric approach to structural learning Bayesian nets. International Journal of Approximate Reasoning 52 (2011), n. 5, pp. 627-640.