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. 499510.
 Abstract

The paper is inspired by an integer linear programming
approach to learning the structure of decomposable models.
We intend to represent decomposable models by special zeroone 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.
We introduce a class of clutter inequalities and show that all of them
are valid for (the vectors in) the polytope. In fact, these inequalities
are even facetdefining for the polytope and we dare to conjecture
that they lead to a complete polyhedral description of the polytope.
Finally, we propose an LP method to solve the separation problem
with these inequalities for 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 (253kB) is 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. 182191.
 R. Hemmecke, S. Lindner, M. Studeny:
Characteristic imsets for learning Bayesian network structure.
International Journal of Approximate Reasoning
53 (2012), n. 9, pp. 13361349.
 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. 10431071.