Chapter 5A Semantic Web Primer 1 Chapitre 5 Logique et inférence: règles Grigoris Antoniou Frank van Harmelen

Chapter 5 A Semantic Web Primer1

Chapitre 5 Logique et inférence: règles

Grigoris Antoniou

Frank van Harmelen


Sommaire

1. Introduction

2. Règles monotoniques: exemple

3. Règles monotoniques: syntaxe et sémantique

4. Règles non monotoniques: syntaxe

5. Règles non monotoniques: exemple

6. Un DTD pour les règles monotoniques

7. Un DTD pour les règles non monotoniques


Représentation des connaissances

Jusqu'à présent, on a vu ce qui concerne la représentation des connaissances

La représentation des connaissances La logique reste le fondement de KR, surtout

sous la forme de la logique des prédicats (logique du premier ordre)


Importance de la logique

Langage de haut niveau pour l'expression des connaissances

Puissance d'expression élevée Sémantique formelle bien comprise Notion précise de conséquence logique Système de vérification capable de dériver

automatiquement les déclarations du point de vue syntaxique au départ d'un jeu de prémisses


Importance de la logique (2)

Il existe des systèmes de vérification pour lesquels une conséquence sémantique logique coïncide avec la dérivation syntaxique dans le système de vérification

– sûrs et complets La logique des prédicats est unique en ce sens que des

systèmes de vérification sûrs et complets existent réellement – pas pour une logique plus expressive (logique d'ordre

supérieur) Suit la vérification conduisant à une conséquence logique Logique susceptible de fournir des explications aux réponses

– par traçabilité de la vérification


Spécialisations de la logique des prédicats: RDF et OWL

RDFS et OWL (Lite et DL) sont des spécialisations de la logique des prédicats – correspondant essentiellement à une logique

descriptive Elles définissent des sous-jeux raisonnables de la

logique Compromis entre puissance d'expression et

complexité de calcul t– Plus le langage est expressif, moins les systèmes

de vérification correspondant sont efficaces


Spécialisations de la logique des prédicats: logique Horn

Une règle a la forme: A1, . . ., An B– Ai et B sont des formules atomiques

Deux moyens de lire une telle règle:– règles déductives: si A1,..., An sont réputés

vrais, B est alors également vrai– règles réactives: si les conditions A1,..., An sont

vraies, exécuter l'action B


Logique descriptive par rapport à logique Horn

Aucune n'est un sous-ensemble de l'autre Il est impossible d'affirmer que des personnes qui

étudient et vivent dans la même ville sont des "home students" en OWL

– facile avec les règles:studies(X,Y), lives(X,Z), loc(Y,U), loc(Z,U) homeStudent(X)

Les règles ne peuvent affirmer l'information qu'une personne est un homme ou une femme

– cette information s'exprime facilement en OWL par une union disjointe


Règles monotonique par rapport aux règles non monotoniques

Exemple: Un commerçant en ligne souhaite offrir une remise spéciale si le client a son anniversaire ce jour-là

Solution 1

R1: si anniversaire, remise spéciale

R2: si pas anniversaire, pas de remise spéciale Que se passe-t-il si un client refuse de donner sa

date de naissance pour des raisons de respect de la vie privée?


Règles monotonique par rapport aux règles non monotoniques (2)

Solution 2 R1: si anniversaire, remise spéciale R2’: si date anniversaire inconnue, pas de

remise spéciale Résout le problème, mais:

– la prémisse de la règle R2' n'est pas comprise dans la puissance d'expression de la logique des prédicats

– il faut un nouveau type de système de règles


Règles monotoniques par rapport aux règles non monotoniques (3)

La solution avec les règles R1 et R2 fonctionne lorsqu'on a une information complète de la situation

Le nouveau système de règles sera appliqué dans les cas où les informations disponibles sont incomplètes

R2’ est une règle non monotonique


Echange de règles

Echange de règles entre différentes applications– ex., une boutique en ligne fait la pub de ses politiques de

prix, de remboursement et de confidentialité. Elle les exprime par des règles

L'approche sémantique consiste à exprimer le contenu de manière accessible par la machine en faisant appel à l'un des langages web que nous avons vus

On montre comment les règles peuvent s'exprimer en langages de type XML (langages de balisage des règles)


Sommaire

1. Introduction








Relations familiales

Eléments factuels d'une base de données sur les relations familiales:

– mother(X,Y), X mère de Y– father(X,Y), X père de Y– male(X), X masculin– female(X), X féminin

Relation inférée parent: un parent est soit un père soit une mère

mother(X,Y) parent(X,Y)

father(X,Y) parent(X,Y)


Relations inférées

male(X), parent(P,X), parent(P,Y), notSame(X,Y) brother(X,Y)

female(X), parent(P,X), parent(P,Y), notSame(X,Y) sister(X,Y)

brother(X,P), parent(P,Y) uncle(X,Y) mother(X,P), parent(P,Y) grandmother(X,Y) parent(X,Y) ancestor(X,Y) ancestor(X,P), parent(P,Y) ancestor(X,Y)


Sommaire

1. Introduction








Règles monotoniques - syntaxe

loyalCustomer(X), age(X) > 60 => discount(X)

On distingue dans les règles :– variables: les variables sont des marques de

réservation de valeurs : X– constants: les constantes signalant des valeurs fixes:

60– predicats: indiquent des objets: loyalCustomer, >– function symbols: symboles de fonction qui donnent

une certaine valeur pour certains arguments: age


Règles

B1, . . . , Bn A

A, B1, ... , Bn sont des formules atomiques A est l’en-tête de la règle B1, ... , Bn sont les prémisses (énoncé de la règle ) Les virgules contenues dans l'énoncé de la règle sont lues de

manière conjonctive Les variables peuvent se présenter dans A, B1, ... , Bn

– loyalCustomer(X), age(X) > 60 discount(X)– implicitement quantifiées de manière universelle


Faits et programmes de logique

Un fait est une formule atomique Par ex. loyalCustomer(a345678) Les variables d'un fait sont implicitement quantifiées

de manière universelle Un programme de logique P est un ensemble fini de

faits et de règles Sa traduction en logique des prédicats pl(P) est

l'ensemble de toutes les interprétations logiques des prédicats des règles et des faits dans P


Buts

Un but [finalité] signale une requête G demandée à un programme de logique

La forme: B1, . . . , Bn Si n = 0 on a un but vide ð


Interprétation du premier ordre des buts [finalité]

X1 . . . Xk (¬B1 . . . ¬Bn)– où X1, ... , Xk sont toutes les variables se présentant dans

B1, ..., Bn– Identique à pl(r), mais l'en-tête de la règle est omise

De même: ¬X1 . . . Xk (B1 . . . Bn)– supposons que l'on connaisse p(a) ; et avec le but p(X) ®– on veut savoir s'il y a une valeur pour laquelle p est vrai– on attend une réponse positive en raison du fait p(a)– par conséquent p(X) est quantifié existentiellement


Pourquoi la négation de la formule ?

On fait appel à une technique de vérification des mathématiques appelée preuve par contradiction: – vérifier que A découle de B en supposant que A est faux et

dérive une contradiction si combiné à B

En programmation logique, on prouve qu'un but peut recevoir une réponse positive en niant le but et en prouvant que l'on obtient une contradiction en appliquant le programme logique– par ex., étant donné le programme logique suivant, on

obtient une contradiction logique


Exemple

p(a)

¬X p(X) La deuxième formule indique qu'aucun

élément n'a la propriété p La première formule indique que la valeur de

a a la propriété p Ainsi $X p(X) découle de p(a)


Règles monotoniques - Sémantique de la logique des prédicats

Etant donnée un programme logique P et une requête

B1, . . . , Bn avec les variables X1, ... , Xk on répond positivement

si et uniquement si

pl(P) |= X1 . . . Xk(B1 ... Bn) (1) ou équivalent, si

pl(P) {¬X1 . . . Xk (B1 ... Ù Bn)} est insatisfiable (2)


Sémantique de la logique des prédicats

Les composantes du langage logique (signature) peuvent avoir n'importe quelle signification

– Un modèle A de logique des prédicats attribue une certaine signification

En logique des prédicats un modèle est constitué de:– un domaine dom(A), ensemble non vide d'objets à propos

duquel les formules donnent des déclarations– un élémént du domaine pour chaque constante– une fonction concrète du domaine dom(A) pour chaque

symbole de fonction– une relation concrète du domaine dom(A) pour chaque prédicat


Sémantique de la logique des prédicats (2)

Les significations des connecteurs logiques ¬,Ú,Ù,®,",$ sont définies en fonction de leur sens intuitif: – non, ou, implique, pour tout, il y a

on définit si une formule est vraie dans un modèle A, indiqué comme A |= φ

Une formule φ découle d'un ensemble M de formules si φ est vrai dans tous les modèles A où M est vrai


Motivation de l'interprétation du premier ordre des buts [finalité]

p(a)p(X) q(X) q(X)

q(a) découle de pl(P) $X q(X) découle de pl(P), Ainsi, pl(P)È{¬$ Xq(X)} est insatisfiable et

on donne une réponse positive


Motivation de l'interprétation du premier ordre des buts [finalité] (2)

p(a)

p(X) q(X)

q(b)

Il faut donner une réponse négative parce que q(b) ne découle pas de pl(P)


Témoins "Ground"

On s'est focalisé jusqu'ici sur les réponses oui/non aux requêtes

En supposant le fait p(a) et la requête p(X) ®– La réponse oui est correcte mais pas

satisfaisante La réponse appropriée est une substitution

{X/a} qui donne une instanciation pour X La constante a est appelée témoin "ground"


Témoins paramétrisés

add(X,0,X)add(X,Y,Z) add(X,s(Y ),s(Z))add(X, s8(0),Z)

Témoins "ground" possibles:– {X/0,Z/s8(0)}, {X/s(0),Z/s9(0)} . . .

Le témoin paramétrisé Z = s8(X) est la répnse la plus générale à la requête: X Z add(X,s8(0),Z)

Le calcul de la majorité des témoins généraux est l'objectif premier de la résolution SLD


Sommaire

1. Introduction








Motivation – Négation dans l'en-tête des règles

Dans les systèmes non monotoniques de règles, une règle peut ne pas s'appliquer même si toutes les prémisses sont connues parce qu'il faut prendre en considération des chaînes de raisonnement contraire

Voyons maintenant les règles défaisables , c'est-à-dire des règles qui peuvent être annulées par d'autres règles

Des atomes niés peuvent se présenter dans l'en-tête et l'énoncé des règles pour permettre des conflits

– p(X) q(X)– r(X) ¬q(X)


Règles défaisables

p(X) q(X)

r(X) ¬q(X) Etant donné les faits p(a) et r(a) on conclut ni q(a) ni ¬q(a)

– voilà un exemple type de deux règles se bloquant l'une l'autre

Le conflit peut être résolu en appliquant des priorités entre règles

Supposons que l'on sache d'une manière ou d'une autre que la première règle est plus forte que la deuxième

– on peut alors déduire q(a)


Origine des priorités entre règles

Primauté– par ex., une loi communautaire a prépondérance sur une

loi nationale – par ex., en gestion d'entreprise, un cadre supérieur a une

autorité supérieure à un cadre moyen Caractère plus récent (antériorité) Spécificité

– l'exemple classique est la règle générale comptant quelques exceptions

On fait abstraction du principe de priorisation spécifique – on suppose l'existence d'une relation externe de priorité

sur l'ensemble de règles


Priorités des règles

r1: p(X) q(X)

r2: r(X) ¬q(X)

r1 > r2

Les règles ont un étiquette unique La relation de priorité doit être acyclique


Règles concurrentes

Dans les cas simples, deux règles sont concurrentes si l'en-tête de l'une est la négation de l'autre

Mais souvent, lorsqu'un prédicat p est dérivé, certains autres prédicats sont exclus – par ex., un conseiller en investissements peut

baser ses recommandations sur trois niveaux de risques acceptables par les investisseurs: faible, moyen et élevé

– un seul niveau de risque par investisseur est retenu


Règles concurrentes (2)

Ces situations sont modélisées en maintenant un ensemble conflictuel C(L) pour chaque littéral L

C(L) contient toujours la négation de L mais peut contenir plusieurs littéraux


Règles défaisables: syntaxe

r : L1, ..., Ln L r est l'étiquette {L1, ..., Ln} l'énoncé (ou prémisses) L l'en-tête de la règle L, L1, ..., Ln sont des littéraux positifs ou négatifs Un littéral est une formule atomique p(t1,...,tm) ou

sa négation ¬p(t1,...,tm) Aucun symbole de fonction ne peut être présent

dans la règle


Programmes à logique défaisable

Un programme à logique défaisable est un triplet (F,R,>) constitué de– un ensemble F de faits– un ensemble fini R de règles défaisables– une relation binaire acyclique > en R

un ensemble de paires r > r' où r et r' sont les étiquettes des règles en R


Sommaire

1. Introduction








Commerce par courtage

Le commerce par courtage se caractérise par l'intervention d'un tiers, le courtier

Le rôle du courtier est de faire coïncider les exigences de l'acheteur avec les possibilités du vendeur, puis de proposer une transaction lorsque les deux parties trouvent leur satisfaction dans l'échange commercial

La location immobilière est une activité courante souvent fastidieuse et qui prend beaucoup de temps


Exigences potentielles du client

– 45 mètres carrés minimum avec au moins 2 chambres à coucher – ascenseur si au troisième étage ou plus haut– animaux de compagnie autorisés

Carlos est d'accord de payer:– $ 300 pour un appartement de 45 m2 situé au centre– $ 250 pour un appartement identique en banlieue– $ 5 en plus par m2 supplémentaire– $ 2 en plus par m2 s'il y a un jardin– il ne peut pas payer plus de $ 400 au total

S'il a le choix, il prendra l'offre la moins chère Sa deuxième priorité est le jardin Sa dernière priorité est la surface supplémentaire


Formalisation des exigences de Carlos – prédicats utilisés

size(x,y), y est la surface de l'appartement x (en m2) bedrooms(x,y), x a y chambres à coucher price(x,y), y est le prix de x floor(x,y), x est à l'étage y gardenSize(x,y), x a un jardin de superficie y lift(x), il y a un ascenseur dans la maison x pets(x), animaux de compagnie admis dans x central(x), x est situé au centre acceptable(x), appartement x répond aux exigences de

Carlos offer(x,y), Carlos est d'accord de payer $ y pour

l'appartement x


Formalisation des exigences de Carlos – Règles

r1: acceptable(X)

r2: bedrooms(X,Y), Y < 2 ¬acceptable(X)

r3: size(X,Y), Y < 45 ¬acceptable(X)

r4: ¬pets(X) ¬acceptable(X)

r5: floor(X,Y), Y > 2,¬lift(X) ¬acceptable(X)

r6: price(X,Y), Y > 400 ¬acceptable(X)

r2 > r1, r3 > r1, r4 > r1, r5 > r1, r6 > r1


Formalisation des exigences de Carlos – Règles (2)

r7: size(X,Y), Y ≥ 45, garden(X,Z), central(X)

offer(X, 300 + 2*Z + 5*(Y − 45))

r8: size(X,Y), Y ≥ 45, garden(X,Z), ¬central(X)

offer(X, 250 + 2*Z + 5(Y − 45))

r9: offer(X,Y), price(X,Z), Y < Z ¬acceptable(X)

r9 > r1


Représentation des appartements disponibles

bedrooms(a1,1)

size(a1,50)

central(a1)

floor(a1,1)

¬lift(a1)

pets(a1)

garden(a1,0)

price(a1,300)


Représentation des appartements disponibles (2)

37512ouinon1oui 653a7

3700nonnon3oui 602a6

35015oui non0oui 553a5

33015nonoui 1non552a4

3500oui non2non652a3



Price prix

Garden jardin

Pets anim

Lift ascen

Floor étage

Central Central

Size surf.

Bedrooms chambres

Flat app.


Détermination des appartements acceptables

Si on fait correspondre les exigences de Carlos avec les appartements disponibles, on a

appart. a1 n'est pas acceptable parce qu'il n'a qu'une seule chambre (règle r2)

appart. a4 et a6 ne sont pas acceptables parce que les animaux de compagnie ne sont pas admis (règle r4)

pour a2, Carlos est d'accord de payer $ 300, mais le prix est plus élevé (règles r7 et r9)

appart. a3, a5 et a7 sont acceptables (règle r1)


Choix d'un appartement

r10: cheapest(X) rent(X)

r11: cheapest(X), largestGarden(X) rent(X)

r12: cheapest(X), largestGarden(X), largest(X)

rent(X)

r12 > r10, r12 > r11, r11 > r10 On doit spécifier que pas plus d'un appartement ne peut

être loué en appliquant les ensembles conflictuels– C(rent(x)) = {¬rent(x)} {rent(y) | y ≠ x}


Sommaire

1. Introduction








Formules atomiques

p(X, a, f(b, Y ))

<atom><predicate>p</predicate><term><var>X</var></term><term><const>a</const></term><term> <function>f</function>

<term><const>b</const></term><term> <var>Y</var></term>

</term></atom>


Faits

<fact><atom>

<predicate>p</predicate><term>

<const>a</const> </term></atom>

</fact>


Règles

<rule>

<head>

<atom>

<predicate>r</predicate>

<term><var>X</var></term>

<term><var>Y</var></term>

</atom>

</head>


Règles (2)

<body><atom><predicate>p</predicate>

<term><var>X</var></term><term><const>a</const> </term>

</atom><atom><predicate>q</predicate>

<term><var>Y</var></term><term><const>b</const></term>

</atom></body>

</rule>


Balisage des règles en XML: un DTD

<!ELEMENT program ((rule|fact)*)> <!ELEMENT fact (atom)> <!ELEMENT rule (head,body)><!ELEMENT head (atom)><!ELEMENT body (atom*)><!ELEMENT atom (predicate,term*)><!ELEMENT term (const|var|(function,term*))><!ELEMENT predicate (#PCDATA)><!ELEMENT function (#PCDATA)><!ELEMENT var (#PCDATA)><!ELEMENT const (#PCDATA)><!ELEMENT query (atom*))>


Modèle de données alternatif de RuleML

RuleML représente un effort majeur de standardisation dans le domaine des règles

RuleML est actuellement basé sur XML mais fait appel à des "role-tags" de type RDF, dont la position dans une expression n'est pas pertinente– cependant, ils sont différents pour le modèle de

données XML dans lequel l'ordre est important


Notre DTD par rapport à RuleML

varvar

indconst

relpredicate

andatom*

_body body

_head head

imprule

rulebaseprogram


Sommaire

1. Introduction








Modifications par rapport au DTD précédent

Absence de symboles de fonction– la structure du terme est neutre

Les atomes négatifs peuvent se présenter dans l'en-tête et l'énoncé d'une règle

Chaque règle a un nom En plus des règles et des faits, un programme

contient encore des déclarations de priorité – on utilise une étiquette <stronger> pour représenter les

priorités et une étiquette d'ID dans les règles pour signaler leur nom


Exemple

r1: p(X) s(X)

r2: q(X) ¬s(X)

p(a)

q(a)

r1 > r2


Règle r1 en XML

<rule id="r1"><head>

<atom><predicate>s</predicate><term> <var>X</var></term>

</atom></head><body>

<atom><predicate>p</predicate><term> <var>X</var> </term>

</atom></body>

</rule>


Faits et priorité en XML

<fact><atom>

<predicate>p</predicate><term> <const>a</const></term>

</atom></fact>

<stronger superior="r1" inferior="r2"/>


un DTD

<!ELEMENT program ((rule|fact|stronger)*)>

<!ELEMENT fact (atom|neg)>

<!ELEMENT neg (atom)>

<!ELEMENT rule (head,body)>

<!ATTLIST rule id ID #IMPLIED>

<!ELEMENT head (atom|neg)>

<!ELEMENT body ((atom|neg)*)>


Un DTD (2)

<!ELEMENT atom (predicate,(var|const)*)><!ELEMENT stronger EMPTY)><!ATTLIST stronger

superior IDREF #REQUIRED>inferior IDREF #REQUIRED>

<!ELEMENT predicate (#PCDATA)><!ELEMENT var (#PCDATA)><!ELEMENT const (#PCDATA)><!ELEMENT query (atom*))>


Récapitulation

La logique Horn est un sous-ensemble de la logique des prédicats permettant un raisonnement efficace, indépendant de la logique de description

La logique Horn est la base des règles monotoniques Les règles monotoniques sont utiles dans les cas où

les informations disponibles sont incomplètes Il s'agit de règles susceptibles de dérogation par une

preuve contraire Les priorités s'utilisent pour résoudre certains conflits

entre règles Les langages de représentation de type XML sont

simples

Documents

Chapter 5A Semantic Web Primer 1 Chapitre 5 Logique et inférence: règles Grigoris Antoniou Frank van Harmelen