The Chordal Graph Polytope for Learning Decomposable Models

Milan Studeny´; James Cussens

The Chordal Graph Polytope for Learning Decomposable Models

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 zeroone
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.

Original language	English
Title of host publication	Proceedings of the Eighth International Conference on Probabilistic Graphical Models
Editors	Alessandro Antonucci, Giorgio Corani, Cassio Polpo de Campos
Pages	499-510
Number of pages	12
Volume	52
Publication status	Published - 2016

Publication series

Name	Journal of Machine Learning Research: Workshop and Conference Proceedings
ISSN (Electronic)	1938-7228

Bibliographical note

© 2016, The Authors. This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details

Access to Document

studeny16
© 2016, The Authors. This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details
Final published version, 237 KBLicence: Unspecified

http://jmlr.org/proceedings/papers/v52/studeny16.pdfLicence: Unspecified

Cite this

Studeny´, M., & Cussens, J. (2016). The Chordal Graph Polytope for Learning Decomposable Models. In A. Antonucci, G. Corani, & C. Polpo de Campos (Eds.), Proceedings of the Eighth International Conference on Probabilistic Graphical Models (Vol. 52, pp. 499-510). (Journal of Machine Learning Research: Workshop and Conference Proceedings). http://jmlr.org/proceedings/papers/v52/studeny16.pdf

@inproceedings{ddd12175e264433a8032f0add122698a,

title = "The Chordal Graph Polytope for Learning Decomposable Models",

abstract = "This theoretical paper is inspired by an integer linear programming (ILP) approach to learning thestructure of decomposable models. We intend to represent decomposable models by special zeroonevectors, 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 graphpolytope. We introduce a class of clutter inequalities and show that all of them are valid for (thevectors in) the polytope. In fact, these inequalities are even facet-defining for the polytope and wedare to conjecture that they lead to a complete polyhedral description of the polytope. Finally, wepropose an LP method to solve the separation problem with these inequalities for use in a cuttingplane approach.",

author = "Milan Studeny´ and James Cussens",

note = "{\textcopyright} 2016, The Authors. This is an author-produced version of the published paper. Uploaded in accordance with the publisher{\textquoteright}s self-archiving policy. Further copying may not be permitted; contact the publisher for details",

year = "2016",

language = "English",

volume = "52",

series = "Journal of Machine Learning Research: Workshop and Conference Proceedings",

pages = "499--510",

editor = "Antonucci, {Alessandro } and Corani, {Giorgio } and {Polpo de Campos}, {Cassio }",

booktitle = "Proceedings of the Eighth International Conference on Probabilistic Graphical Models",

}

Studeny´, M & Cussens, J 2016, The Chordal Graph Polytope for Learning Decomposable Models. in A Antonucci, G Corani & C Polpo de Campos (eds), Proceedings of the Eighth International Conference on Probabilistic Graphical Models. vol. 52, Journal of Machine Learning Research: Workshop and Conference Proceedings, pp. 499-510. <http://jmlr.org/proceedings/papers/v52/studeny16.pdf>

The Chordal Graph Polytope for Learning Decomposable Models. / Studeny´, Milan; Cussens, James.

Proceedings of the Eighth International Conference on Probabilistic Graphical Models. ed. / Alessandro Antonucci; Giorgio Corani; Cassio Polpo de Campos. Vol. 52 2016. p. 499-510 (Journal of Machine Learning Research: Workshop and Conference Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - The Chordal Graph Polytope for Learning Decomposable Models

AU - Studeny´, Milan

AU - Cussens, James

N1 - © 2016, The Authors. This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details

PY - 2016

Y1 - 2016

N2 - This theoretical paper is inspired by an integer linear programming (ILP) approach to learning thestructure of decomposable models. We intend to represent decomposable models by special zeroonevectors, 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 graphpolytope. We introduce a class of clutter inequalities and show that all of them are valid for (thevectors in) the polytope. In fact, these inequalities are even facet-defining for the polytope and wedare to conjecture that they lead to a complete polyhedral description of the polytope. Finally, wepropose an LP method to solve the separation problem with these inequalities for use in a cuttingplane approach.

AB - This theoretical paper is inspired by an integer linear programming (ILP) approach to learning thestructure of decomposable models. We intend to represent decomposable models by special zeroonevectors, 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 graphpolytope. We introduce a class of clutter inequalities and show that all of them are valid for (thevectors in) the polytope. In fact, these inequalities are even facet-defining for the polytope and wedare to conjecture that they lead to a complete polyhedral description of the polytope. Finally, wepropose an LP method to solve the separation problem with these inequalities for use in a cuttingplane approach.

M3 - Conference contribution

VL - 52

T3 - Journal of Machine Learning Research: Workshop and Conference Proceedings

SP - 499

EP - 510

BT - Proceedings of the Eighth International Conference on Probabilistic Graphical Models

A2 - Antonucci, Alessandro

A2 - Corani, Giorgio

A2 - Polpo de Campos, Cassio

ER -