Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming

Trösser, Fulya; de Givry, Simon; Katsirelos, George

doi:10.24963/ijcai.2021/584

Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming

Fulya Trösser, Simon de Givry, George Katsirelos

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 4250-4257.

https://doi.org/10.24963/ijcai.2021/584

Keywords

Uncertainty in AI: Bayesian Networks
Constraints and SAT: Constraint Optimization

Abstract

Bayesian networks are probabilistic graphical models with a wide

range of application areas including gene regulatory networks inference, risk

analysis and image processing. Learning the structure of a Bayesian

network (BNSL) from discrete data is known to be an NP-hard task with

a superexponential search space of directed acyclic graphs. In this

work, we propose a new polynomial time algorithm for discovering a

subset of all possible cluster cuts, a greedy algorithm for

approximately solving the resulting linear program, and a generalized

arc consistency algorithm for the acyclicity constraint. We embed

these in the constraint programming-based branch-and-bound solver

CPBayes and show that, despite being suboptimal, they improve

performance by orders of magnitude. The resulting solver also compares

favorably with GOBNILP, a state-of-the-art solver for the BNSL

problem which solves an NP-hard problem to discover each cut and

solves the linear program exactly.

Fulya Trösser, Simon de Givry, and George Katsirelos. 2021. Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 4250–4257. https://doi.org/10.24963/ijcai.2021/584

@inproceedings{ijcai2021p584,
  title     = {Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming},
  author    = {Trösser, Fulya and de Givry, Simon and Katsirelos, George},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {4250--4257},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/584},
  url       = {https://doi.org/10.24963/ijcai.2021/584},
}

TY  - CPAPER
TI  - Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming
AU  - Trösser, Fulya
AU  - de Givry, Simon
AU  - Katsirelos, George
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 4250
EP  - 4257
DO  - 10.24963/ijcai.2021/584
UR  - https://doi.org/10.24963/ijcai.2021/584
ER  -