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 zeroone vector representative is the characteristic imset.
This concept allows one to reformulate 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 byproduct 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:
 M. Studeny:
Probabilistic Conditional Independence Structures. SpringerVerlag, London, 2005.
 C.P. de Campos, Q. Ji:
Efficient structure learning Bayesian networks using constraints. Journal of Machine Learning Research 12 (2011) pp. 663689.
 T. Jaakkola, D. Sontag, A. Globerson, M. Meila:
Learning Bayesian network structure using LP relaxations. In Proceedings of the 13th International Conference on Artificial
Intelligence and Statistics (2010) pp. 358365.
 J. Cussens:
Bayesian network learning with cutting planes. In Proceedings of the 27th Conference on Uncertainty in Artificial
Intelligence (2011) pp. 153160.