Modèles Relationnels Probabilistes et Incertitude de Références

 Contributions

Nous distinguons trois types de contributions dans cette thèse : des contributions théoriques, expérimentales et logicielles. 

Contributions théoriques

Nous proposons dans cette thèse plusieurs contributions théoriques. La première prend la forme d’une explication détaillée des modèles d’intérêt, détaillant des points laissés même obscurs dans la littérature. Cette contribution comprend également certaines propositions comme autant de choix qui ne sont pas faits dans les articles originaux, p.ex. la définition d’un a priori sur les fonctions de partition pour l’évaluation des modèles, et la description de règles de calculs des distributions de probabilités dans les instanciations de ceux-ci. En outre, cette contribution comprend l’identification de limites pour ces modèles. Notre seconde contribution théorique correspond aux deux extensions que nous proposons pour corriger les limites identifiées préalablement et aux stratégies de partitionnement que nous proposons, allant au-delà de ce qu’il est possible de faire dans les modèles historiques. Nous nous focalisons notamment sur l’utilisation de fonctions de partitionnement relationnel, permettant de grouper conjointement les ensembles d’entités impliqués dans une même association, permettant ainsi de profiter de l’information topologique des associations elles-mêmes, non exploitée sinon. Nous proposons également un algorithme d’apprentissage de structure glouton pour l’apprentissage de nos extensions. Cette contribution a mené à deux publications : la première a été présentée lors de la conférence FLAIRS 27 en 2014 [41] ; la seconde a été présentée lors de la conférence IJCNN 2015 [42]. Enfin, pour faire suite à notre recherche d’algorithmes de partitionnement relationnel et après avoir considéré les avantages et inconvénients de plusieurs méthodes, nous avons découvert une équivalence entre deux familles de méthodes, à savoir d’une part les méthodes de factorisation non négatives régularisées par des matrices laplaciennes, et d’autre part les méthodes de coupes minimales dans des graphes augmentés d’arcs de similarités. Cette équivalence permet d’envisager un partitionnement relationnel présentant la précision de calcul des méthodes de la première famille, avec les temps de calcul rapides de certaines méthodes de la seconde. Cette contribution a également conduit à la publication d’un article présenté lors de la conférence ESANN 2015 [40]. 1.2.2 Contributions expérimentales Nous apportons dans cette thèse des validations expérimentales pour les contributions théoriques énoncées précédemment. Ces contributions expérimentales permettent ainsi de confirmer l’intérêt de réaliser du partitionnement relationnel pour apprendre des modèles plus fidèles aux données, tant sur le plan de l’apprentissage de paramètres que de l’apprentissage de structure. De plus, les différents algorithmes de partitionnement quenous utilisons au fur et à mesure des expériences, après avoir constaté les limites des résultats précédemment obtenus, nous permettent de comparer leurs comportements et de mesurer leur adéquation dans le contexte d’un apprentissage de modèles relationnels probabilistes avec incertitude de références. 

Contributions logicielles

Les contributions de cette thèse comprennent enfin des valorisations logicielles importantes. Aucun outil n’existant pour l’apprentissage de structure des modèles relationnels probabilistes et leurs extensions, nous avons dû construire un cadre logiciel permettant de définir ces modèles, de raisonner avec eux, et de les apprendre à partir de données. Ce travail a mené à la réalisation d’une bibliothèque complète, appelée PILGRIM Relational, où nous proposons la majorité des fonctionnalités de la littérature sur les modèles relationnels probabilistes, ainsi que l’ensemble des fonctionnalités provenant de nos contributions théoriques et expérimentales. La réalisation de ce projet s’est faite en collaboration avec d’autres membres de l’équipe de recherche et nous parlerons essentiellement dans ce manuscrit de notre propre apport, comprenant la définition de l’architecture globale du projet, de nombreuses implémentations des concepts de base, ainsi que l’implémentation des extensions avec incertitude de référence et tous les concepts associés. 

Organisation du manuscrit

Ce manuscrit est organisé de la façon suivante : Le chapitre 2 présente les concepts généraux qui sont nécessaires à la compréhension de cette thèse. Nous commençons par décrire les concepts liés à la définition de domaines de données mono relationnels, ou tabulaires, c.-à-d. ne comportant qu’une seule relation. Nous définissons ensuite les concepts de dépendance fonctionnelle et probabiliste avant d’aborder l’hypothèse i.i.d. faite dans les algorithmes d’apprentissage non relationnels. Nous définissons ensuite les réseaux bayésiens, le raisonnement à partir de ces modèles ainsi que l’apprentissage de ceux-ci à partir de données. Puis, nous abordons les problèmes que pose la contrainte i.i.d. et motivons le besoin d’aller vers des solutions multi relationnelles. Nous définissons alors les concepts permettant de décrire des jeux de données relationnels et finissons par définir un premier modèle de réseaux bayésiens étendus, les réseaux bayésiens orientés objet, mais donnons les limites de ces modèles justifiant le besoin des modèles relationnels probabilistes, que nous définissons également ainsi que les principes pour y raisonner et en réaliser l’apprentissage à partir de données. Le chapitre 3 présente en détail les modèles relationnels probabilistes dans le contexte d’incertitude de références. Ce chapitre donne des définitions précises des concepts impliqués spécifiques à cette extension et explicite même des points non détaillés dans la littérature par des définitions supplémentaires ainsi que divers exemples. Les notions de variables sélecteur et leur lien avec les fonctions de partition sont des points très importants de ce chapitre et font l’objet d’une attention particulière. Comme pour leur version de base, le raisonnement et l’apprentissage à partir de données pour cette extension sont également détaillés et nous finissons par présenter les différentes limites de ces modèles et de leur apprentissage, tant sur le plan des contraintes inhérentes aux fonctions de partition, où nous regrettons l’impossibilité d’utiliser des méthodes de copartitionnement, que celles induites par le biais de représentation des structures. Le chapitre 4 s’appuie sur les limites énoncées au chapitre précédent relatives aux fonctions de partition et notamment à l’absence de support des méthodes de copartitionnement. Nous y présentons ainsi diverses méthodes faisant partie de la famille que nous appelons partitionnement relationnel permettant de grouper simultanément les différents ensembles d’entités impliqués dans un type d’association. Trois types d’algorithmes nous intéressent particulièrement dans ce chapitre, à savoir les méthodes de factorisation non négatives de matrices, les méthodes de coupe de graphe, ainsi que les méthodes de détection de communautés basées sur l’optimisation de critères de modularité. Le chapitre se termine par notre contribution relative à l’équivalence des méthodes de factorisation de matrices binaires avec régularisation laplacienne et des méthodes de coupe minimale dans un graphe augmenté d’informations de similarités. Le chapitre 5 est le premier à proposer un nouveau type de modèle relationnel probabiliste, visant à effacer les limites des modèles du chapitre 3 relatives aux contraintes sur les fonctions de partition. Ce modèle nous sert principalement à confirmer l’hypothèse que nous faisons au sujet de l’importance d’utiliser des méthodes de partitionnement relationnel pour l’apprentissage de modèles avec incertitude de références. Après avoir décrit cette nouvelle extension, nous réalisons des expériences permettant de confirmer que l’apprentissage de modèles avec des méthodes de partitionnement relationnel obtient de meilleurs résultats que l’apprentissage de modèles selon l’approche historique décrite dans la littérature, utilisant le produit cartésien d’un ensemble d’attributs pris dans le type d’entité concerné pour chaque fonction de partitions. Le chapitre 6 va plus loin et contient une nouvelle proposition d’extension plus complète des modèles du chapitre 3 visant à corriger l’ensemble des problèmes énoncés dans ce chapitre. Cette nouvelle extension, appelée modèles relationnels probabilistes avec incertitude de clusters, est définie de façon précise et nous abordons une nouvelle fois les principes de raisonnement et d’apprentissage dans ces modèles. Nous confirmons l’intérêt de ce modèle par des expérimentations, à la fois sur des données synthétiques, et sur des données réelles. Pour finir, le chapitre 7 présente les contributions logicielles faites durant cette thèse dans le but de valoriser le travail de compréhension des modèles existants avant nous ainsi que nos contributions, et pour être en mesure de réaliser les diverses expériences des chapitres précédents. Nous énumérons l’ensemble des solutions existantes de programmation probabiliste puis nous identifions leurs propriétés et exhibons l’absence d’outils permettant de réaliser de l’apprentissage de structure de modèles relationnels probabilistes, motivant la création de notre propre outil. Nous abordons ainsi ensuite le sujet principal du chapitre, à savoir le projet PILGRIM, et plus particulièrement sa brique relationnelle à laquelle nous avons contribué de façon conséquente. Nous présentons les différentes parties constituant cet outil et donnons divers points de documentation simplifiés, avec quelques diagrammes de classe de haut niveau.