Vai ai contenuti. | Spostati sulla navigazione | Spostati sulla ricerca | Vai al menu | Contatti | Accessibilità

logo del sistema bibliotecario dell'ateneo di padova

Venco, Francesco (2012) Structural learning of bayesian networks using statistical constraints. [Magistrali biennali]

Full text disponibile come:

[img]
Preview
PDF
1026Kb

Abstract

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

Item Type:Magistrali biennali
Corsi di Diploma di Laurea:Scuola di Ingegneria > Ingegneria Informatica
Scuola di Ingegneria > Ingegneria Informatica
Uncontrolled Keywords:Bayesian Network, machine learning, artificial intelligence
Subjects:Area 09 - Ingegneria industriale e dell'informazione > ING-INF/05 Sistemi di elaborazione delle informazioni
Codice ID:39776
Relatore:Badaloni, Silvana
Correlatore:Sambo, Francesco
Data della tesi:23 April 2012
Biblioteca:Polo di Ingegneria > Biblioteca di Ingegneria dell'Informazione e Ingegneria Elettrica "Giovanni Someda"
Tipo di fruizione per il documento:on-line per i full-text

Solo per lo Staff dell Archivio: Modifica questo record