M.Sc. Kari Rantanen defends his doctoral thesis Optimization Algorithms for Learning Graphical Model Structures on Wednesday the 8th of December 2021 at 15 o'clock through remote access. His opponent is Professor Peter van Beek (University of Waterloo, Canada) and custos Associate Professor Matti Järvisalo (University of Helsinki). The defence will be held in English. It is possible to follow the defence as a live stream at https://helsinki.zoom.us/j/68883114243.
The thesis of Kari Rantanen is a part of research done in the Department of Computer Science and in the Constraint Reasoning and Optimization research group at the University of Helsinki. His supervisors have been Associate Professor Matti Järvisalo and University Researcher, Docent Antti Hyttinen (University of Helsinki).
Optimization Algorithms for Learning Graphical Model Structures
Graphical models are a versatile machine learning framework enabling efficient and intuitive representations of probability distributions. They can be used for performing various data analysis tasks that would not be feasible otherwise. This is made possible by constructing a graph structure which encodes the underlying dependence structure of the probability distribution. To that end, the field of structure learning develops specialized algorithms which can learn a structure that describes given data well.
This thesis presents advances in structure learning for three different graphical model classes: chordal Markov networks, maximal ancestral graphs, and causal graphs with cycles and latent confounders. Learning structures for these model classes has turned out to be a very challenging task, with the few existing exact methods scaling to much fewer number of random variables compared to more extensively developed methods for Bayesian networks.
Chordal Markov networks are a central class of undirected graphical models. Being equivalent to so-called decomposable models, they are essentially a special case of Bayesian networks. This thesis presents an exact branch-and-bound algorithm and an in-exact stochastic local search for learning chordal Markov network structures. Empirically we show that the branch and bound is at times able to learn provably optimal structures with higher number of variables than competing methods, whereas the local search scales considerably further.
Maximal ancestral graphs are a generalization of Bayesian networks which allow for representing the influence of unobserved variables. This thesis introduces the first exact search algorithm for learning maximal ancestral graphs and a framework for generating and pruning local scores for the search. Empirically we show that the proposed exact search is able to learn higher-quality structures than existing in-exact methods.
Finally, we introduce an exact branch-and-bound algorithm for learning causal graphs in the presence of cycles and latent confounders. Our empirical results show that the presented algorithm is able to learn optimal structures considerably faster than a recent exact method for the problem. We also extend our branch and bound to support interventional data and σ-separation, and show empirically that the algorithm can handle higher number of experimental datasets than the only competing method supporting σ-separation.
Availability of the dissertation
An electronic version of the doctoral dissertation is available on the e-thesis site of the University of Helsinki at http://urn.fi/URN:ISBN:978-951-51-7750-6.
Printed copies will be available on request from Kari Rantanen: kari.rantanen@helsinki.fi.