Maximal ancestral graph structure learning via exact search
Kari Rantanen, Antti Hyttinen, Matti Järvisalo
Abstract
Generalizing Bayesian networks, maximal ancestral graphs (MAGs) are a theoretically appealing model class for dealing with unobserved variables. Despite significant advances in developing practical exact algorithms for learning score-optimal Bayesian networks, practical exact algorithms for learning score-optimal MAGs have not been developed to-date. We develop here methodology for score-based structure learning of directed maximal ancestral graphs. In particular, we develop local score computation employing a linear Gaussian BIC score, as well as score pruning techniques, which are essential for exact structure learning approaches. Furthermore, employing dynamic programming and branch and bound, we present a first exact search algorithm that is guaranteed to find a globally optimal MAG for given local scores. The experiments show that our approach is able to find considerably higher scoring MAGs than previously proposed in-exact approaches.
BibTeX
@InProceedings{pmlr-v161-rantanen21a,
title = {Maximal ancestral graph structure learning via exact search},
author = {Rantanen, Kari and Hyttinen, Antti and J\"arvisalo, Matti},
booktitle = {Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence},
pages = {1237--1247},
year = {2021},
editor = {de Campos, Cassio and Maathuis, Marloes H.},
volume = {161},
series = {Proceedings of Machine Learning Research},
month = {27--30 Jul},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v161/rantanen21a/rantanen21a.pdf},
url = {https://proceedings.mlr.press/v161/rantanen21a.html},
abstract = {Generalizing Bayesian networks, maximal ancestral graphs (MAGs) are a theoretically appealing model class for dealing with unobserved variables. Despite significant advances in developing practical exact algorithms for learning score-optimal Bayesian networks, practical exact algorithms for learning score-optimal MAGs have not been developed to-date. We develop here methodology for score-based structure learning of directed maximal ancestral graphs. In particular, we develop local score computation employing a linear Gaussian BIC score, as well as score pruning techniques, which are essential for exact structure learning approaches. Furthermore, employing dynamic programming and branch and bound, we present a first exact search algorithm that is guaranteed to find a globally optimal MAG for given local scores. The experiments show that our approach is able to find considerably higher scoring MAGs than previously proposed in-exact approaches.}
}