R. Hemmecke, S.Lindner, M. Studeny:
Characteristic imsets for learning Bayesian network structure.
International Journal of Approximate Reasoning
53 (2012), n. 9, pp. 13361349.
 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) zeroone 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 openaccess available.
The paper builds on results from the following publications: