Négation

Mugnier

Description

• cours - matière potentielle : introduction

Page 1 Négation Jusqu'ici nous vivions dans un monde positif … Que signifie « non » ? Quelles difficultés pose l'introduction de négation ? Contenu du cours Introduction de « la » négation atomique ¬ p(t1 …tk) ¬ =(t1,t2) Dans les différents niveaux de bases de connaissances : Faits Ontologie légère + Faits Ontologie sous forme de règles + Faits en considérant le problème d'interrogation Différentes formes de négation Selon les hypothèses faites sur les connaissances représentées Hyp.

• ontop c1
• hypothèse du monde ouvert
• blue -blue c2
• base de connaissances ¶
• world assumption
• ontop c3
• bases
• base

Sujets

• Introduction
• Connaissance
• Assumption

Informations

• Publié par: shooz
• Nombre de lectures: 67
• Langue: Français

Extrait

Négation
Jusqu’ici nous vivions dans un monde positif …
Que signifie « non » ?
Quelles difficultés pose l’introduction de négation ?
Contenu du cours
Introduction de « la » négation atomique
¬ p(t1 …tk) ¬ =(t1,t2)
Dans les différents niveaux de bases de connaissances :
Faits
Ontologie légère + Faits
Ontologie sous forme de règles + Faits
en considérant le problème d’interrogation
Différentes formes de négation
Selon les hypothèses faites sur les connaissances représentées
Hyp. du « monde ouvert » / du « monde clos »
Selon ce qu’on considère comme une preuve
Page 1$
Ù
Ù
Ù
$
Niveaux faits (+ requête conjonctive)
Vue logique : un fait est une conjonction de littéraux fermée
existentiellement
x y ( B(x) ¬ B(y) on(x,y) ¬ on(y,x) )
Vue graphe : un sommet relation peut être étiqueté par +p ou –p,
où p est un prédicat (« graphe polarisé » (PG))
+blue
+p correspond à p
-p correspond à ¬p -on +on
Dans les dessins, on mettra souvent p au lieu de +p
-blue
Littéraux « contradictoires » : p(t1…tk) et ¬p(t1…tk)
Pté: un fait est inconsistant (insatisfiable) ssi il a des littéraux contradictoires
A partir de maintenant, on considère des faits (et requêtes) consistants.
Exemple de base
QB c1 blue blue
1
onToponTop
2
3
c2 -blue
« are there x and y suchonTop
that b(x) and not b(y) …..»
« find all x and y such thatc3
b(x) and not b(y) …..»
Page 2Hypothèse du monde clos
Hypothèse du monde clos
(CWA : closed-world assumption)
On suppose une connaissance complète du monde
on n’encode dans les faits que ce qui est vrai
« P est vrai » si P est présent
(plus généralement : déductible de la base)
« P est faux » si P n’est pas présent
(plus généralement : n’est pas déductible de la base)
Hypothèse faite en Bases de Données
Permet de ne stocker que ce qui est positif
ex : « être un utilisateur enregistré »
ex: pour des stations de métro : « être directement connectées »
Hypothèse du monde ouvert
Hypothèse du monde ouvert
(OWA : open-world assumption)
On suppose une connaissance incomplète du monde

« P est vrai » si P est déductible de la base
« P est faux » si ¬ P est déductible de la base
« la valeur de P est inconnue »
si ni P ni (¬ P) ne sont déductibles de la base
ex : « avoir un ou des enfants », « être fan de rock »
Hypothèse généralement faite
dans les systèmes à base de connaissances
Page 3Négation dans les requêtes
« y-a-t-il x et y tels que b(x)
and non b(y) …..»
Que signifie non b(y)?
OWACWA
non b(y) est prouvableb(y) n’est pas prouvable
(« négation par l’échec »)
La notion de preuve elle-même
peut avoir différents sensSi l’on n’a que des faits:
b(y) n’est pas présent
Hypothèse du monde clos (CWA)
On n'encode donc dans les faits que la connaissance positive.
La négation n’apparaît donc que dans les requêtes
B encode « B complété négativement », c-a-d obtenu en ajoutant toutes
les relations négatives implicites (c-a-d qui ne sont pas contradictoires
avec une relation positive de B)
TH. Soient Q et B (B consistante)
Q est conséquence de B ssi il existe un homomorphisme de Q
dans le graphe "complété négativement" de B
Page 4P
P
P
P
P
P
B Q
-onT
blue
c1 blue
onT
onT -onT
-onT
-blue
c2 -blue
-onTonT
-onT
-bluec3
B complété « en négatif » (ou presque …)
En pratique on ne construit pas le complété de B :
Soit Q+ la partie positive de Q (sommets termes et relations positives)
Q est conséquence de B s’il existe un homomorphisme de Q+ dans B,
qui ne contredit pas de relation négative de Q :
–r(t1...tk) de Q est contredite si B contient +r ( (t1)... (tk))
Si Q est une requête non booléenne :
Notation Datalog : ans(x1…xp) Q
L’ensemble des réponses à Q est l’ensemble des ( (x1)... (xp)),
pour chacun des définis comme ci-dessus
Page 5Closed world assumption: « not proving »
B
Qc1 blue blue
onToponTop
c2 -blue
onTop
Is there a homomorphism from
Q+ to B that does not contradict
the negative relations of Q?
c3
An answer is given by such a
homomorphism
Open world assumption: « proving not »
Q
B bluebluec1
onToponTop
-blue
-bluec2
blue Is Q consequence of B?
onTop
Yes (with classical logic)
-blue Is there an answer to Q in B?c3
No
Page 6Déduction classique
• Graphe complet (par rapport à un ensemble de relations) :
pour toute relation r d'arité k, pour tout k-uplet de termes t1 ... tk,
on a un littéral +r (t1...tk) ou (exclusif) –r (t1...tk)
• Graphe complet obtenu à partir de B : on ajoute à B des littéraux,
sans créer d’inconsistance, jusqu’à avoir un graphe complet
TH. Soient Q et B (B consistante)
Q est conséquence de B ssi il existe un homomorphisme de Q
dans chaque graphe complet constructible à partir de B
Algorithme brutal
1. construire tous les graphes complets que l’on peut obtenir à partir de
B (il y en a un nombre exponentiel en la taille de B)
2. vérifier qu’il y a un homomorphisme de Q dans chacun d’eux
Bien sûr, on peut améliorer l’algorithme brutal
Réduire le nombre de symboles de relation à considérer dans la
complétion
On peut se limiter aux (symboles de) relations qui apparaissent à la
fois dans Q et dans B, et ce, à la fois positivement et négativement
Trouver des conditions suffisantes ou nécessaires de déduction
Ex : Si on a un homomorphisme de Q dans B
alors Q est conséquence de B
Ex : Si Q est conséquence de B
alors on a un homomorphisme de Q+ dans B
Compléter les graphes incrémentalement au lieu de générer
directement des graphes complets
Page 7Avoid to build complete graphs
instead of checking homomorphisms from Q to all completions of B,
proceed incrementally from B
B
Q
Total Completions of B
Avoid to build complete graphs
Instead of checking homomorphisms from Q to all completions of B,
proceed incrementally from B
B
+r(t1…tk) -r(t1…tk)
Q
Space ordered
by
subgraph inclusion
Completions of B
Try to find a set of graphs { B1… Bn } that « covers » the completions of B
and such that Q can be mapped to each Bi
Page 8Example
Q
B bluebluec1
onTop
onTop
-blue
-bluec2
blue
onTop
-bluec3
Sketch of an improved algorithm
Filtering step
If allows to conclude, return true or false
Completion step
Call RecursiveCheck(B)
R = {relation types occurring both positively and negatively in Q and in B}
RecursiveCheck(B’)
1. If there is a homomorphism from Q to B’, return true
2. If B’ is complete wrt to R return false // B’ is a counter-example
3. Choose r in R and (t1…tk) in B’
4. Let B+ be B’ added with +r(t1…tk)
Let B- be B’ added with -r(t1…tk)
Return (RecursiveCheck(B+) and RecursiveCheck(B-))
Page 9Let’s come back to the example
QB c1 blue blue
onToponTop
c2 -blue
Is Q consequence of B?
onTop
Yes (with classical logic)
Is there an answer to Q in B-bluec3
(if we want the values of x and y) ?
No
[Définir la notion de réponse à une requête non booléenne]
Observations
The assertions « Q can be deduced from B » and
« B contains an answer to Q » might disagree
Thus :
Deduction (« is Q deducible from B ? »)
and Query Answering
(in its decision form : « is there an answer to Q in B ? »)
are not equivalent anymore
This is due to the law of excluded-middle
Question: which logic to translate the notion of answer?
Page 10