UM2 : M2RI UMIN310 2005-2006 Examen Module Représentation ...

Examen Module Représentation des Connaissances
Question « Ouverte » Modalités : l'examen comporte deux parties :
1. une épreuve « classique sur table » d'une durée de 2 heures qui aura
lieu le vendredi 4 novembre 2005 à 15h00 dans la salle habituelle et
qui comportera des questions sur les différents cours et sur les
documents qui vous ont été remis : chapitre « Basic Graph » du livre en
préparation et rapport de recherche sur la négation (sauf partie lien
avec les bases de données) ;
2. une question « ouverte » nécessitant un travail de réflexion plus long.
Pour cette deuxième épreuve, nous vous proposons ci-dessous deux
sujets. Vous devez en traiter 1 seul au choix et nous rendre le jour de
l'examen (4/11/2005) votre travail sur cette question en même temps que
la copie de l'épreuve sur table. Sujets de question « ouverte » : Le sujet 1 concerne l'étude d'une
extension du modèle de base des graphes conceptuels : l'introduction de
relations particulières d'égalité et de différence. Le sujet 2 est un sujet
d'algorithmique : il s'agit de réfléchir à différentes améliorations de
l'algorithme de « backtrack » vu en cours.
Sujet 1 : Introduction de la différence dans le modèle BG. Le modèle de base des graphes conceptuels (BG) permet de représenter
n'importe quelle relation entre entités (i.e. sommets concepts). On se pose
le problème de la représentation des relations d'égalité et de différence
entre entités. On pourrait les représenter par des sommets relations
classiques mais cela ne tiendrait pas compte de leurs spécificités
algébriques (réflexivité et anti-réflexivité, symétrie, transitivité...).
On préfère donc les introduire comme de « nouveaux éléments» du modèle et
les représenter graphiquement par des arêtes spécifiques que nous
appellerons liens de coréférence (arêtes en pointillés pour l'égalité) et
liens d'anti-coréférence (symbolisés par une arête avec deux barres pour la
différence) comme proposé sur la figure 1. Le graphe de la figure 1
représente le fait suivant : « Paul, who is a child, possesses a small car.
Paul and a person, who is not Paul, play with this car ».
[pic]
Figure 1 On peut pour ce nouveau modèle de graphe, définir une « forme normale »
en fusionnant les sommets concepts « coréférents » (cf. figure 2) obtenant
ainsi un graphe sémantiquement équivalent au premier ne possédant plus de
liens de coréférence. La relation d'égalité sur l'ensemble C des sommets
concepts d'un graphe sous cette forme normale est donc réduite à la
relation d'identité sur C (c'est-à-dire que chaque sommet n'est coréférent
qu'avec lui-même).
Figure 2 L'objectif du travail demandé est l'extension du modèle des BG aux
graphes contenant des liens d'anti-coréférence. On ne s'intéressera pas
dans ce travail à l'introduction des liens de coréférence considérant qu'on
peut toujours se ramener à une forme normale. Il vous est donc demandé :
1. De définir l'extension BG? :
o définir la syntaxe formelle de ce nouveau modèle BG? ;
o étendre les fonctions d'interprétation logique ? et
ensembliste ( à BG? ;
o étendre les opérations de spécialisation et de généralisation
à BG? ;
o étendre la définition de la projection pour BG?.
2. De s'intéresser aux propriétés suivantes (i.e. donner des preuves
(au moins des schémas de preuves) ou des contre-exemples) :
o équivalence entre spécialisation et projection ;
o adéquation et complétude de la projection par rapport à la
déduction logique et/ou par rapport à la conséquence
sémantique définie dans l'interprétation ensembliste.
3. De discuter des liens entre cette extension et l'extension des BG à
la négation telle qu'elle est décrite dans le rapport de recherche.
En particulier, observant que la différence est la négation de
l'égalité, pourrait-on proposer différentes sémantiques de
différence ?
Sujet 2 : Amélioration de l'algorithme de backtrack recherchant une
projection Contexte. En cours, nous avons vu un algorithme générique qui, étant donnés
deux BGs G et H, retourne une projection de G dans H s'il en existe une, et
un échec dans le cas contraire. Cet algorithme suit le principe classique
du backtrack : il tente successivement d'affecter une image à un noeud de
G, en maintenant la propriété suivante : « à un instant donné, les
affectations déjà construites doivent définir une solution partielle ». Si
une affectation d'un sommet c est incompatible avec celles déjà réalisées
(on n'a plus une solution partielle), l'algorithme tente d'affecter une
autre image à c. Si toutes les images potentielles de c ont été essayées
sans succès, l'algorithme « backtrack » : il revient au noeud traité juste
avant c et essaye d'affecter une autre image à ce noeud, si possible. Cet
algorithme peut être vu comme explorant un arbre de recherche représentant
toutes les applications possibles de CG dans CH. Le sous-algorithme preprocessing() a pour tâche de restreindre a priori
la partie de l'arbre de recherche explorée par l'algorithme. Nous partirons
du sous-algorithme suivant : Pour tout sommet c de CG
1. Calculer poss(c) = { c' ( CH | étiq(c) ( étiq(c') }
2. Si poss(c) est vide, sortir avec échec Questions.
1. Donner une définition précise de ce qu'est une « projection
partielle ». Comment peut-on vérifier, après affectation d'une image
à c, que l'application Sol' obtenue est une projection partielle? 2. On appelle filtre une application qui à tout sommet concept de G
associe un ensemble non vide de sommets de H ayant une étiquette
inférieure ou égale. Tout filtre vérifie la propriété suivante,
appelée consistance d'étiquettes :
pour c ( CG, poss(c) n'est pas vide et
pour tout c' ( poss(c), {(c,c')} est une projection
partielle de G dans H.
Lorsqu'il se termine avec succès, le sous-algorithme précédent calcule le
filtre maximal (à tout sommet, il associe l'ensemble de tous les sommets de
H ayant une étiquette inférieure ou égale). Toute projection de G dans H
associe forcément à tout sommet c ( CG un élément de poss(c).
A partir du filtre maximal, on veut calculer le plus grand filtre qui
vérifie la propriété suivante (appelée consistance de relation) :
pour tout c ( CG, pour tout c'( poss(c), pour toute
relation r voisine de c, ayant pour autres voisins c1 ...
cp, on peut étendre la projection partielle {(c,c')} à une
projection partielle affectant à tout ci une image prise
dans poss(ci).
Pour G et H donnés, il n'existe pas forcément de filtre vérifiant cette
propriété, mais s'il en existe un, il est unique (ce qu'on ne vous demande
pas de démontrer). On l'appelle le filtre relation-consistant.
Remarque : pour assurer cette propriété, il est intéressant d'étendre la
notion de filtre aux sommets relations.
o Définir précisément la notion de filtre qui vérifie la consistance
de relation.
o Proposer un algorithme qui calcule ce filtre lorsqu'il existe.
Votre algorithme est-il polynomial ? 3. Les techniques de filtrage peuvent être utilisées en phase de
prétraitement, mais aussi pendant la recherche elle-même, de façon à
propager les conséquences d'une affectation. Expliquez comment vous
pouvez tirer parti de votre algorithme de filtrage dans l'algorithme
de backtrack.
-----------------------
Person Car Child : Paul Car Size : Small poss attr play2
1 2 3 3 2 1 play2 attr poss Size : Small Child : Paul Car Person