The chordal graph polytope for learning decomposable models

0462009 - ÚTIA 2017 RIV US eng C - Konferenční příspěvek (zahraniční konf.)
Studený, Milan - Cussens, J.
The chordal graph polytope for learning decomposable models.
Proceedings of the Eighth International Conference on Probabilistic Graphical Models. Brookline: Microtome Publishing, 2016 - (Antonucci, A.; Corani, G.; Polpo de Campos, C.), s. 499-510. JMLR: Workshop and Conference Proceedings, vol. 52. E-ISSN 1938-7228.
[the Eighth International Conference on Probabilistic Graphical Models. Lugano (CH), 06.09.2016-09.09.2016]
Grant CEP: GA ČR(CZ) GA16-12010S
Institucionální podpora: RVO:67985556
Klíčová slova: learning decomposable models * integer linear programming * characteristic imset * chordal graph polytope * clutter inequalities * separation problem
Kód oboru RIV: BA - Obecná matematika
http://library.utia.cas.cz/separaty/2016/MTR/studeny-0462009.pdf

This theoretical paper is inspired by an integer linear programming (ILP) 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.
Trvalý link: http://hdl.handle.net/11104/0261903