Closed-form Bayesian inference of graphical model structures by averaging over trees

Schwaller, Loïc  ; Robin, Stéphane  ; Stumpf, Michael

Journal de la société française de statistique, Tome 160 (2019) no. 2, pp. 1-23

Abstract (VO)

We consider the inference of the structure of an undirected graphical model in a Bayesian framework. To avoid convergence issues and highly demanding Monte Carlo sampling, we focus on exact inference. More specifically we aim at achieving the inference with closed-form posteriors, avoiding any sampling step. To this aim, we restrict the set of considered graphs to mixtures of spanning trees. We investigate under which conditions on the priors – on both tree structures and parameters – closed-form Bayesian inference can be achieved. Under these conditions, we derive a fast an exact algorithm to compute the posterior probability for an edge to belong to the tree model using an algebraic result called the Matrix-Tree theorem. We show that the assumption we have made does not prevent our approach to perform well on synthetic and flow cytometry data.

Résumé

Nous nous intéressons à l’inférence de la structure d’un modèle graphique non orienté dans une cadre bayésien. Pour éviter de recourir à des méthodes de Monte-Carlo coûteuses et aux problèmes de convergence associés, nous nous concentrons sur des méthodes exactes. Plus précisément, nous menons l’inférence au moyen de lois a posteriori explicites, évitant ainsi toute étape d’échantillonnage. Dans ce but, nous restreignons l’espace des graphes à des mélanges d’arbres recouvrants. Nous étudions sous quelles condition sur les lois a priori – à la fois sur les arbres et sur les paramètres – une inférence bayésienne exacte peut être menée. Dans ce cadre, nous proposons un algorithme exact et rapide permettant de calculer la probabilité a posteriori pour qu’une arête appartienne au graphe, en utilisant un résultat algébrique connu sous le nom de théorème Arbre-Matrice. Nous montrons que la restriction aux arbres n’empêche pas d’obtenir de bons résultats aussi bien sur des données simulées que sur des données issues de cytométrie de flux.

Détail

Keywords: graphical models, hyper Markov, matrix-tree theorem, spanning trees
Mots-clés : arbres recouvrants, hyper-Markov, modèles graphiques, théorème arbre-matrice