Abstract

The motivation for this paper is the integer linear programming (ILP) approach to learning the structure of a decomposable graphical model. We have chosen to represent decomposable models by means of special zero-one vectors, named characteristic imsets. Our approach leads to the study of a special polytope, defined as the convex hull of all characteristic imsets for chordal graphs, named the chordal graph polytope. In this theoretical paper, we introduce a class of clutter inequalities (valid for the vectors in the polytope) and show that all of them are facet-defining for the polytope. We dare to conjecture that they lead to a complete polyhedral description of the polytope. Finally, we propose a linear programming method to solve the separation problem with these inequalities for the use in a cutting plane approach.

AMS classification 52B12 68T30 90C27

Keywords

integer linear programming

learning decomposable models

characteristic imset

chordal graph polytope

clutter inequalities

separation problem

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

The contribution builds on the following papers:

• M. Bartlett, J. Cussens: Advances in Bayesian network learning using integer programming. In Uncertainty in Artificial Intelligence. Proceedings of the 29th Conference (A. Nicholson, P. Smyth eds.), AUAI Press, Corvallis 2013, pp. 182-191.
• R. Hemmecke, S. Lindner, M. Studeny: Characteristic imsets for learning Bayesian network structure. International Journal of Approximate Reasoning 53 (2012), n. 9, pp. 1336-1349.
• S. L. Lauritzen (1996). Graphical Models. Clarendon Press, Oxford.
• S. Lindner (2012) Discrete optimization in machine learning: learning Bayesian network structures and conditional independence implication. PhD thesis, TU Munich.
• 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.

Moreover, the paper is an extended version of the conference proceedings paper:

• M. Studeny, J. Cussens: The chordal graph polytope for learning decomposable models. In JMLR Workshops and Conference Proceedings 52 (2016), Proceedings of the Conference on Probabilistic Graphical Models [PGM 2016], (A. Antonucci, G. Corani, C. P. de Campos eds.), pp. 499-510.