Construire un moteur d'inférence

J. ROHMER ESILV S08 2012-2013 INTELLIGENCE ARTIFICIELLE

REGLES, MOTEURs D’INFERENCE

ET ARCHITECTURES REACTIVES

(Version Etendue)

Cours de 4 ème année ESILV Option Informatique

Jean Rohmer

1


Cette présentation traite de:

-- comment faire un moteur d’inférence en chaînage avant pour des règles de production avec variables: moteur Delta-Driven

-- comment transformer des problèmes de chaînage arrière en chaînage avant: Méthode d’Alexandre

-- comment construire une architecture réactive avec un moteur Delta-Driven et la Méthode d’Alexandre

2


On se place dans un monde de « triplets:

TRT / fait partie de / THALES

THALES / a un effectif de / 62000

PIERRE / travaille pour / TRT

TRT France / fait partie de / TRT

TRT France / est situé à / PALAISEAU

THALES / est une / ORGANISATION

ORGANISATION / est une / CATEGORIE

Est situé à / est une / RELATION

3


« TOUT » peut être représenté par des triplets

•Des tables relationnelles

•Des tableaux Excel

•Des objets JAVA

•Du XML

•Des arbres d’analyse syntaxique de langage naturel

4


Exemples de représentations par triplets

•Frames

•Réseaux sémantiques

•Graphes conceptuels

•RDF

•C’est très ancien: années 60 (ou Aristote …)

•Voir un réseau sémantique du 16 ème siècle: http://www.serialmapper.com/archive/2008/01/08/reseau-semantique-du-16eme-siecle.html

•Papier sur l’histoire des réseaux sémantiques : http://www.jfsowa.com/pubs/semnet.htm

5


TRT Fait partie de

THALES

THALES A un effectif de

62000

PIERRE Travaille pour

TRT

TRT France

Fait partie de

TRT

TRT France

Est situé à

Palaiseau

Un simple tableau à 3 colonnes

6


TRT Fait partie de THALES


62000


TRT

TRT France Fait partie de TRT

PIERRE dirige TRT France

TRT France Est situé à Palaiseau

Ca se dessine …

THALES

Fait partie de

TRT

A un effectif de

62000

PIERRE

Travaille pour

TRT France

Fait partie de

Est situé à PALAISEAU

dirige

7


TRT Fait partie de

THALES


62000


TRT

TRT France

Fait partie de

TRT

TRT France

Est situé à

Palaiseau

MODELE SVCI: 4 éléments

10

20

30

40

50

8


TRT Fait partie de THALES

THALES A un effectif de 62000

PIERRE Travaille pour TRT France

TRT France Fait partie de TRT

TRT France Est situé à Palaiseau

MODELE SVCI: 4 éléments10

20

30

40

50

10 depuis 2002

20 En 2012

30 Parce que 50

Paul Dit que 99

101 à l’occasion de Anniversaire de Marie

77

88

99

101

110

9


Ca se dessine …

THALES

Fait partie de

TRT

A un effectif de

62000

PIERRE

Travaille pour

TRT France

Fait partie de

Est situé àPALAISEAU

dirige

2002

depuis

2012

Parce que

PAUL

Dit que

à l’occasion de

Anniversaire

Marie

10


REGLES …

« LES AMIS DE MES AMIS SONT MES AMIS »

X / AMI / Y

et

Y / AMI / Z

=>

X / AMI / Z

11


EN GENERAL PLUSIEURS REGLES …

« LES AMIS DE MES ENNEMIS SONT MES ENNEMIS »

« LES ENNEMIS DE MES AMIS SONT MES ENNEMIS »

« LES ENNEMIS DE MES ENNEMIS SONT MES AMIS »

« LES ANCETRES DE MES ANCETRES SONT MES ANCETRES »

« MES PARENTS SONR MES ANCETRES »

« MES ANCETRES SONT MES AMIS »

Etc ….

NB: on ne s’occupe pas ici de savoir si ces règles ont du sens ou non, si elles sont contradictoires …On se contente de les exécuter

12


APPLIQUER UNE REGLE

PIERRE / AMI / PAUL

PAUL / AMI / JACQUES

X / AMI / Y et Y / AMI / Z => X / AMI / Z

Tout ceci implique:

PIERRE / AMI / JACQUES

13


MOTEUR DE REGLES / MOTEUR D’INFERENCE

UN ENSEMBLE DE TRIPLETS

+UN ENSEMBLE DE REGLES

��

DE NOUVEAUX TRIPLETS

14


MOTEUR D’INFERENCE / APPROCHE NAIVE

APPLIQUER TOUTES LES REGLES

AJOUTER LEURS CONCLUSIONS A LA BASE

RECOMMENCER SI LA BASE A GROSSI

(Méthode de « saturation »)

15


APPLIQUER UNE REGLE

X / AMI / Y Y / AMI / Z -> X / AMI / Z

AA ami BB

AA ami CC

BB ami CC

BB ami DD

CC ami EE

EE ami GG

AA ami BB

AA ami CC

BB ami CC

BB ami DD

CC ami EE

FF ami GG

Tous les triplets Tous les triplets 16


APPLIQUER UNE REGLE = opération de JOINTURE


AA ami CC

AA ami DD

AA ami EE

BB ami EE

Ancien !

Nouveau !

Nouveau !

Nouveau !



UN MOTEUR, CA TOURNE …

UNE REGLE QUI S’APPLIQUE CREE DE NOUVEAUX TRIPLETS

CES NOUVEAUX TRIPLETS PEUVENT PERMETTRE A D’AUTRES REGLES DE S’APPLIQUER

QUAND PLUS AUCUNE REGLE NE PRODUIT DE NOUVEAUX TRIPLETS, C’EST FINI

CA S’ARRETE TOUJOURS

CAR ??? (je vous laisse trouver)

18


LORS D’ UN TOUR SUIVANT …


AA ami CC

AA ami DD

AA ami EE

BB ami EE

AA ami GG

AA ami EE

Nouveau !

ANCIEN!

ANCIEN!

ANCIEN!

ANCIEN!

19


RELATIONS INVERSES

RELATIONS SYMETRIQUES

Traité par des règles supplémentaires

X / travaille pour / Y => Y / emploie / X

X /emploie / Y => Y /travaille pour / X

X / ami / Y => Y / ami / X

Ou mécanisme assuré par la base de données: solution Idéliance

20


Implémentation Naïve de la Saturation

21


Syntaxe des RèglesUn fichier .txt de la forme:

R1,IF,?X,ami de,?Y

R1,IF,?X, est un,Personne

R1,IF,?Y,ami de,?Z

R1,THEN,?X,ami de,?Z

R2,IF,?X,ennemi,?Y

R2,IF,?Y,ami,?Z

R2,THEN,?X,ennemi,?Z

Convention: une variable commence par un « ? » sinon c’est une constante 22


Syntaxe de la base de faits

Un fichier .txt de la forme:

Pierre,est un,Personne

Pierre,ami de,Paul

Paul,ami de,Louis

Max,ennemi,Pierre

23


Premier programme

• Lire un fichier de faits

• Lire un fichier de règles

• Faire toutes les déductions possibles

• Lister toutes les déductions nouvelles

24


Structure du programme (1)

• Lire les faits– Vérifier que syntaxiquement correct– Ignorer les faits incorrects– Lister les faits incorrects

• Lire un fichier de règles– Vérifier que syntaxiquement correct– Ignorer les règles incorrectes– Lister les lignes des règles incorrectes

• Lancer le moteur– Faire toutes les déductions possibles– Lister toutes les déductions nouvelles

25


Structure du programme (2)

• Choix simples d’implémentation• Tous les symboles sont codés dans un dictionnaire• La base de faits est une matrice à 3 colonnes

contenant les codes des symboles des faits• La base de règle est une matrice à 5 colonnes

contenant les codes des symboles des règles

26


Structure des données (1)

Pierre,est un,PersonnePierre,ami de,PaulPaul,ami de,Louis

0 Pierre

1 est un

2 Personne

3 ami de

4 Paul

5 Louis

6 R1

7 IF

8 ?X

9 ?Y

10 ?Z

11 THEN

R1,IF,?X,ami de,?YR1,IF,?X, est un,PersonneR1,IF,?Y,ami de,?ZR1,THEN,?X,ami de,?Z

0 1 2

0 3 4

4 3 5

6 7 8 3 9

6 7 8 1 2

6 7 9 3 10

6 11 8 3 10

27


Structure des données (2)

• Donc on va essentiellement manipuler des matrices de codes dictionnaire• => Classe Java: M• Et des vecteurs de codes dictionnaire• => Classe Java: V• Et on a besoin d’un dictionnaire• => Classe Java: D

28


Classe Java Vecteur « V » (suggestions et exemples) V: un ArrayList de Integer

V ( ) /** créé un vecteur videV (int n,Integer Val) /** créé un vecteur de N fois ValV(Integer I) /** créé un vecteur de 1 élément

Méthodes sur V

Int membre (Integer I) /** rend 0 si I n’est pas dans V, 1 sinon

Void Indicer (V indice) /** undice le vecteur par un vecteur d’indices

Void ajout_integer (Integer I) /** ajoute un élément à un vecteur

Void concat(V V2)b /**Concatene un vecteur à un vecteur

Integer Get (Int i) /** rend le ième élément

Void Set (Int i, Integer Val) /** affectation élément i

V Union () /** rend l’ensemble des éléments d’un vecteur

Void lister (D d) /** liste les symboles d’un vecteur décodés avec le dictionnaire

29


Classe Java Matrice « M » (suggestions et exemples)

M est un ArrayList de V (vecteur) /** un Arraylist de vecteurs qui sont les colonnes de la matrice

M(String s,D d) /** matrice 1 ligne 1 colonne contenant le code de s dans D

M(Integer i) /** matrice 1 ligne 1 colonne contenant i

Void Add_Vect_C (V c) /** ajoute un vecteur à une matrice en dernière colonne

Void Add_Vect_L (V c) /** ajoute un vecteur à une matrice en dernière ligne

Void Add_Mat_C(M m) /** ajoute une matrice à droite

Void Add_Mat_L(M m) /** ajoute une matrice en bas

V getcol(int i) /** rend un vecteur égal à la i ème colonne

Void setcol (int i,V) /** remplace la ième colonne par un vecteur

Etc, etc …

30


Classe Java Dictionnaire « D » (suggestions et exemples)

D est un ArrayList de String

Méthodes

Int code(String s) /** donne le code de la chaîne s dans le dictionnaire, la rajoute si absente

String decode(int i) /** rend la chaine d’un code

V code(String[] s) /** le vecteur des codes d’un tableau de chaînes

Etc …

31


Opération clé: la jointure

• Programmation de la jointure en Java

• Une jointure va être une CLASSE Java

• JMM( M A,int iA,M B,int iB)

• Jointure entre A et B selon colonnes iA, iB

• JMM( M A,int iA,M B,int iB). get() va rendre le résultat

32


APPLIQUER UNE REGLE = opération de JOINTURE


AA ami CC

AA ami DD

AA ami EE

BB ami EE

Ancien !

Nouveau !

Nouveau !

Nouveau !



Principe de la Jointure

• Soit un élément commun E entre les deux colonnes de la jointure

• Si il est présent nA fois dans une colonne et nB fois dans l’autre, ceci va générer nA*nB lignes dans le résultat

34


ExempleLA1 AA

LA2 AA

LA3 BB

LA4 BB

LA5 BB

LA6 CC

LA7 DD

AA LB1

BB LB2

BB LB3

EE LB4

CC LB5

FF LB6

GG LB7

AA : 2 * 1 = 2

BB : 3 * 2 = 6

CC : 1 * 1 = 1

Donc le résultat aura 9 lignes

35


ExempleLA1 AA

LA2 AA

LA3 BB

LA4 BB

LA5 BB

LA6 CC

LA7 DD

AA LB1

BB LB2

BB LB3

EE LB4

CC LB5

FF LB6

GG LB7

LA1 AA AA LB1

LA2 AA AA LB1

LA3 BB BB LB2

LA3 BB BB LB3

LA4 BB BB LB2

LA4 BB BB LB3

LA5 BB BB LB2

LA5 BB BB LB3

LA6 CC CC LB5

36


LA1 AA

LA2 AA

LA3 BB

LA4 BB

LA5 BB

LA6 CC

LA7 DD

AA LB1

BB LB2

BB LB3

EE LB4

CC LB5

FF LB6

GG LB7

LA1 AA AA LB1

LA2 AA AA LB1

LA3 BB BB LB2

LA3 BB BB LB3

LA4 BB BB LB2

LA4 BB BB LB3

LA5 BB BB LB2

LA5 BB BB LB3

LA6 CC CC LB5

Il suffit de calculer les indices des lignes présentes dans le résultat:

Depuis M1: 1, 2, 3, 3, 4, 4, 5, 5, 6

Depuis M2: 1, 1, 2, 3, 2, 3, 2, 3, 5

37


Une opération intermédiaire: apparier deux vecteurs

AA

BB

BB

EE

CC

FF

GG

AA

AA

BB

BB

BB

CC

DD

1

2

3

3

4

4

5

5

6

+ =

1

1

2

3

2

3

2

3

5

+

38


Classe ApparierApparier (V va,V vb)

Apparier(va,vb).get_ia: donne le vecteur d’indices pour va

Apparier(va,vb).get_ib: donne le vecteur d’indices pour vb

Bien voir: l’opération va et vb -> ia et ib

est une instancede la classe Apparier

Les résultatssont construits comme attributs internesà l’instance

39


Principes du Moteur d’Inférence en Saturation Naïve

• On part d’un fichier de faits, traduit en une matrice de 3 colonnes M_Faits

• Et d’un fichier de règles, traduit en une matrice de 5 colonnes M_Regles

• On fait tourner le moteur jusqu’à ce qu’il ne produise plus de nouvelles conclusions

• A chaque tour du moteur, on exécute toutes les règles, qui vont produire des conclusions. On ajoute les conclusions nouvellesà la base de faits

• Exécution d’une règle:– Exécuter toutes les hypothèses (c’est le cœur de

l’algorithme)– Exécuter toutes les conclusions

• A la fin, on sort le fichier des conclusions nouvelles

40


Données Principales• Dictionnaire• M_Faits• M_Regles• M_Delta_Global: la totalité des nouveaux faits

accumulée• M_Delta_Un_Tour: les nouveaux faits produits

par un tour du moteur• M_Delta_Une_Regle: les nouveaux faits produits

par l’exécution d’une règle

41


Lecture des fichiers de règleset faits

Traduire un fichier en une matrice

Et codage dans un dictionnaire

Via une méthode sur une matrice de classe M

M.Lire_fichier(File F, D d)

42


REPRESENTATION ETEXECUTION D’UNE REGLE

43


Représentation d’une règle

La matrice des règles a 5 colonnes : M_regles

Calcul de l’ensemble des noms des règles:

V M_regles.getcol(0).union()

Retrouver les lignes d’une règle de nom R

m = matrice 1 ligne 1 colonne qui contient R

M_lignes_regle = Jointure(M_regles,0,m,0)

Séparer les hypothèses et les conclusions

mh = matrice 1 ligne 1 colonne qui contient le code de ‘IF’

mc=matrice 1 ligne 1 colonne qui contient le code de ‘THEN’

M_hypos_regle = Jointure(M_lignes_regle,1,mh,0)

M_concl_regle = Jointure(M_lignes_regle,1,mc,0)

44


NOTES DE PROGRAMMATION

Il est utile de faire un constructeur de matrice qui créé une matrice constituée du code d’une unique chaîne de caractères:

M(‘IF’) M(‘THEN’) Utilisable par exemple dansJMM(M_regles,1,M(‘IF’)).

On pourrait aussi encapsuler ça dans une méthode qui filtre une matrice

M.filtre(1, ’IF’) sur une colonne donnée

45


Exécution d’une règle

A la fin des hypothèses, il faut l’ensemble de toutes les combinaisons des variables:

(X,Y,Z, …)

⇒Construction d’une table des N-uplets

⇒C’est la matrice « M_XYZT»

⇒Où chaque colonne correspond à une variable


46


EVALUATION DES HYPOTHESES D’UNE REGLE:

Construire le produit cartésien des variables:

X / habite à Z / et Y / habite à T / et X / ami de Y /

et T / situé en / France et Y / est né à / Z

X Z Y T Attention!:Autant de colonnes que de variables (4) et non qu’autant d’hypothèses (5)!C’est comme trouver toutes les solutions d’une équation en X,Y,Z,T

47


La matrice «M_XYZT »

Toutes les combinaisons des variables (comme en Prolog)

X ami Y et Y ami Z => X ami Z

=> Tableau à 3 colonnes: X,Y,Z

48


M_XYZTX ami Y et Y ami Z => X ami Z

X Y Z

AA BB CC

AA BB DD

AA CC EE

BB CC EE

49


Donc: Un Vecteur V_XYZT qui nomme les colonnes par un nom de variableUne Matrice M_XYZT

AA BB CC

AA BB DD

AA CC EE

BB CC EE

X Y ZOn représente toutes les combinaisons possibles des variables qui satisfont les conditions en hypothèses

50


Si une nouvelle hypothèse arrive

X ami Y et Y ami Z et …T habite à U

AA BB CC

AA BB DD

AA CC EE

BB CC EE

X Y Z

On va interdire ce cas:

Cela ferait un produit cartésien

Entre toutes les valeurs de (X,Y,Z) d’une part et de (T,U) d’autre part.

Une hypothèse –sauf la première- doit avoir au moins une variable commune avec les précédentes

NB: on peut aussi l’autoriser; il suffit de construire le produit cartésien …

51


Ce qui revient à dire: Importance de l’ordre des hypothèses

Au lieu de:

Si

?X ami ?Y

?Z ami ?T

?X père ?Z

?Y père ?T

Alors …

Il faut écrire :

Si

?X ami ?Y

?X père ?Z

?Y père ?T

?Z ami ?T

Alors …

CF Optimisation des requêtes SQL

52


Restriction

Pour l’instant, on se limite à des hypothèses ne comportant que des variables, et pas des constantes:

?X ami ?Y est permis

?X ami Paul est interdit

(sera étendu dans un second temps)

53


Exécution d’une Règle

Une règle est représentée par deux M:

M_H : matrice 3 colonnes de ses hypothèses

M_C : matrice 3 colonnes de ses conclusions

Programme:

Exécuter la première hypothèse

Exécuter les hypothèses suivantes

Exécuter chaque conclusion54


Exécution de la première hypothèse d’une règle (1)

Exemple: X ami YCela consiste à initialiserV_XYZTM_XYZT

Mettre les variables X et Y dans V_XYZTMettre dans M_XYZT tous les X et Y tels que X R Y

Cas particulier à traiter plus tard:Une hypothèse peut très bien être de la forme X R XExemple: X est l’employeur de X

55


Exécution de la première hypothèse d’une règle (2)Exemple: X ami YCela consiste à initialiserV_XYZTM_XYZTEn faisant Mettre les variables X et Y dans V_XYZT

Mettre dans M_XYZT tous les X et Y tels que X R Y

Pour cela, il suffit de faire une jointure entre la base de faits et la matrice mr = 1 ligne 1 colonne constituée du seul élément R

mr = new M(‘R’)

JMM(Base de Faits,1,mr,0)

Et d’initialiser M_XYZT avec les colonnes contenant les sujets et les compléments de la jointure.

56


AA ami CC

AA ami BB

AA ami EE

BB ami EEX Y

Si la première hypothèse est X ami Y

1) On recherche tous les faits « ami »

2) On initialise V_XYZT et M_XYZT

AA CC

AA BB

AA EE

BB EE

V_XYZT :

M_XYZT :

57


Exécution des Hypothèses Suivantesd’une règle

V_XYZT et M_XYZT ont déjà des valeurs

Que l’on va modifier avec la nouvelle hypothèse

58



X ami Y et Y ami Z et …Y travaille à T

AA BB CC

AA BB DD

AA CC EE

BB CC EE

X Y Z Déterminer la position de Y et T dans V_XYZT

Pos_Y = 1

Pos_T = Hors (convention)

Donc méthode sur vecteur:

Int Get_position (Int)

Il faut retrouver dans la base de faits les Y déjà présents dans M_XYZT qui travaillent pour des T …

59




AA BB CC

AA BB DD

AA CC EE

BB CC EE

X Y Z

Calculer un extrait de la base de faits

BB travaille DD1

CC travaille DD2

CC travaille DD3

HH travaille DD4

60




AA BB CC

AA BB DD

AA CC EE

BB CC EE

X Y Z

Faire la jointure entre M_xyzt et l’ extrait de la bdf:

BB travaille DD1

CC travaille DD2

CC travaille DD3

HH travaille DD4

C’est-à-dire:

JMM (M_XYZT , 1,M_Extrait , 0)

61




AA BB CC

AA BB DD

AA CC EE

BB CC EE

X Y Z

BB travaille DD1

CC travaille DD2

CC travaille DD3

HH travaille DD4

C’est-à-dire:

JMM (M_XYZT , 1,M_Extrait , 0)

62


Ce qui donne un nouveau M_XYZT …

AA BB CC DD1

BB BB DD DD1

AA CC EE DD2

BB CC EE DD2

AA CC EE DD3

BB CC EE DD3

… et un nouveau V_XYZT en rajoutant T

X Y Z T

63



X ami Y et Y ami Z et …X chef de Y

AA BB CC

AA BB DD

AA CC EE

BB CC EE

X Y ZDéterminer la position de X et Y dans V_XYZT

Pos_X= 0

Pos_Y = 1

Il faut retrouver dans la base de faits les X et Y déjà présents dans M_XYZT tels que X travaille pour Y

64

Ici, on n’ajoute pas de nouvelle colonne, car pas de nouvelle variable. On filtre: on garde seulement les lignes dont le couple X, Y vérifie X chef de Y, donc est présent dans une ligne de l’extrait


IMPORTANTPour les hypothèses suivantes (après la première) il y

a trois cas à traiter

?Z R ?T?Z est une anciennevariable et ?T est une nouvellevariable

?Z est une nouvellevariable et ?T est une anciennevariable

?Z est une ancienne variable et ?T est une ancienne variable

Rappel: le cas nouvelle / nouvelleest interdit (sauf à construire le produit cartésien)

Dans chacun des trois cas, il y a des jointures différentes à faire entre M_xyzt et la base de faits

65


Exécution des Conclusions d’une Règle

On a exécuté toutes les hypothèses d’une règle

On a V_xyzt et M_xyzt qui nous donnent toutes les combinaisons de variables qui satisfont toutes les hypothèses.

Important: M_xyzt peut être vide: aucune ligne, il n’y a aucune solution !

(On peut arrêter l’exécution d’une règle dès qu’une hypothèse a rendu M_xyzt vide)

Si M_xyzt n’est pas vide, on va générer chacune des conclusions

66


Si X ami Y et Y ami Z alors X ami Z

AA ami CC

AA ami DD

AA ami DD

BB ami EE

X Y Z

Rechercher les positions de X et Z dans V_xyzt: 0 et 2

Construire la matrice de 2 colonnes avec les colonnes 0 et 2 de M_xyzt et ajouter « ami » au milieu

AA BB CC

AA BB DD

AA CC DD

BB CC EE

Et dédoublonnez les lignes présentes plusieurs fois (union)

67


Génération d’une Conclusion (suite)

Les conclusions sont ajoutées au M_delta_une_regle si elles ne sont pas déjà présentes dans la base de faits

68


Cœur du MoteurM_delta_global = M vide

M_delta_un_tour = M contenant une valeur bidon (non vide)

Tant que M_delta_un_tour non vide Faire

M_delta_un_tour = videPour chaque règle

Exécuter la règle sur la base de faits

Soient M_delta_une_regle les conclusionsM_delta_une_regle = M_delta_une_regle moins Base_de_Faits

Si M_delta_une_regle non vide:

Ajouter M_delta_une_regle à M_Faits

Ajouter M_delta_une_regle à M_delta_un_tour

Ajouter M_delta_une_regle à M_delta_global

69


Autres Méthodes Utiles

Dédoublonnaged’une matrice: supprimer les doublons de lignes de M1

Intersection de deux matrices M1 et M2 : les lignes qui sont présentes dans les deux

M1 moins M2: ne garder de M1 que les lignes qui ne sont pas présentes dans M2

Implémentation possible de ces opérations: rendre le vecteur des indices des lignes de M1 à conserver (comme dans le cas de la méthodes Apparier)

70


Note d’implémentation

Les fonctions Apparier, Dédoublonnage, Intersection, Moins peuvent s’implémenter:

-- de manière naïve avec des boucles imbriquées

-- optimisées avec des tris

-- optimisées avec du h-code

71


Mieux que la saturation naïve:La méthode «DELTA DRIVEN »

(J. Rohmer 1982)

72


LA METHODE NAIVE DE SATURATION: A CHAQUE FOIS ON REFAIT LES MEMES CALCULS …

POUR OPTIMISER:

1) IL FAUT RELANCER LE MOTEUR SEULEMENT AVEC LES NOUVEAUX TRIPLETS

2) IL FAUT ALLER CHERCHER LES REGLES QUE LES NOUVEAUX VONT EXCITER

C’EST L’ALGORITHME:

« DELTA DRIVEN » (JR 1982)

73


Algorithme DELTA-DRIVEN

Principe: intégrer les dérivées des règles

P Q => R

se transforme en∆PQ ∪ ∆QP => ∆RExemple:

X / ami / Y et Y / ami / Z => X / ami / Z

se transforme en deux règles différentes:

X / ∆ami / Y et Y / ami / Z=> X / ∆ami / Z

Y / ∆ami / Z et X / ami / Y=> X / ∆ami / Z 74


Y / ∆ami / Z et X / ami / Y=> X / ∆ami / Z

« les amis de mes nouveaux amis sont mes nouveauxamis » !

Distinction entre base des triplets et base des «DELTA TRIPLETS »

X / ∆ami / Y et Y / ami / Z=> X / ∆ami / Z

« les nouveauxamis de mes amis sont mes nouveauxamis » !

Mais aussi !:

75


X / ∆ami / Y et Y / ami / Z=> X / ∆ami / ZAA ami BB

BB ami CC

AA ami CC

DELTA de DEPART

DELTA de ARRIVEE

76


ECORCHE FINAL DU MOTEUR

REGLES

D’ORIGINEH1 H2

H3 H4 H5

=> C1

=> C2 C3

BASE de Triplets CUMUL des Delta

H2

H1

H4 H5

H3 H5

H3 H4

=> ∆∆∆∆C1

=> ∆∆∆∆C1

=> ∆∆∆∆C2 ∆∆∆∆C3

=> ∆∆∆∆C2 ∆∆∆∆C3

=> ∆∆∆∆C2 ∆∆∆∆C3

∆∆∆∆

∆∆∆∆

∆∆∆∆H1

∆∆∆∆H2

∆∆∆∆H3

∆∆∆∆H4

∆∆∆∆H5

DELTA

REGLES

New Only

!

77


Points Importants:

Réordonner les hypothèses des règles

Y compris pour les Delta-Règles

Opérations de base sur des tables

-- sélection

-- jointure

Donc:

Pour travail en mémoire (par exemple en Java): créer des objets de type table, et des opérateurs de sélection et jointure sur table

Pour travail sur de gros volumes, ce moteur peut être interprété et même compiléen SQL

78


CECI C’ETAIT LE

CHAINAGE AVANT: « on cherche tout sans but »

MAIS ON VEUT SOUVENT FAIRE

DU CHAINAGE ARRIERE: « on a un but »

« Quels sont les Amis de Pierre » ?

« Est-ce que Pierre et Paul sont Amis » ?

C’est plus délicat …

PROLOG fait du chaînage arrière, mais il peut boucler

LA METHODE D’ALEXANDRE (Rohmer, Lescoeur, Kérisit 1985)

Transforme le chaînage arrière en chaînage avant par transformation des règles selon les buts, sans boucler

Cette méthode fut la première à implémenter efficacement le DATALOG, (http://en.wikipedia.org/wiki/Datalog)

79


PRINCIPE DE LA METHODE D’ALEXANDRE (Très simplifié)

Soit la règle P Q => R

Elle se transforme en trois règles:

Si j’ai le problème de trouver R

Alors j’ai le problème de trouver P

Et je dois continuer après P

Si j’ai la solution à P

Et que je dois continuer après P

Alors j’ai le problème de trouver Q

Et je dois continuer après Q

Si j’ai la solution à Q

Et que dois continuer après Q

Alors j’ai la solution à R

Bien sûr les règles concluant sur P et Q seront transformées de la même manière

Baptisée d’après Alexandre le Grand qui trancha le nœud gordien: ici on coupe aussi un prédicat en 3 faits:

•Un problème

•Une continuation

•Une solution

80


X Parent Y => X Anc Y

(X Parent Y) (Y Anc Z) => X Anc Z

On transforme les règles en introduisant les Problèmes, Continuations et Solutions:

(Pb_Anc_10 On X) (X Parent Y) => X Sol_Anc_10 Y

(Pb_Anc_10 On X) (X Parent Y) => (Pb_Anc_10 On Y) (X Cont_Anc_10 Y)

(Y Sol_Anc_10 Z) (X Cont_Anc_10 Y) => X Sol_Anc_10 Z

LE CELEBRE PROBLEME DES ANCETRES

81


82


APPLICATIONS AUX RESEAUX SOCIAUX

« SOCIAL COGNITIVE RULES »

We can formulate several theories about Trust:

I trust people trusted by people I trust:

(X trusts Y) (Y trusts Z) => X trusts Z (transitive closure).

Another theory is:

I trust people who trust the same people as me:

(X trusts Y) (Z trusts Y) => X trusts Z

(which is quite different from a transitive closure) 83


(X trusts Y) (Z trusts Y) => X trusts Z

Se transforme via la Méthode d’Alexandre en:

R1: (Pb_Trust_10 On X) (X Trust Y) => (Pb_Trust_01 On Y) (Y Cont_Trust_10X)

R2: (X Cont_Trust_10 Y) (Z Trust Y) => X Sol_Trust_10 Z

R3 : (X Cont_Trust_10 Y) (Z Sol_Trust_10 Y) => X Sol_Trust_10Z

R4: (Pb_Trust_10 On X) (X Sol_Trust_10 Y) => (Pb_Trust_01 On Y) (XCont_Trust_10 Y)

R5: (Pb_Trust_01 On Z) (Z Trust Y) => (Pb_Trust_01 On Y) (Z Cont_Trust_01Y)

R6: (Pb_Trust_01 On Z) (Z Sol_Trust_01 Y) => (Pb_Trust_01 OnY) (ZCont_Trust_01 Y)

R7: (X Sol_Trust_01 Y) (Z Cont_Trust_01 Y) => X Sol_Trust_01Z

R8: (X Trust Y) (Z Cont_Trust_01 Y) => X Sol_Trust_01 Z

84


PASSER DU MOTEUR D’INFERENCE DELTA-DRIVEN

A UNE ARCHITECTURE DE SYSTEME REACTIVE

(parfois appelée aussi EVENT- DRIVEN)

PRINCIPE:

Quand des éléments d’information nouveaux arrivent de l’extérieur (messages, importations de fichiers, saisie manuelle)

On va faire comme si c’étaient des conclusions de règles, on les

prend comme des Delta ∆∆∆∆Et on lance les Delta-Règles avec

Qui vont relancer tout le moteur

85


NOUVELLE

INFORMATION

ARCHITECTURE REACTIVE: DELTA-DRIVEN

Relance du moteur

Mise à jour

de la base

86


ARCHITECTURE DELTA-DRIVEN

+ METHODE D’ ALEXANDRE

= RAFRAICHISSEMENT AUTOMATIQUE

DES ALERTES

DES CONSIGNES DE RECHERCHE

DES CONSIGNES DE SURVEILLANCE

PERMANENTES

EN MODE « DATA STREAM»

87


On veut surveiller « Qui sont les amis de Paul ?»

Installation des delta règles d’Alexandre qui concluent sur « amis de quelqu’un »

Injection du problème

« je cherche les amis de Paul » comme nouvelle information

Premiers résultats:

Les amis actuels de Paul

Arrivée permanente de nouvelles infos ‘lointaines’:

« Max ami de Leo »

« Henri ennemi de Fred »

Déduction permanente de nouveaux amis de Paul, via le jeu des règles d’Alexandre avec les

Problèmes

Continuations

Solutions

1

2

3

4

5

88

Software

Construire un moteur d'inférence