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.
- 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 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.
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 facet-defining 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. 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.