Institute of Information Theory and Automation

You are here

Bibliography

Conference Paper (international conference)

The chordal graph polytope for learning decomposable models

Studený Milan, Cussens J.

: 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

: 10.1016/j.ijar.2017.06.001

: 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

2019-01-07 08:39