M. Studeny: Integer linear programming approach to learning Bayesian network structure: towards the essential graph In Proceedings of the 6th European Workshop on Probabilistic Graphical Models (A. Cano, M. Gomez-Olmedo, T. D. Nielsen eds.), University of Granada 2012, pp. 307-314.

Abstract

The basic idea of a geometric approach to learning a Bayesian network (BN) structure is to represent every BN structure by a certain (uniquely determined) vector. If the vector representative is chosen properly, it 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. Suitable such a zero-one vector representative is the characteristic imset, introduced in (Studeny, Hemmecke, Lindner 2010). In this paper, extensions of characteristic imsets are considered which additionally encode chain graphs without flags equivalent to acyclic directed graphs. The main contribution is the polyhedral description (= in terms of a set of linear inequalities) of the respective domain of the ILP problem. It is just a theoretical result, but it opens the way to the application of ILP software packages in the area of learning a BN structure. The advantage of this approach is that, as a by-product of the ILP optimization procedure, one may get the essential graph, which is a traditional graphical BN representative.

AMS classification 68T30

Keywords

characteristic imset

integer linear programming

essential graph

A scanned pdf copy (408kB) is available. A substantially extended version of this conference paper was later published as a journal paper:

• M. Studeny, D. Haws: Learning Bayesian network structure: towards the essential graph by integer linear programming tools.
  International Journal of Approximate Reasoning 55 (2014), pp. 1043-1071.

---

The contribution follows the approach proposed in a previous PGM 2010 conference paper:

• 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. 257-264.

The technical proof of the main observations are in a research report:

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

---