License: Creative Commons Attribution 4.0 International 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16666/
Go to the corresponding LIPIcs Volume Portal

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

Structured Set Variable Domains in Bayesian Network Structure Learning

pdf-format:
LIPIcs-CP-2022-37.pdf (0.7 MB)

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
Collection: 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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI