Apprentissage statistique des modèles de graphes aléatoires exponentiels : théorie et méthodes

Abstract

Les modèles de graphes aléatoires de la famille exponentielle sont flexibles et permettent d’analyser des relations entre des objets. Malheureusement, leur souplesse vient avec un lot de difficultés. Échantillonner des graphes provenant de ces modèles est le plus souvent infaisable, ce qui oblige d’utiliser des techniques comme Métropolis-Hastings. Approximer l’estimateur de vraisemblance maximale est ardu, et l’utilisation de techniques souvent peu connues est nécessaire. En statistique bayésienne, une approximation par à une loi normale de la loi à postériori est tout ce qu’on peut espérer. Dans cette monographie, on commence par montrer comment échantillonner selon ces modèles, puisque cette tâche revient tout au long du document. Il s’en suit une étude détaillée sur l’estimateur de vraisemblance maximale, et puis finalement, on montre comment obtenir une approximation de la loi à postériori dans le cadre bayésien. Un grand effort est apporté à l’approximation par Monte Carlo par chaînes de Markov de l’estimateur de vraisemblance maximale. On y voit les conditions nécessaires et suffisantes à son existence et à son unicité, mais aussi à l’existence et l’unicité de son approximation. On apporte des améliorations aux algorithmes déjà existants pour mieux prendre en compte la théorie et assurer leur robustesse. On termine en démontrant le comportement asymptotique de l’approximation. Les précédentes études ont simplement appliqué la méthode pour ce type de modèle sans s’assurer de la validité de l’application, ce qu’on rectifie.

Exponential random graph models are flexible and allow analyzing relations between any type of objects. Unfortunately, they come with a large number of nuisances. Sampling random graphs is impossible. It left no choice except to use methods such as Metropolis-Hastings. Approximating the maximum likelihood estimator is not trivial, and employing not well- known tools are needed. In Bayesian statistics, a normal law approximation is the closest we can get from the posterior law. In this monograph, we first show how to sample random graphs since it is required for all other techniques. After that, a well-developed study on the maximum likelihood estimator is done. Finally, we show how to approximate the posterior law. A great effort has been made to clarify the Markov chain Monte Carlo approximation of the maximum likelihood estimator. We exhaustively enumerate the conditions for the existence and the uniqueness of the estimator and its approximation. We then bring im- provements to existing algorithms for better reflecting the theory and strengthen robustness. Lastly, we show the asymptotic behaviour of this approximation. Previous studies simply applied the technique without verifying all needed conditions. We pass through all those conditions, and apply modifications when needed.