Journal
JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH
Volume 58, Issue -, Pages 185-229Publisher
AI ACCESS FOUNDATION
DOI: 10.1613/jair.5203
Keywords
-
Categories
Funding
- UK Medical Research Council [G1002312]
- KU Leuven [SF/14/008]
- UK NC3RS Grant [NC/K001264/1]
- Academy of Finland [251170 COIN]
- Centre of Excellence in Computational Inference Research [276412, 284591]
- Research Funds of the University of Helsinki
- Icelandic Research Fund [152679-051]
- MRC [G1002312] Funding Source: UKRI
Ask authors/readers for more resources
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 Ilayesian networks arguably the most central class of graphical models especially in what is known as the 50010 1)050(1 setting. A successful generic approach to optimal Bayesian network structure learning (BNSL), based on integer programming (IP); is implemented in the GOBNLP System. Despite the recent algoirithmic! 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 elliciemiT 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 N P-hard; (ii) We formalise mid analyse the relationship between three key polytopes underlynig 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available