Abstract

The basic idea of the geometric approach to learning a Bayesian network (BN) structure is to represent every BN structure by a certain 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. Such a suitable zero-one vector representative is the characteristic imset, introduced by Studeny, Hemmecke and Lindner in 2010, in the proceedings of the 5th PGM workshop. 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 a polyhedral description of the respective domain of the ILP problem, that is, by means of a set of linear inequalities. This theoretical result opens the way to the application of ILP software packages. The advantage of our 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. We also describe some computational experiments based on this idea.

AMS classification 68T30 52B12 62H05

Keywords

learning Bayesian network structure

integer linear programming

characteristic imset

essential graph

A pdf version of the published paper (477kB) is already open-access available.

The paper is (quite a lot) extended version of the conference paper

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

Moreover, it also builds on results from the following journal papers:

• R. Hemmecke, S. Lindner, M. Studeny: Characteristic imsets for learning Bayesian network structure. International Journal of Approximate Reasoning 53 (2012), pp. 1336-1349.
• M. Studeny, D. C. Haws: On polyhedral approximations of polytopes for learning Bayesian networks. Journal of Algebraic Statistics 4 (2013), pp. 58-91.