Advancements in Bayesian network structure learning

You are cordially invited to attend the PhD Dissertation Defense of Mauro SCANAGATTA on Monday, June 4 2018 at 16h30 in room SI-003 (Informatics building)

Abstract:

Bayesian network (BN) is a versatile and well-known probabilistic graphical model with applications in a variety of fields. It is based on: (i) a directed acyclic graph (DAG), where each node represents a random variable and each arc represents a conditional dependency, and (ii) a set of conditional probability distributions defined for each variable given its parents in the graph.

Their graphical nature makes BNs excellent models for representing the complex probabilistic relationships existing in many real problems ranging from bioinformatics to law, from image processing to economic risk analysis.

A main task required to successfully adopt Bayesian networks is to learn their dependency graph, also known as their structure, from data. This is a challenging task, known to be NP-Hard. At the present time in the literature there are very sophisticated algorithms for the task. However, the research in this area is far from complete. Practical application of structure learning often involves particular circumstances (such as missing data or many variables) that severely impact the effectiveness of the existing approaches. My research was therefore intended to identify and overcome these limitations, focusing on the concept of scalability.

This thesis presents several novel approaches and algorithms, each one dedicated to a different aspect of Bayesian network structure learning. Taken together they allow for a remarkable improvement over the existing state-of-the-art, in terms of both applicability and usefulness of this statistical tool.

We show that it is now possible to learn a Bayesian network from datasets containing thousands of variables, and to achieve this goal without constraints on the final structure. As a reference, before the publication of the techniques described in this thesis a BN was applicable only on domains with at most few hundreds of variables.

We further illustrate how to learn a BN in a way that ensures its usefulness for performing inferences by constraining its tree width. Again, in this thesis we outline approaches that improve on the state-of-the-art of two orders of magnitude, opening entire new possibilities and research areas. We show a practical example of this, presenting the first algorithm able to effectively cope with the ubiquitous problem of missing data.

Dissertation Committee:

• Prof. Luca Maria Gambardella, IDSIA, Switzerland (Research Advisor)
• Prof. Marco Zaffalon, IDSIA, Switzerland (Research co-Advisor)
• Prof. Cassio P. De Campos, Queen’s University Belfast, United Kingdom (Research co-Advisor)
• Prof. Fabio Crestani, Università della Svizzera italiana, Switzerland (Internal Member)
• Prof. Evanthia Papadopoulou, Università della Svizzera italiana, Switzerland (Internal Member)
• Prof. Antonio Salmerón Cerdán, Universidad de Almería, Spain (External Member)
• Prof. Fabio Stella, Università degli Studi di Milano-Bicocca, Italy (External Member)