7 Future perspectives?
6.3 Concluding remarks
Au formalisme “noyau” des graphes conceptuels simples, la famille SG ajoute deux types de connaissances représentées sous forme bicolorée : les règles et les contraintes. Cette section présente les règles SG et les mécanismes d’inférence à partir desquelles les connaissances sont déduites. Une règle SG R qui exprime une connaissance de la forme
“si hypothèse alors conclusion” est un SG bicoloré dont les sous-graphes R(0) et R(1)
représentent respectivement l’hypothèse et la conclusion.
La figure 3.5 présente deux exemples de règles. L’hypothèse de la règle se compose des sommets blancs (couleur 0) alors que sa conclusion est coloriée en gris (couleur 1).
Les règles R1, R2 et R3 expriment les propriétés des relations proche et membre. R1
donne son caractère symétrique à la relation proche tandis que R2 permet de déduire
la proximité de deux bureaux s’ils sont adjacents à un même troisième. R3 exprime que
1
R
R2
R3
adjacent Bureau adjacent Bureau Bureau
Bureau Bureau
Chercheur membre Projet proche proche
proche
Fig.3.5 – Règles SG
Afin de permettre la représentation du lien de coréférence dans une règle définie par un SG bicoloré, on contraint ce dernier à prendre une coloration qui indique son appartenance ou non à la partie conclusion. Pour colorier ce lien il faut respecter la règle suivante : tout lien de coréférence relié à un sommet non frontière de la conclusion prend la couleur de ce sommet ; et par conséquence appartient à la conclusion. Il faut remarquer que les règles SG peuvent aussi être définies sous la forme de deux SG disjoints (l’un représentant l’hypothèse et l’autre la conclusion) dont les sommets frontières sont reliés par des liens de coréférence (cette définition n’est pas présentée ici pour plus de détails voir [BM02]).
3.2.1 Application d’une règle et dérivation
Une règle R s’applique à un SG F s’il existe une projection de l’hypothèse de R dans F . L’application de R à F selon une telle projection π consiste à “attacher” à F la conclusion de R, en fusionnant chaque sommet frontière de la conclusion avec l’image par π du sommet frontière lui correspondant dans l’hypothèse. Notons que ce mécanisme est complètement basé sur des opérations de graphe.
Plus formellement : soit F un SG et R une règle, R est applicable à F s’il existe
une projection π de R(0) dans F . Dans ce cas, le résultat de l’application de R dans
F relativement à π est le SG F0 obtenu en effectuant l’union disjointe de F avec R(1),
puis en fusionnant chaque sommet frontière s de R(1) avec π(s). On dit de F0 qu’il est
la R-dérivation directe de F .
La figure 3.6 présente deux applications des règles R2 et R1 de la figure 3.5. F1 et F2
sont respectivement obtenus en appliquant R2 sur F0 et F1 et sont respectivement une
R2-dérivation et une R1-dérivation directe de F0 et de F1. Les sommets ajoutés lors de
F1
F2 0
F adjacent
Bureau : N30 Bureau adjacent Bureau : N32
dans Chercheur
Chercheur : L. dans
Bureau : N30 adjacent Bureau adjacent Bureau : N32 proche
Chercheur : L.
dans Chercheur dans
Bureau : N30 adjacent Bureau adjacent Bureau : N32
dans Chercheur proche proche Chercheur : L. dans
Fig. 3.6 – Applications de règle
Étant donné un fait F et un ensemble de règles R, on dit qu’un SG F0 se dérive de
F par R s’il existe une séquence d’applications de règles de R menant de F à F0. Plus
précisément, la R-dérivation de F à F0 est une séquence de SG F = F
0, ..., Fk = F0 telle
que pour tout 1 ≤ i ≤ k, Fi soit une R-dérivation directe de Fi−1 et R une règle de R.
On considère maintenant une base de connaissances K = (S, F, R) composée d’un support S , d’un ensemble de règles R et d’un fait F définis par rapport au support. Le mécanisme d’interrogation de K doit prendre en compte la connaissance implicite encodée dans les règles. La base de connaissances répond à une requête Q s’il existe un
SG F0 dérivé de F (par les règles de R) tel que Q se projette dans F0.
Considérons par exemple la figure 3.7 qui présente un graphe F0 obtenu par R-
dérivation à partir du graphe F0 de la figure 3.6. Les sommets ajoutés par application
de règles ont leurs contours en pointillés. On peut établir une projection entre le SG Q
de cette figure et le sous-graphe F00 délimité par la portion grise. Si Q est vue comme
une requête, l’image F00 de Q peut être considérée comme une des réponses déductibles
F’’
Q F’
adjacent Bureau adjacent
membre Projet Projet membre Chercheur dans Bureau proche Bureau Chercheur dans F’’ Projet membre membre dans Chercheur dans Chercheur : L. proche proche Bureau : N32 Bureau : N30 Projet
Fig. 3.7 – Réponse à une requête après R-dérivation
Pour déterminer si un tel SG Q se déduit de la base de connaissances K, on dis- pose de mécanismes de chaînage avant et de chaînage arrière adéquats et complets par rapport à la déduction logique [SM96]. Précisons que le problème d’interrogation n’est plus décidable (autrement dit il n’existe pas d’algorithme qui résolve ce problème en un temps fini quelles que soient les données) si l’on ne restreint pas la forme des règles. Règles à dérivation finie
Néanmoins, lorsque les règles sont à dérivation finie, la décidabilité du problème est assurée quelle que soit la base de faits. Ces règles se définissent à partir de la notion de graphe complet : un graphe irredondant H est dit complet par rapport à un ensemble de règles R lorsque tout graphe résultant de l’application sur H d’une de ces règles est équivalent à H.
Un ensemble de règles est dit à dérivation finie si pour tout SG G, il existe une R-
dérivation G ... G0 telle que irr(G0) soit complet par rapport à R. Le graphe complet est
noté GR.
Pour un tel ensemble R de règles, le problème de déduction pour une base de connais- sances K = (S, G, R) devient décidable. Pour déterminer si un SG Q est déductible de
K, il suffit d’obtenir GR et de vérifier l’existence d’une projection de Q dans GR 4.
4
Lorsque les conclusions de règles ont des sommets individuels, il est néanmoins nécessaire de mettre chaque graphe résultant d’une application de règle sous forme normale
Toutefois, cette condition n’est pas nécessaire et pour certains ensembles de règles la déduction peut être décidable sans qu’ils soient à dérivation finie.
Il existe des conditions suffisantes qui permettent de déterminer si un ensemble de règles est à dérivation finie. L’une d’entre elles, énoncée dans [BS06], stipule qu’un en- semble de règles est tel si aucun cycle de dépendance n’apparaît au sein de l’ensemble,
sachant qu’une règle R2 est dépendante d’une règle R1 si l’application de R1 peut “dé-
clencher” l’application de R2, c’est-à-dire s’il existe un SG G sur lequel l’application de
R1 produit un SG dans lequel peut être établie une projection de l’hypothèse de R2 qui
ne peut l’être dans G. Un algorithme est proposé pour déterminer si un ensemble de règles respecte cette condition. En plus de cette méthode, il existe une procédure simple pour reconnaître un autre type de règles à dérivation finie en s’assurant que leur syntaxe respecte certaines conditions : les règles “range-restricted”.
Règles “range-restricted”
Une règle est dite “range-restricted” lorsque sa conclusion ne présente aucun sommet concept générique. Le terme est similaire à celui utilisé pour désigner les règles Datalog dont toutes les variables de la tête doivent apparaître dans le corps. Dans la figure 3.5,
les deux règles R1 et R2 sont “range-restricted” alors que R3 ne l’est pas.
Chaque règle R de ce type peut se fragmenter en un ensemble D(R) de règles dont l’hypothèse est identique à R et dont la conclusion ne présente qu’un seul sommet relation ou concept individuel provenant de la conclusion de R. Plus précisément, pour chaque
sommet s de la conclusion de R, il existe une règle R0 dans D(R) telle que :
– si s est un sommet concept individuel, alors l’hypothèse de R0 est celle de R et la
conclusion de R0 est celle de R restreinte au sommet s ;
– si s est un sommet relation, alors l’hypothèse de R0 est la somme disjointe de celle
de R avec les sommets individuels de la conclusion de R ; et la conclusion de R0
est restreinte au sommet s tel qu’il ait les mêmes voisins que dans R ;
Soit R un ensemble de règles “range-restricted” et F un SG. Un SG Q est déductible de F et des règles R ssi il est déductible de F et de leur décomposition D(R) (par contre, cette équivalence n’est plus valable si les contraintes - qui seront introduites en partie 3.3 - interviennent). Avec de telles règles, le problème de déduction dans une base de connaissances K = (S, G, R) est NP -complet.
3.2.2 Sémantique logique.
La sémantique logique Φ s’étend de façon naturelle aux règles. La formule associée à
une règle R est de la forme Φ(R) = ∀x1 ... xp ((hyp) → ∃y1 ... yq (conc)), où hyp et conc
sont les conjonctions d’atomes respectivement associées à l’hypothèse R(0)et à la conclu-
sont les variables associées aux sommets de la conclusion à l’exclusion des sommets fron- tières. Les mêmes variables sont associées aux sommets frontières se correspondant dans
l’hypothèse et la conclusion (i.e. reliés par des liens de coréférence). Pour la règle R2 de
la figure 3.5, on obtient ainsi Φ(R2) = ∀x∀y∀z (Bureau(x) ∧ Bureau(y) ∧ Bureau(z) ∧
adjacent(x, y) ∧ adjacent(y, z) → Bureau(x) ∧ Bureau(z) ∧ proche(x, z)) et pour la
règle R3 on obtient Φ(R3) = ∀x(Chercheur(x) → ∃(yP rojet(y) ∧ member(x, y))). On
remarque que les variables qui n’apparaissent que dans la conclusion sont existentielle- ment quantifiées.
Le mécanisme de chaînage avant associé à une base de connaissances K = (S, F, R) est adéquat et complet par rapport à celui de la logique des prédicats. Étant donné un SG Q, Q ≥ K ssi φ(S), φ(G), φ(R) |= φ(Q). Ce résultat est établi si les graphes Q et G donnés et ceux résultant de l’application sur G des règles sont donnés ou mis sous forme normale.
Lorsque les règles de R sont “range-restricted”, les formules issues de l’interprétation logique des règles de D(R) peuvent être mises sous la forme de clauses de Horn. En effet,
chaque formule obtenue sera de la forme Φ(R) = ∀x1 ... xp ((hyp) → r(xi1, xi2, ..., xik))
(avec 1 ≤ ij ≤ p, pour 1 ≤ j ≤ k et k l’arité de r) ; ce qui peut se réécrire en une formule
équivalente ∀x1 ... xp (hyp0∨ r(xi1, xi2, ..., xik)) où hyp
0 est une disjonction de littéraux
négatifs équivalente à ¬hyp. L’expression hyp0∨r(x
i1, xi2, ..., xik) est donc une disjonction
composée de la série des littéraux négatifs apparaissant dans hyp0 et d’un seul littéral
positif (le prédicat r), ce qui correspond à une clause de Horn. Cette caractéristique des règles “range-restricted” garantit une déduction décidable.