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 = {Milan Studený and James Cussens}, booktitle = {Proceedings of the Eighth International Conference on Probabilistic Graphical Models}, pages = {499--510}, year = {2016}, editor = {Alessandro Antonucci and Giorgio Corani and Cassio Polpo Campos}}, 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 = {http://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 %J Proceedings of Machine Learning Research %P 499--510 %U http://proceedings.mlr.press %V 52 %W PMLR %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 PY - 2016/08/15 DA - 2016/08/15 ED - Alessandro Antonucci ED - Giorgio Corani ED - Cassio Polpo Campos} ID - pmlr-v52-studeny16 PB - PMLR SP - 499 DP - PMLR EP - 510 L1 - http://proceedings.mlr.press/v52/studeny16.pdf UR - http://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 PMLR 52:499-510

Related Material