Robust structure learning of Bayesian networks

Bayesian networks mix graphs and probabilities in order to perform reasoning under uncertainty. Their main advocate, Judea Pearl, has been awarded in 2011 the prestigious "ACM Turing Award" because, among other things, "this work not only revolutionized the field of artificial intelligence but also became an important tool for many other branches of engineering and the natural sciences". The graph of a Bayesian network describes the dependence relations between the variables in a domain, while its (probabilistic) parameters encode their strengths. A Bayesian net can be learned from data, be queried to assess the probability of events given observations, and help on decision making. For Bayesian networks to be successful, a crucial, and a very challenging, task that must often be addressed is how to learn the dependency graph (the "structure") from data. This is typically achieved by searching the space of graphs while trying to optimize a score that measures how well a graph fits the data (or other domain knowledge). Structure learning has been, and still is, the subject of intense, cutting-edge, research. At present time, there are very sophisticated algorithms for this task. However, these methods fall short to consider the reliability of their results. Two undesired outcomes are then possible: (i) that there is a structure with a slightly better fit than the others, but which is heavily prone to structural changes under small variations in the data (or personal beliefs); (ii) that there are many structures with similar score that lead to different outcomes in applications, so that the choice among them is highly arbitrary. Problem (i) is severe in applications, such as genomics, where the focus is often on understanding the underlying mechanism that should be modeled by the network. Problem (ii) negatively affects the application of Bayesian networks to prediction as in the data-mining task of "pattern classification", because structures with similar score can, in some cases, lead to quite different prediction accuracy. In this project we aim at developing reliable (or "robust") structure learning methods. Our standpoint is that to achieve reliability, we should have methods able to infer from data, and work with, multiple candidate structures. In this we are inspired by the field of "imprecise" (or "credal") probability, where it is widely acknowledged that robustness is entangled with sets of models (and in particular sets of probability distributions). We will proceed according to the following plan: - We will start by studying current methods for structure learning and the reliability of their results, through *sensitivity analysis of optimal structures*. The idea is to understand which characteristics can be borrowed from them. - We will *develop algorithms that deliver sets of candidate structures*. To this end, we will first deliver new, state-of-the-art, algorithms for the traditional case of (standard) structure learning. Then we will work upon them for our set-based methods using k-best ideas (i.e., finding the k most-probable structures) when the focus is on precise probability, as well as imprecise-probability criteria, such as maximality (which will yield the more structures the less information in the data). - We will *develop robust score functions and models based on imprecise probability*. We will employ decision criteria such as "maximum entropy" and "maximin" in order to produce a single, robust, structure out of the multiple ones when this has to be the case. We will also keep on working with multiple structures and, whenever needed, probabilistically average over them (by "credal model averaging" in the case of maximality, and Bayesian model averaging in the k-best case). - We will *extend the above methods to the case of incomplete data*. Few approaches handle missing data to date. - We will develop these methods with (some) *accuracy guarantees, and we will formally study their complexity*. - We will *specialize robust structure learning to problems of multi-label classification* (where an object can belong to multiple categories). Current methods are still limited in this. - We will *apply robust structure learning to genomic and clinical real data sets*. Working with these data sets is especially relevant, because dealing with incomplete and multi-label data is often unavoidable. Also, by using more reliable procedures, we intend to improve on current methods, yielding results that have pratical impact.