DROPS

Document

DOI: 10.4230/LIPIcs.CP.2022.37

Structured Set Variable Domains in Bayesian Network Structure Learning

Authors: Fulya Trösser, Simon de Givry, and George Katsirelos

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

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.

Cite as

Fulya Trösser, Simon de Givry, and George Katsirelos. Structured Set Variable Domains in Bayesian Network Structure Learning. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 37:1-37:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.CP.2022.37},
  URN =		{urn:nbn:de:0030-drops-166661},
  doi =		{10.4230/LIPIcs.CP.2022.37},
  annote =	{Keywords: Combinatorial Optimization, Bayesian Networks, Decision Trees}
}

Search Results

Documents authored by Trösser, Fulya

Structured Set Variable Domains in Bayesian Network Structure Learning

Abstract

Cite as

Thanks for your feedback!

Could not send message