Measures of Variability for Graphical Models

In recent years, graphical models have been successfully applied in several different disciplines, including medicine, biology and epidemiology. This has been made possible by the rapid evolution of structure learning algorithms, from constraint-based ones to score-based and hybrid ones. The main goal in the development of these algorithms has been the reduction of the number of either independence tests or score comparisons needed to learn the structure of the Bayesian network. In most cases the characteristics of the learned networks have been studied using a small number of reference data sets as benchmarks, and differences from the true structure heve been measured with purely descriptive measures such as Hamming distance. This approach to model validation is not possible for real world data sets, as the true structure of their probability distribution is not known. An alternative is provided by the use of either parametric or nonparametric bootstrap. By applying a learning algorithm to a sufficiently large number of bootstrap samples it is possible to obtain the empirical probability of any feature of the resulting network, such as the structure of the Markov Blanket of a particular node. The fundamental limit in the interpretation of the results is that the “reasonable” level of confidence for thresholding depends on the data and the learning algorithm. In this thesis we extend the aforementioned bootstrap-based approach for the in- ference on the structure of a Bayesian or Markov network. The graph representing the network structure and its underlying undirected graph (in the case of Bayesian networks) are modelled using a multivariate extension of the Trinomial and Bernoulli distributions; each component is associated with an arc. These assumptions allow the derivation of exact and asymptotic measures of the variability of the network structure or any of its parts. These measures are then applied to some common learning strate- gies used in literature using the implementation provided by the bnlearn R package implemented and maintained by the author.

Negli ultimi anni i modelli grafici, ed in particolare i network Bayesiani, sono entrati nella pratica corrente delle analisi statistiche in diversi settori scientifici, tra cui medi cina e biostatistica. L’uso di questo tipo di modelli è stato reso possibile dalla rapida evoluzione degli algoritmi per apprenderne la struttura, sia quelli basati su test statistici che quelli basati su funzioni punteggio. L’obiettivo principale di questi nuovi algoritmi è la riduzione del numero di modelli intermedi considerati nell’apprendimento; le loro caratteristiche sono state usualmente valutate usando dei dati di riferimento (per i quali la vera struttura del modello è nota da letteratura) e la distanza di Hamming. Questo approccio tuttavia non può essere usato per dati sperimentali, poiché la loro struttura probabilistica non è nota a priori. In questo caso una valida alternativa è costituita dal bootstrap non parametrico: apprendendo un numero sufficientemente grande di modelli da campioni bootstrap è infatti possibile ottenere una stima empirica della probabilità di ogni caratteristica di interesse del network stesso. In questa tesi viene affrontato il principale limite di questo secondo approccio: la difficoltà di stabilire una soglia di significatività per le probabilità empiriche. Una possibile soluzione è data dall’assunzione di una distribuzione Trinomiale multivariata (nel caso di grafi orientati aciclici) o Bernoulliana multivariata (nel caso di grafi non orientati), che permette di associare ogni arco del network ad una distribuzione mar ginale. Questa assunzione permette di costruire dei test statistici, sia asintotici che esatti, per la variabilità multivariata della struttura del network nel suo complesso o di una sua parte. Tali misure di variabilità sono state poi applicate ad alcuni algoritmi di apprendimento della struttura di network Bayesiani utilizzando il pacchetto R bnlearn, implementato e mantenuto dall’autore.