The Chordal Graph Polytope for Learning Decomposable Models

Milan Studený, James Cussens
Proceedings of the Eighth International Conference on Probabilistic Graphical Models, PMLR 52:499-510, 2016.

Abstract

This theoretical paper is inspired by an \em integer linear programming (ILP) approach to learning the structure of \em decomposable models. We intend to represent decomposable models by special zero-one vectors, named \em 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 \em chordal graph polytope. We introduce a class of \em 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 \em separation problem with these inequalities for use in a cutting plane approach.

Cite this Paper

BibTeX
@InProceedings{pmlr-v52-studeny16, title = {The Chordal Graph Polytope for Learning Decomposable Models}, author = {Studený, Milan and Cussens, James}, booktitle = {Proceedings of the Eighth International Conference on Probabilistic Graphical Models}, pages = {499--510}, year = {2016}, editor = {Antonucci, Alessandro and Corani, Giorgio and Campos}, Cassio Polpo}, volume = {52}, series = {Proceedings of Machine Learning Research}, address = {Lugano, Switzerland}, month = {06--09 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v52/studeny16.pdf}, url = {https://proceedings.mlr.press/v52/studeny16.html}, abstract = {This theoretical paper is inspired by an \em integer linear programming (ILP) approach to learning the structure of \em decomposable models. We intend to represent decomposable models by special zero-one vectors, named \em 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 \em chordal graph polytope. We introduce a class of \em 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 \em separation problem with these inequalities for use in a cutting plane approach.} }
Endnote
%0 Conference Paper %T The Chordal Graph Polytope for Learning Decomposable Models %A Milan Studený %A James Cussens %B Proceedings of the Eighth International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2016 %E Alessandro Antonucci %E Giorgio Corani %E Cassio Polpo Campos} %F pmlr-v52-studeny16 %I PMLR %P 499--510 %U https://proceedings.mlr.press/v52/studeny16.html %V 52 %X This theoretical paper is inspired by an \em integer linear programming (ILP) approach to learning the structure of \em decomposable models. We intend to represent decomposable models by special zero-one vectors, named \em 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 \em chordal graph polytope. We introduce a class of \em 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 \em separation problem with these inequalities for use in a cutting plane approach.
RIS
TY - CPAPER TI - The Chordal Graph Polytope for Learning Decomposable Models AU - Milan Studený AU - James Cussens BT - Proceedings of the Eighth International Conference on Probabilistic Graphical Models DA - 2016/08/15 ED - Alessandro Antonucci ED - Giorgio Corani ED - Cassio Polpo Campos} ID - pmlr-v52-studeny16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 52 SP - 499 EP - 510 L1 - http://proceedings.mlr.press/v52/studeny16.pdf UR - https://proceedings.mlr.press/v52/studeny16.html AB - This theoretical paper is inspired by an \em integer linear programming (ILP) approach to learning the structure of \em decomposable models. We intend to represent decomposable models by special zero-one vectors, named \em 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 \em chordal graph polytope. We introduce a class of \em 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 \em separation problem with these inequalities for use in a cutting plane approach. ER -
APA
Studený, M. & Cussens, J.. (2016). The Chordal Graph Polytope for Learning Decomposable Models. Proceedings of the Eighth International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 52:499-510 Available from https://proceedings.mlr.press/v52/studeny16.html.

Related Material