Inférence probabiliste structurée dans les modèles graphiques probabilistes orientés-objetOù :
LIP6 - salle 101, couloir 25-26 au LIP6 - 4, place Jussieu - 75005 Paris.Quand :
27-01-2012 - 14h Direction de recherche :
Christophe GONZALES
Les modèles graphiques probabilistes (MGP) sont particulièrement utilisés dans les domaines du diagnostique automatique, de la sûreté de fonctionnement et de la maitrise des risques. Pour ces applications, les réseaux bayésiens (RB) sont parmi les MGP les plus populaires, car ils offrent un cadre efficace pour la représentation des connaissances et le raisonnement probabiliste. Toutefois, la modélisation des systèmes complexes avec des RB soulèvent des difficultés, les principaux étant l'impossibilité de réutiliser l'existant et la difficulté pour modéliser des systèmes de grandes tailles. Vers la fin des années 1990, plusieurs extensions des RB allaient lancer le développement des modèles probabilistes du premier ordre (MPPO). Alors que la communauté des chercheurs en IA se concentra sur la fusion de la logique du premier ordre avec les MGP, les difficultés pour modéliser des systèmes complexes à l'aide de RB furent laissées de côtés. Néanmoins, il y a encore de nombreux manques dans les extensions orientés-objet des RB: pouvons nous mieux définir l'héritage ? Comment représenter des concepts tels que le polymorphisme, le prototypage ou encore l'abstraction ? Quelles sont les différences entre les MPPO et les MGP orientés-objet ?
Lorsque les connaissances d'experts sont utilisées pour modéliser un système, l'inférence probabiliste est une des principales applications des RB. Il existe une grande variété d'approches, chacune exploitant un aspect particulier des RB (conditionnement, arbre de jonction, CNF, etc.). Mais, lorsque nous considérons les extensions des RB, il y a peu d'algorithmes dédiés. En effet, la plupart des extensions utilisent l'inférence "groundée", ie. que le modèle est transformé en RB pour y appliquer des algorithmes d'inférence classiques. Parmi les algorithmes dédiés, Structured Variable Elimination (SVE, Pfeffer 1999) exploite les modèles orientés-objet. Il réduit le nombre de calcul en utilisant la répétition structurelle caractéristique des modèles orientés-objet. Toutefois, SVE a des défauts qui empêchent sont utilisation sur des systèmes conçus par des experts dans lesquels il n'y a pas d'incertitude structurelle, ie. dans les mondes fermés.
L'objectif de cette thèse est de développer une modélisation orienté-objet pour les MGP et de généraliser l'inférence structurée. Après une analyse de l'état de l'art, nous proposons une comparaison des différents paradigmes de représentation (orienté-objet, entité relation, premier ordre). Puis nous présentons notre première contribution: une formalisation complète du paradigme orienté-objet pour les MGP. Nous utilisons les modèles probabilistes relationnels (MPR) comme base que nous étendons pour inclure des concepts tel que l'héritage multiple, l'abstraction, le polymorphisme et l'héritage de type.
La deuxième contribution de cette thèse est l'étude et la généralisation de l'algorithme SVE. SVE exploite l'information structurelle représentée par les classes et réduit les calculs redondants. Nous proposons une reformulation de SVE et analysons ses principaux défauts. Puis nous généralisons SVE en étendant la notion d'inférence structurée à notre formalisme. Ceci donne une nouvelle forme d'inférence appelée Inférence Probabiliste Structurée (IPS). Finalement, nous montrons comment l'analyse en d-séparation et l'inférence structurée peuvent être utilisées conjointement pour améliorer les performances de IPS.
La troisième contribution de cette thèse repousse un peu plus loin le concept de l'inférence structurée. Nous exploitons un algorithme de recherche d'isomorphisme de sous graphes pour détecter une répétition de motifs dans un système. Ces motifs définissent une structure de haut niveau, appelée classe dynamique, qui peut être exploitée pour améliorer IPS. Nous proposons une analyse de la complexité du problème et un algorithme approché pour trouver de "bonne" classe dynamique. Nous fournissons des résultats expérimentaux étayant notre approche.
Lionel Torti
