Towards using the chordal graph polytope in learning decomposable models

0475614 - ÚTIA 2018 RIV US eng J - Journal Article
Studený, Milan - Cussens, J.
Towards using the chordal graph polytope in learning decomposable models.
International Journal of Approximate Reasoning. Roč. 88, č. 1 (2017), s. 259-281. ISSN 0888-613X. E-ISSN 1873-4731.
[8th International Conference of Probabilistic Graphical Models. Lugano, 06.09.2016-09.09.2016]
R&D Projects: GA ČR(CZ) GA16-12010S
Institutional support: RVO:67985556
Keywords : learning decomposable models * integer linear programming * characteristic imset * chordal graph polytope * clutter inequalities * separation problem
OECD category: Statistics and probability
Impact factor: 1.766, year: 2017
http://library.utia.cas.cz/separaty/2017/MTR/studeny-0475614.pdf

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.
Permanent Link: http://hdl.handle.net/11104/0272346