Archived
This content is available here strictly for research, reference, and/or recordkeeping and as such it may not be fully accessible. If you work or study at University of Kentucky and would like to request an accessible version, please use the SensusAccess Document Converter.
Abstract
In 2010, M. Studený, R. Hemmecke, and S. Lindner explored a new algebraic description of graphical models, called characteristic imsets. Compared with standard imsets, characteristic imsets have several advantages: they are still unique vector representatives of conditional independence structures, 0-1 vectors, and more intuitive in terms of graphs than standard imsets. After defining a characteristic imset polytope (cim-polytope) as the convex hull of all characteristic imsets with a given set of nodes, they also showed that a model selection in graphical models, which maximizes a quality criterion, can be converted into a linear programming problem over the cim-polytope. However, in general, for a fixed set of nodes, the cim-polytope can have exponentially many vertices over an exponentially high dimension. Therefore, in this paper, we focus on the family of directed acyclic graphs whose nodes have a fixed order. This family includes diagnosis models described by bipartite graphs with a set of m nodes and a set of n nodes for any m, n ∈ Z+. We first consider cim-polytopes for all diagnosis models and show that these polytopes are direct products of simplices. Then we give a combinatorial description of all edges and all facets of these polytopes. Finally, we generalize these results to the cim-polytopes for all Bayesian networks with a fixed underlying ordering of nodes with or without fixed (or forbidden) edges.
Document Type
Article
Publication Date
2015
Digital Object Identifier (DOI)
http://dx.doi.org/10.1137/130933848
Repository Citation
Xi, Jing and Yoshida, Ruriko, "The Characteristic Imset Polytope of Bayesian Networks with Ordered Nodes" (2015). Statistics Faculty Publications. 15.
https://uknowledge.uky.edu/statistics_facpub/15
Notes/Citation Information
Published in SIAM Journal on Discrete Mathematics, v. 29, no. 2, p. 697-715.
First Published in SIAM Journal on Discrete Mathematicsin v. 29, no. 2, published by the Society of Industrial and Applied Mathematics (SIAM). © 2015, Society for Industrial and Applied Mathematics. Unauthorized reproduction of this article is prohibited.