Bayesian network structure learning with integer programming: polytopes, facets and complexity
From MaRDI portal
Abstract: The challenging task of learning structures of probabilistic graphical models is an important problem within modern AI research. Recent years have witnessed several major algorithmic advances in structure learning for Bayesian networks---arguably the most central class of graphical models---especially in what is known as the score-based setting. A successful generic approach to optimal Bayesian network structure learning (BNSL), based on integer programming (IP), is implemented in the GOBNILP system. Despite the recent algorithmic advances, current understanding of foundational aspects underlying the IP based approach to BNSL is still somewhat lacking. Understanding fundamental aspects of cutting planes and the related separation problem( is important not only from a purely theoretical perspective, but also since it holds out the promise of further improving the efficiency of state-of-the-art approaches to solving BNSL exactly. In this paper, we make several theoretical contributions towards these goals: (i) we study the computational complexity of the separation problem, proving that the problem is NP-hard; (ii) we formalise and analyse the relationship between three key polytopes underlying the IP-based approach to BNSL; (iii) we study the facets of the three polytopes both from the theoretical and practical perspective, providing, via exhaustive computation, a complete enumeration of facets for low-dimensional family-variable polytopes; and, furthermore, (iv) we establish a tight connection of the BNSL problem to the acyclic subgraph problem.
Recommendations
- Polyhedral approaches to learning Bayesian networks
- Learning Bayesian network structure: towards the essential graph by integer linear programming tools
- Polyhedral aspects of score equivalence in Bayesian network structure learning
- Bayesian network structure learning: hybridizing complete search with independence tests
- Integer linear programming for the Bayesian network structure learning problem
Cited in
(13)- Approximate structure learning for large Bayesian networks
- Polyhedral aspects of score equivalence in Bayesian network structure learning
- Asymmetric hidden Markov models
- Learning Bayesian network structure: towards the essential graph by integer linear programming tools
- Polyhedral approaches to learning Bayesian networks
- scientific article; zbMATH DE number 7626781 (Why is no real title available?)
- Efficient Sampling and Structure Learning of Bayesian Networks
- Integer linear programming for the Bayesian network structure learning problem
- MaxSAT-based cutting planes for learning graphical models
- Structural learning of mixed noisy-or Bayesian networks
- Automatically finding the right probabilities in Bayesian networks
- Integer programming for learning directed acyclic graphs from nonidentifiable Gaussian models
- VC dimension and inner product space induced by Bayesian networks
This page was built for publication: Bayesian network structure learning with integer programming: polytopes, facets and complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2962570)
