Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2022.37
URN: urn:nbn:de:0030-drops-166661
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16666/
Trösser, Fulya ; de Givry, Simon ; Katsirelos, George
Structured Set Variable Domains in Bayesian Network Structure Learning
| pdf-format: |
|
Abstract
Constraint programming is a state of the art technique for learning the structure of Bayesian Networks from data (Bayesian Network Structure Learning - BNSL). However, scalability both for CP and other combinatorial optimization techniques for this problem is limited by the fact that the basic decision variables are set variables with domain sizes that may grow super polynomially with the number of random variables. Usual techniques for handling set variables in CP are not useful, as they lead to poor bounds. In this paper, we propose using decision trees as a data structure for storing sets of sets to represent set variable domains. We show that relatively simple operations are sufficient to implement all propagation and bounding algorithms, and that the use of these data structures improves scalability of a state of the art CP-based solver for BNSL.
BibTeX - Entry
@InProceedings{trosser_et_al:LIPIcs.CP.2022.37,
author = {Tr\"{o}sser, Fulya and de Givry, Simon and Katsirelos, George},
title = {{Structured Set Variable Domains in Bayesian Network Structure Learning}},
booktitle = {28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
pages = {37:1--37:9},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-240-2},
ISSN = {1868-8969},
year = {2022},
volume = {235},
editor = {Solnon, Christine},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16666},
URN = {urn:nbn:de:0030-drops-166661},
doi = {10.4230/LIPIcs.CP.2022.37},
annote = {Keywords: Combinatorial Optimization, Bayesian Networks, Decision Trees}
}
| Keywords: | Combinatorial Optimization, Bayesian Networks, Decision Trees | |
| Seminar: | 28th International Conference on Principles and Practice of Constraint Programming (CP 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 23.07.2022 | |
| Supplementary Material: | Software (Source Code): https://gkatsi.github.io/elsa-cp22.tar.gz |
