M. Studeny: LP relaxations and pruning for characteristic imsets. Research report n. 2323, Institute of Information Theory and Automation, Prague, June 2012.

Abstract
The geometric approach to learning a Bayesian network (BN) structure is based on the idea to represent every BN structure by a certain vector. Suitable such a zero-one vector representative is the characteristic imset. This concept allows one to re-formulate the task of finding the global maximum of a score over BN structures as an integer linear programming (ILP) problem. In this research report, extensions of characteristic imsets are considered which additionally encode chain graphs without flags equivalent to acyclic directed graphs. The main contribution is the LP relaxation of the corresponding polytope, that is, a polyhedral description (= in terms of linear inequalities) of the domain of the respective ILP problem. The advantage of this approach is that, as a by-product of the ILP optimization procedure, one may directly get the essential graph, which is a traditional graphical BN representative. In the second part of the report, the method of search space reduction is discussed; in our context it leads to suitable pruning components of the characteristic imsets, that is, to the reduction of the length of these vector representatives.

AMS classification 68T30

Keywords
learning Bayesian network structure
quality criterion
integer linear programming
characteristic imset
LP relaxation
essential graph
search space reduction

A pdf version (407kB) is available.
The report partially builds on these publications: