The paper Maximal Ancestral Graph Structure Learning via Exact Search Kari Rantanen, Antti Hyttinen, and Matti Järvisalo of the Constraint Reasoning and Optimization group has been accepted for publications in the proceedings of the 37th Conference on Uncertainty in Artificial Intelligence (UAI 2021), a central international conference in its field.
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.