LP relaxations and pruning for characteristic imsets. Research report n. 2323,
Institute of Information Theory and Automation, Prague, June 2012.
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
- learning Bayesian network structure
- quality criterion
- integer linear programming
- characteristic imset
- LP relaxation
- essential graph
- search space reduction
The report partially builds on these publications:
pdf version (407kB) is available.
- M. Studeny:
Probabilistic Conditional Independence Structures. Springer-Verlag, London, 2005.
- C.P. de Campos, Q. Ji:
Efficient structure learning Bayesian networks using constraints. Journal of Machine Learning Research 12 (2011) pp. 663-689.
- 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. 358-365.
- J. Cussens:
Bayesian network learning with cutting planes. In Proceedings of the 27th Conference on Uncertainty in Artificial
Intelligence (2011) pp. 153-160.