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. 257264.
 Abstract

First, we recall the basic idea of an algebraic and geometric approach
to learning a Bayesian network (BN) structure proposed in (Studeny, Vomlel, Hemmecke 2010):
to represent every BN structure by a certain uniquely determined vector.
The original proposal was to use a socalled standard imset which is a vector having integers as components,
as an algebraic representative of a BN structure.
In this paper we propose an even simpler algebraic representative called the characteristic imset.
It is 01vector obtained from the standard imset by an affine transformation.
This implies that every reasonable quality criterion is an affine function of the characteristic imset.
The characteristic imset is much closer to the graphical description:
we establish a simple relation to any chain graph without flags that defines the BN structure.
In particular, we are interested in the relation to the essential graph,
which is a classic graphical BN structure representative.
In the end, we discuss two special cases in which the use of characteristic imsets particularly simplifies things:
learning decomposable models and (undirected) forests.
 AMS classification 68T30, 62H05
 Keywords
 structural learning Bayesian nets
 standard imset
 characteristic imset
 essential graph
 A
pdf version (154kB) is available.
The paper builds on results from the following (later published) journal publication: