Soutenance mémoire
Introduction de la négation et hypothèse du monde clos
Nous nous intéressons à l’introduction d’une forme de négation basique mais néanmoins fondamentale, la négation atomique. Cette négation porte uniquement sur un atome : par exemple ¬sur (A,B) (« l’entité A n’est pas sur l’entité B », le symbole ¬ exprimant la négation), mais pas sur une forme plus structurée comme ¬(sur (A,B)∧sur (C,D)) (il est faux que : « A est sur B et C est sur D »). Elle nous permet d’exprimer des connaissances de la forme « cette entité n’a pas cette propriété », « cette relation n’apparaît pas entre ces entités » . . . On distingue généralement deux grandes façons d’interpréter la négation. En effet, si nous posons une question de la forme « ¬sur (A,B) ? » (« est-ce que l’entité A n’est pas sur l’entité B »), le symbole ¬ peut être interprété de différentes manières. Il peut signifier que :
1. La connaissance « sur (A,B) » ne peut pas être prouvée.
2. La connaissance « ¬sur (A,B) » peut être prouvée.
La première affirmation correspond à l’hypothèse du monde clos [Reiter, 1977], qui est communément faite dans les bases de données. Faire l’hypothèse du monde clos correspond à supposer une connaissance complète du monde. Ainsi, on se contente d’une description partielle du monde : seules les informations positives (vraies) sont spécifiées. C’est-à-dire que l’absence d’une information est automatiquement traduite par sa négation. Intuitivement, cela signifie que bien que la définition d’une propriété soit limitée à la liste des individus la satisfaisant, il est possible de dire pour tout individu s’il a ou non la propriété. La connaissance ¬sur (A,B) est alors interprétée par « sur (A,B) n’apparaît pas dans la BD », ou plus généralement « sur (A,B) ne peut pas être déduit de la BD ». D’un point de vue bases de données, ce choix est motivé par la simplification de la représentation d’un côté et les performances de l’autre [Bidoit, 1991]. Par exemple, pour définir une propriété, il semble plus naturel et il est plus économe de donner la liste des individus satisfaisant cette propriété plutôt que d’énumérer tous les individus et d’indiquer pour chacun d’eux s’il satisfait ou non la propriété. Prenons le cas de la propriété « être un cinéma de Montpellier (noté estCinemaMTP) ». Supposer une connaissance complète pour cette propriété semble raisonnable ; tous les cinémas n’apparaissant pas dans la liste des cinémas de Montpellier, c’est-à-dire tous les V tels que Localisations(V,Montpellier) n’est pas un atome de la BD CINEMA, sont considérés comme ne se situant pas à Montpellier. Ainsi d’un côté la représentation des données est simplifiée puisque seuls les cinémas situés à Montpellier sont représentés, et de l’autre les mécanismes de réponse sont optimisés. Il est néanmoins à noter que, si cette hypothèse semble naturelle en bases de données, il est impossible en logique classique (plus généralement pour toute logique monotone) d’inférer des informations négatives à partir d’informations positives. Il est par exemple impossible d’inférer ¬estCinemaMTP(A) si l’information est CinemaMTP(A) n’apparaît pas dans la base. Différentes logiques non-monotones ont été proposées pour traduire l’hypothèse du monde clos, comme la logique des défauts ; pour être capable d’inférer des informations négatives à partir d’une description incomplète, on a recours à des règles des défauts de la forme : « s’il est cohérent de supposer qu’une entité ne satisfait pas une propriété, alors inférer que cette entité ne satisfait pas la propriété » (voir [Apt et Bol, 1994] pour plus de détails concernant les logiques non-monotones).
Les logiques de description et les graphes conceptuels
Nous mentionnons brièvement deux familles de langages utilisant des ontologies : les Logiques de Description (LD) et les Graphes Conceptuels (GC). Les LD [Baader et al., 2003] sont des fragments décidables de la logique du premier ordre. Une base de connaissance en LD est composée de deux parties différentes : la TBox (elle représente une ontologie de niveau 2 ou 3), composante intensionnelle qui définit les connaissances générales, et la ABox (elle représente la base de faits), composante extensionnelle, qui définit les données connues sur des individus. Les GC [Sowa, 1976][Sowa, 1984][Chein et Mugnier, 2009] sont un formalisme de représentation par graphes ayant une traduction en logique du premier ordre. Une base de connaissances en GC est également composée de deux parties différentes : le support (il représente une ontologie de niveau 2, qui pourra être enrichie par l’ajout de règles et de contraintes, ce qui conduira alors à une ontologie de niveau 3), qui décrit les ensembles de concepts et relations servant à étiqueter les sommets des graphes ainsi que leur ordonnancement par une relation de spécialisation/généralisation, et la base de faits, décrite par un ensemble de graphes bipartis étiquetés (une des classes de sommets représente les concepts et l’autre les relations entre ces concepts ou des propriétés sur ces concepts). Ces deux familles de langages utilisant des ontologies sont issues des réseaux sémantiques (voir [Woods, 1975] par exemple), et ont visé à partir des années 80 des objectifs différents mais complémentaires : les LD se sont concentrées sur les raisonnements par classification dans une ontologie (recherche des éléments plus généraux ou plus spécifiques qu’un élément donné) ; l’idée générale étant d’associer des descriptions complexes à des entités – des concepts par exemple – et de se poser le problème de classifier de nouveaux concepts au sein d’un ensemble de concepts précédemment décrits ou de déterminer si un ensemble de concepts est satisfiable. Les LD ont ainsi développé des types d’axiomes ontologiques pour lesquels ces problèmes sont décidables et peuvent même se résoudre de façon efficace. En revanche, elles ne traitent que des cas limités de requêtes et règles d’inférence. Les GC se sont quant à eux concentrés sur la déduction entre faits, problème fondamental pour résoudre le problème de calcul des réponses à une requête conjonctive et la prise en compte de règles d’inférence dans les raisonnements. Dans leur version de base, ils permettent l’expression de n’importe quelle requête conjonctive, mais ne disposent que d’expressions limitées d’axiomes ontologiques. Ces dernières années, les objectifs des LD et des GC ont eu tendance à se rejoindre, notamment pour traiter le problème de l’interrogation du web sémantique (voir [Berners-Lee et al., 2001] par exemple) : les LD ont cherché à simplifier leurs axiomes ontologiques pour pouvoir traiter des requêtes conjonctives en limitant la hausse de complexité, tandis que les GC, qui englobent naturellement les requêtes conjonctives, ont cherché à exprimer des axiomes ontologiques plus riches à l’aide des règles d’inférence de leur formalisme.
Problèmes équivalents au problème IRC ¬
Le problème IRC ¬ est équivalent à deux problèmes fondamentaux en logique du premier ordre : le problème de déduction de formules et le problème d’implication de clauses. Le problème de déduction est un problème de base en logique classique : « étant données deux formules f et g , f se déduit-elle de g (noté g ` f ) ? » (c’est-à-dire intuitivement est-ce que les informations contenues dans f se trouvent dans g ?). Par la suite, nous considérons la restriction de ce problème à des formules de FOL{∃,∧,¬a}, et nous l’appellerons simplement Déduction. Ce problème est équivalent au problème IRC ¬ en bases de données, comme le montrent les réductions polynomiales naturelles vues en 2.3.1 ; nous manipulons les mêmes objets sous des formes différentes, et nous posons la même question. Nous avons alors la propriété suivante : soient q1 et q2 deux RC ¬, et g et f les formules de FOL{∃,∧,¬a} qui leur sont associées, q1 v q2 si et seulement si g ` f (ceci peut se prouver par exemple en s’appuyant sur le théorème 2.19 en section 2.4.1). Le problème Déduction est également équivalent à un autre problème fondamental en programmation logique inductive, le problème d’implication de clauses (sans fonction, comme dans [Gottlob, 1987]) : « étant données deux clauses c1 et c2, c1 implique-t-elle c2, c’est-à-dire c2 se déduit-elle de c1 ? » L’équivalence est immédiate : si nous prenons la négation des formules de FOL{∃,∧,¬a}, nous obtenons directement des clauses dans un autre fragment de la logique du premier ordre, le fragment universel disjonctif, noté FOL{∀,∨,¬a}. L’équivalence provient de ce que g ` f si et seulement si ¬f ` ¬g .
Construction incrémentale des complétions
Le but de la construction incrémentale des complétions est de ne pas avoir à parcourir l’ensemble des complétions totales pour répondre si oui ou non F se déduit de G ; ainsi on cherche un ensemble de complétions partielles couvrant l’ensemble des complétions totales. Cette construction est directement liée à la condition nécessaire pour la déduction suivante : on a G ` F si et seulement si (1) il existe un homomorphisme h de F p dans G p , et (2) pour chaque sommet relation négatif −r (t1,…,tk) de F, on a G 0 ` F, où G 0 est la complétion de G obtenue par l’ajout de +r (h(t1),…,h(tk)). L’algorithme proposé explore l’espace de recherche menant de G à ses complétions totales par ce qui « ressemble » à un parcours en largeur 7 . Nous employons le terme « ressembler » car nous montrons au chapitre 4 qu’une complétion peut être parcourue plusieurs fois. On peut voir cet espace de recherche (cf. [Leclère et Mugnier, 2007]) comme partiellement ordonné par la relation d’inclusion « sous-graphe de » (notée ⊆), G formant la racine de l’arbre de recherche. Tous les homomorphismes h1,…,hn de F p dans G p sont calculés, et une branche est construite pour chacun d’eux à partir de la racine. Pour chaque branche hi et pour chaque sommet relation négatif −r (t1,…,tk) de F, on construit un nœud Ni,j à partir de hi , correspondant à une complétion obtenue de G par l’ajout de +r (hi(t1),…,hi(tk)) (cf. figure 2.8). L’idée est que toute complétion de G contient soit −r (hi(t1),…,hi(tk)), soit +r (hi(t1),…,hi(tk)). Dans le premier cas, l’homomorphisme hi peut être étendu. Dans le deuxième cas, il reste à prouver que F se déduit de G ∪{+r (hi(t1),…,hi(tk))}. Chaque nœud Ni,j dont la complétion associée est inconsistante (le dernier sommet relation ajouté est contradictoire avec un sommet relation négatif de G) est marqué comme « contenu » (il « étend » l’homomorphisme hi) et chaque nœud Ni,j dont la complétion associée est redondante (le dernier sommet relation ajouté est égal à un sommet relation positif de G) est marqué comme « terminal » (il contredit l’homomorphisme hi). S’il existe une branche (partant de la racine) valide, c’est-à-dire que pour toutes complétions G 0 associées aux nœuds se trouvant dans le sous-arbre de racine hi, alors G ` F. S’il existe un nœud Ni,j tel qu’au moins un nœud de chaque branche partant de Ni,j est marqué « terminal » (aucun homomorphisme ne vérifie la condition nécessaire susmentionnée), alors G 6` F. Sinon, les nœuds non marqués sont étendus en prenant en compte les nouveaux homomorphismes et le processus recommence.
Influence des différents paramètres sur la difficulté
La difficulté d’une instance dépend des valeurs des paramètres choisies pour la génération des graphes. Dans cette partie, nous déterminons empiriquement l’influence des paramètres sur la difficulté de résolution. Notons que, pour une instance I, plus l’espace de recherche exploré afin de résoudre I est grand plus le nombre d’homomorphismes calculés est grand (puisqu’au moins un test d’homomorphisme est effectué à chaque nœud de l’espace de recherche), et donc plus l’instance sera difficile. Intuitivement, on s’attend à ce qu’en moyenne plus la taille de l’espace de recherche menant de G à ses complétions totales est grande (c’est à-dire plus le nombre de complétions totales de G est grand), plus l’arbre de recherche exploré a de chances d’être grand. Rappelons qu’un graphe G a 2(nG ) k×|VG | complétions totales possibles, ce qui est équivalent avec nos paramètres à 2 (nbTG ) k×nbE (en supposant que la taille du vocabulaire de complétion associé soit égale à nbE). Ainsi en augmentant la valeur des paramètres nbTG , k et nbE, le nombre de complétions totales possibles va croître (de façon exponentielle), ce qui nous laisse supposer que la difficulté de l’instance augmentera également. D’un autre côté, les paramètres c et neg semblent indépendants des autres paramètres : pour ce qui est du pourcentage de négation, on s’attend à ce que les instances les plus difficiles (pour toute valeur des autres paramètres) soient caractérisées par une valeur de 50%. En effet dans le cas contraire, par exemple supposons une difficulté maximum pour neg = 40%, il suffirait d’inverser les signes des sommets relations de F et G afin de se retrouver avec neg = 60% qui serait par hypothèse plus facile à résoudre (cf. figure 3.3, nous obtenons F2 après inversion des signes des sommets relations de F1).
Influence des densités des graphes source et cible
Nous avons commencé par déterminer l’influence des densités des graphes source et cible sur la difficulté du problème car ces paramètres sont primordiaux dans le processus de résolution. En effet, si nous fixons tous les autres paramètres pour F et G et que nous considérons un graphe source très dense et un graphe cible peu dense, l’instance est triviale, nous concluons directement à un échec (nous pouvons par exemple utiliser la propriété 2.2 sur les sous-graphes purs : comme dans ce cas un sous-graphe pur F 0 de F est grand, il n’y a généralement pas d’homomorphisme compatible de F 0 dans G). De même si nous considérons un graphe source peu dense et un graphe cible très dense, nous pouvons conclure à un succès sans compléter G (il y a généralement un homomorphisme de F dans G). Nous avons alors étudié l’influence des densités des graphes source et cible sur la difficulté en fixant nbTS = nbTC = 8, c = 0%, nbE = 1, k = 2 et neg = 50%. Dans la suite, pour neg = 50%, nous considérons toujours les densités pour lesquellesle nombre de sommets relations par relation est pair, afin d’avoir le même nombre de sommets relations positifs et négatifs par relation. Les figures 3.4, 3.5 et 3.6 illustrent les résultats obtenus,respectivement en mesurant le temps de calcul, la taille de l’arbre de recherche exploré et le pourcentage de déduction pour les valeurs de densité du source DS = 9.375%, 12.5%, 15.625%, 18.75%, 21.875%, 25% et 28.125%, et en faisant varier en abscisse la densité du graphe cible. Notons que le pourcentage de timeouts est proche de 0% pour toute valeur de DS et DC.Intuitivement, on s’attend à ce que le temps de résolution soit directement lié à la taille de l’arbre de recherche exploré puisqu’au moins un test d’homomorphisme est effectué à chaque nœud de l’arbre de recherche. Cette intuition est confirmée par les figures 3.4 et 3.5 : les zones de difficulté pour les mesures du temps et de la taille de l’arbre de recherche sont corrélées (par exemple pour DS = 18.75%, les trois pics de difficulté – DC = 31.25%, 34.375% et 37.5% – se retrouvent sur les deux figures). Par ailleurs la difficulté est observée maximale pour DS = 15.625%. Néanmoins quelques valeurs ne sont pas directement corrélées (par exemple pour DS = 15.625%, le temps de résolution pour DC = 18.75% est inférieur à celui pour DC = 21.875% – respectivement 2189ms et 2531ms – alors que la taille pour un graphe cible composé d’environ 1.8 fois plus de sommets relations que le source. Cette distribution peut s’expliquer par le fait qu’elle permet d’obtenir des instances qui vont nécessiter un grand nombre de complétions explorées ; ces instances sont donc généralement non triviales.
|
Table des matières
Remerciements
1 Introduction
2 Notions de base
2.1 Notions classiques en bases de données
2.1.1 Schéma et instance de bases de données
2.1.2 Les requêtes
2.1.3 Problèmes de base
2.1.4 Introduction de la négation et hypothèse du monde clos
2.2 Notions classiques en bases de connaissances
2.2.1 La base de connaissances
2.2.2 Les logiques de description et les graphes conceptuels
2.2.3 Les correspondances et différences entre les BD et les BC
2.3 Reformulation en logique classique
2.3.1 Notions de base
2.3.2 Vision graphes
2.4 État de l’art algorithmique sur le problème Déduction
2.4.1 Impact de l’ajout de la négation sur le problème Déduction
2.4.2 L’approche de Ullman
2.4.3 L’approche de Wei et Lausen
2.4.4 L’approche de Leclère et Mugnier
3 Méthodologie expérimentale
3.1 Les jeux de données
3.2 Paramètres de génération
3.3 Algorithme de génération aléatoire
3.4 Instances difficiles et phénomène de seuil
3.5 Méthodologie de test
3.6 Influence des différents paramètres sur la difficulté
3.6.1 Influence des densités des graphes source et cible
3.6.2 Influence du pourcentage de négation
3.6.3 Influence du pourcentage de sommets constantes
3.6.4 Influence du nombre de sommets termes du graphe cible
3.6.5 Influence de l’arité des relations
3.6.6 Influence du nombre de relations
4 Affinements et nouveaux algorithmes
4.1 Raffinements de l’algorithme recCheck
4.1.1 Choix du prochain littéral de complétion
4.1.2 Choix du fils à parcourir en priorité
4.1.3 Filtrage dynamique
4.1.4 L’algorithme recCheckPlus
4.2 Analyse et reformulation de l’algorithme de Wei et Lausen
4.2.1 Propriétés fondamentales
4.2.2 L’algorithme de Wei et Lausen
4.2.3 Nouveaux algorithmes basés sur la propriété de Wei et Lausen
4.3 Algorithme UNSATCheck
4.3.1 La méthode
4.3.2 Taille de la formule propositionnelle obtenue
4.4 Comparaison des algorithmes
5 Extensions
5.1 Prise en compte des constantes
5.2 Réponse à une requête non-booléenne
5.3 Prise en compte d’une ontologie légère
6 Conclusion
Table des figures
Liste des tableaux
Télécharger le rapport complet
