Polytopes, Facets and Complexity

Article, Unknown, Preprint English OPEN
Cussens, James ; Järvisalo, Matti ; Korhonen, Janne H. ; Bartlett, Mark (2017)
  • Related identifiers: doi: 10.1613/jair.5203
  • Subject: 90C10 | 113 Computer and information sciences | Computer Science - Artificial Intelligence | Artificial Intelligence

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 effciency 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. Peer reviewed
  • References (8)

    Boyd, S., & Pulleyblank, W. R. (2009). Facet generating techniques. In Cook, W., Lov´asz, L., & Vygen, J. (Eds.), Research Trends in Combinatorial Optimization, Bonn Workshop on Combinatorial Optimization 2008, pp. 33-55. Springer.

    Koivisto, M., & Sood, K. (2004). Exact Bayesian structure discovery in Bayesian networks. Journal of Machine Learning Research, 5, 549-573.

    Koller, D., & Friedman, N. (2009). Probabilistic Graphical Models: Principles and Techniques. MIT Press.

    Malone, B., Kangas, K., J¨arvisalo, M., Koivisto, M., & Myllyma¨ki, P. (2014). Predicting the hardness of learning Bayesian networks. In Brodley, C. E., & Stone, P. (Eds.), Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI 2014), pp. 2460-2466. AAAI Press.

    Mart´ı, R., & Reinelt, G. (2011). The Linear Ordering Problem: Exact and Heuristic Methods in Combinatorial Optimization. Springer.

    Peharz, R., & Pernkopf, F. (2012). Exact maximum margin structure learning of Bayesian networks. In Proceedings of the 29th International Conference on Machine Learning (ICML 2012). icml.cc / Omnipress.

    Sheehan, N., Bartlett, M., & Cussens, J. (2014). Improved maximum likelihood reconstruction of complex multi-generational pedigrees. Theoretical Population Biology, 97, 11-19.

    Silander, T., & Myllyma¨ki, P. (2006). A simple approach for finding the globally optimal Bayesian network structure. In Proceedings of the 22nd Conference on Uncertainty in Artificial Intelligence (UAI 2006), pp. 445-452. AUAI Press.

  • Similar Research Results (2)
  • Metrics
    No metrics available