Polyhedral aspects of score equivalence in Bayesian network structure learning

DOI10.1007/S10107-016-1087-2zbMATH Open1387.90260arXiv1503.00829OpenAlexW2963470896MaRDI QIDQ2364495FDOQ2364495

Authors: James Cussens, Milan Studený, David C. Haws 

Publication date: 21 July 2017

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: This paper deals with faces and facets of the family-variable polytope and the characteristic-imset polytope, which are special polytopes used in integer linear programming approaches to statistically learn Bayesian network structure. A common form of linear objectives to be maximized in this area leads to the concept of score equivalence (SE), both for linear objectives and for faces of the family-variable polytope. We characterize the linear space of SE objectives and establish a one-to-one correspondence between SE faces of the family-variable polytope, the faces of the characteristic-imset polytope, and standardized supermodular functions. The characterization of SE facets in terms of extremality of the corresponding supermodular function gives an elegant method to verify whether an inequality is SE-facet-defining for the family-variable polytope. We also show that when maximizing an SE objective one can eliminate linear constraints of the family-variable polytope that correspond to non-SE facets. However, we show that solely considering SE facets is not enough as a counter-example shows; one has to consider the linear inequality constraints that correspond to facets of the characteristic-imset polytope despite the fact that they may not define facets in the family-variable mode.

Full work available at URL: https://arxiv.org/abs/1503.00829

Recommendations

• Polyhedral approaches to learning Bayesian networks
• On polyhedral approximations of polytopes for learning Bayesian networks
• Learning Bayesian network structure: towards the essential graph by integer linear programming tools
• On open questions in the geometric approach to structural learning Bayesian nets
• Bayesian network structure learning with integer programming: polytopes, facets and complexity

zbMATH Keywords

Bayesian networksbelief networkssupermodular set functioncharacteristic-imset polytopefamily-variable polytopescore equivalent face/facet

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Computational learning theory (68Q32) Combinatorial optimization (90C27) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bayesian network structure learning with integer programming: polytopes, facets and complexity
• Efficient structure learning of Bayesian networks using constraints
• Lectures on Polytopes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Core-based criterion for extreme supermodular functions
• On open questions in the geometric approach to structural learning Bayesian nets
• A geometric view on learning Bayesian network structures
• Characteristic imsets for learning Bayesian network structure
• Learning Bayesian network structure: towards the essential graph by integer linear programming tools
• On polyhedral approximations of polytopes for learning Bayesian networks

Cited In (9)

• Generalized Permutohedra from Probabilistic Graphical Models
• Core-based criterion for extreme supermodular functions
• Bayesian network structure learning with integer programming: polytopes, facets and complexity
• On open questions in the geometric approach to structural learning Bayesian nets
• Polyhedral approach to statistical learning graphical models
• The last dozen of years of or research in Czechia and Slovakia
• The dual polyhedron to the chordal graph polytope and the rebuttal of the chordal graph conjecture
• Towards using the chordal graph polytope in learning decomposable models
• Polyhedral approaches to learning Bayesian networks

Uses Software

• GOBNILP

This page was built for publication: Polyhedral aspects of score equivalence in Bayesian network structure learning

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