Measures of Variability for Graphical Models
Marco Scutari · Padua Research Archive (University of Padova) · 2011
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.