Bibliography
Conference Paper (international conference)
The chordal graph polytope for learning decomposable models
,
: Proceedings of the Eighth International Conference on Probabilistic Graphical Models, p. 499-510 , Eds: Antonucci A., Corani G., Polpo de Campos C.
: the Eighth International Conference on Probabilistic Graphical Models, (Lugano, CH, 06.09.2016-09.09.2016)
: GA16-12010S, GA ČR
: learning decomposable models, integer linear programming, characteristic imset, chordal graph polytope, clutter inequalities, separation problem
: http://library.utia.cas.cz/separaty/2016/MTR/studeny-0462009.pdf
(eng): 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.
: BA