Structural learning of bayesian networks using statistical constraints

Bayesian Networks are probabilistic graphical models that encode in a compact manner the conditional probabilistic relations over a set of random variables. In this thesis we address the NP-complete problem of learning the structure of a Bayesian Network from observed data. We first present two algorithms from the state of the art: the Max Min Parent Children Algorithm (MMPC), Tsamardinos et al. , which uses statistical tests of independence to restrict the search space for a simple local search algorithm, and a recent complete Branch and Bound technique, de Campos and Ji . We propose in the thesis a novel hybrid algorithm, which uses the constraints given by the MMPC algorithm for reducing the size of the search space of the complete B&B algorithm. Two different statistical tests of independence were implemented: the simple asymptotic test from Tsamardinos et al. and a permutation-based test, more recently proposed by Tsamardinos and Borboudakis . We tested the different techniques for three well known Bayesian Networks in a realistic scenario, with limited memory and data sets with small sample size. Our results are promising and show that the hybrid algorithm exhibits a minimal loss in score, against a considerable gain in computational time, with respect to the original Branch and Bound algorithm, and that none of the two independence tests consistently dominates the other in terms of computational time gain. Le Reti Bayesiane sono modelli grafici probabilistici che cofificano in maniera compatta le relazioni di dipendenza su di un insieme di variabili aleatorie. In questa tesi ci occupiamo del problema NP-Completo di apprendere la struttura di una rete da dei dati osservati. Descriviamo per prima cosa due algoritmi dallo stato dell’arte: l’algoritmo Max Min Parent Children (MMPC) (Tsamardinos et al. [3]) che usa test statistici di indipendenza per restringere lo spazio di ricerca per un semplice algoritmo di ricerca locale, e un algoritmo completo basato su Branch and Bound (de Campos e Ji ). In questa tesi proponiamo un nuovo algoritmo ibrido che usa i vincoli creati da MMPC per ridurre lo spazio di ricerca per l’algoritmo completo B&B. Due diversi test sono stati implementati: un semplice test asintotico da Tsamardinos et al. e un test basato su permutazioni più recentemente proposto da Tsamardinos e Borboudakis. Abbiamo sperimentato le diverse tecniche per tre reti ben conosciute in uno scenario realistico, con memoria limitati e scarsità di dati. I nostri risultati sono promettenti e mostrano una minima perdita nella qualità a fronte di un considerevole guadagno in tempo computazionale, e nessuno dei due test ha dominato l’altro in termini di guadagno di tempo