R. Hemmecke, S.Lindner, M. Studeny:
Characteristic imsets for learning Bayesian network structure.
International Journal of Approximate Reasoning
53 (2012), n. 9, pp. 1336-1349.
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
- learning Bayesian network structure
- essential graph
- standard imset
- characteristic imset
- LP relaxation of a polytope
pdf version of the published paper (337kB) is already open-access available.
The paper builds on results from the following publications: