The characteristic imset polytope of Bayesian networks with ordered nodes

DOI10.1137/130933848MaRDI QIDQ3453611zbMATH OpenOpenAlexWikidataFDO

Authors Jing Xi, Ruriko Yoshida

Publication date 27 November 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.0406, https://uknowledge.uky.edu/cgi/viewcontent.cgi?article=1014&context=statistics_facpub

zbMATH Keywords

graphical modelbipartite graphdirected acyclic graphsdiagnosis modelcharacteristic imset polytope

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25)

Abstract: In 2010, M. Studen'y, R. Hemmecke, and S. Linder explored a new algebraic description of graphical models, called characteristic imsets. Compare with standard imsets, characteristic imsets have several advantages: they are still unique vector representative of conditional independence structures, they are 0-1 vectors, and they are 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 (DAGs) whose nodes have a fixed order. This family includes diagnosis models which can be described by Bipartite graphs with a set of $m$ nodes and a set of $n$ nodes for any $$. In this paper, 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.

Recommendations

• Characteristic imsets for learning Bayesian network structure
• On open questions in the geometric approach to structural learning Bayesian nets
• Graphical and algebraic representatives of conditional independence models
• Polyhedral approaches to learning Bayesian networks
• Standard imsets for undirected and chain graphical models

Cites work

• scientific article; zbMATH DE number 1134987 (Why is no real title available?)
• scientific article; zbMATH DE number 2150792 (Why is no real title available?)
• scientific article; zbMATH DE number 3444596 (Why is no real title available?)
• A Bayesian method for the induction of probabilistic networks from data
• A characterization of Markov equivalence classes for acyclic digraphs
• A geometric view on learning Bayesian network structures
• Bayesian model-based diagnosis
• Estimating the dimension of a model
• Lectures on Polytopes
• Simple 0/1-polytopes

Cited in

(2)

• Standard imsets for undirected and chain graphical models
• Toric ideals of characteristic imsets via quasi-independence gluing

This page was built for publication: The characteristic imset polytope of Bayesian networks with ordered nodes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3453611)