Institute of Information Theory and Automation

You are here

Bibliography

Journal Article

Towards using the chordal graph polytope in learning decomposable models

Studený Milan, Cussens J.

: International Journal of Approximate Reasoning vol.88, 1 (2017), p. 259-281

: 8th International Conference of Probabilistic Graphical Models, (Lugano, CH, 20160906)

: 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/2017/MTR/studeny-0475614.pdf

(eng): 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.

: BA

: 10103

2019-01-07 08:39