Cette publication est accessible gratuitement
Télécharger

Universit´e d’Artois Facult´e des sciences Jean Perrin
Raisonnement en pr´esence d’incoh´erence :
de la compilation de bases de croyances stratifi´ees
`a l’inf´erence `a partir de bases de croyances
partiellement pr´eordonn´ees
`THESE
pour l’obtention du grade de
Docteur de l’Universit´e d’Artois
(sp´ecialit´e informatique)
par
SafaYahi-Mechouche
devant le jury compos´e de
Pascal Nicolas Professeur des Universit´es, Universit´e d’Angers (rapporteur)
HenriPrade Directeur de recherche, Universit´e Paul Sabatier (rapporteur)
Salem Benferhat Professeur des Universit´es, Universit´e d’Artois (directeur de th`ese)
HabibaDrias Professeur des Universit´es, USTHB (co-directrice de th`ese)
Sylvain Lagrue Maˆıtre de Conf´erences, Universit´e d’Artois (examinateur)
Centre de Recherche en Informatique de Lens (CRIL)Table des mati`eres
Introduction 1
´I Etat de l’art 9
1 Logique propositionnelle 11
11
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2 Syntaxe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3 S´emantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2 Complexit´e 19
19
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2 Notions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 Machines de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4 Classes de complexit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.5 Hi´erarchie polynomiale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3 Propri´et´es logiques 31
31
i`ii TABLE DES MATIERES
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2 Raisonnement cumulatif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Raisonnement cumulatif avec boucle . . . . . . . . . . . . . . . . . . . . . . 36
3.4 Raisonnement pr´ef´erentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.5 Raisonnement rationnel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4 Approches bas´ees sur la restauration de la coh´erence 43
43
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2 Pr´eliminaires formels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.3 Inf´erence `a partir de bases de croyances totalement pr´eordonn´ees . . . . . . 49
4.4 Inf´erence `a partir de bases de croyances partiellement pr´eordonn´ees . . . . . 63
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5 Compilation de connaissances 69
69
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.2 Principe de la compilation de connaissances . . . . . . . . . . . . . . . . . . 70
5.3 M´ethodes classiques de compilation exacte . . . . . . . . . . . . . . . . . . . 72
5.4 M´ethodes classiques de compilation approximative . . . . . . . . . . . . . . 76
5.5 La carte de compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.6 Compilation en pr´esence d’incoh´erence . . . . . . . . . . . . . . . . . . . . . 93
5.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
II Contributions 99
6 Compilation des inf´erences possibiliste et lin´eaire 101
101
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6.2 Principe de compilation de notre approche . . . . . . . . . . . . . . . . . . . 103
6.3 Inf´erence possibiliste simple . . . . . . . . . . . . . . . . . . . . . . . . . . . 104`TABLEDES MATIERES iii
6.4 Inf´erence possibiliste pond´er´ee et conditionnement possibiliste . . . . . . . . 106
6.5 Inf´erence lin´eaire a` partir de bases de croyances stratifi´ees . . . . . . . . . . 107
6.6 R´esultats exp´erimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
6.7 Conlusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
7 Compilation de l’inf´erence lexicographique 113
113
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
7.2 Rappels sur le calcul de l’inf´erence lexicographique . . . . . . . . . . . . . . 114
7.3 Contraintes de cardinalit´e Bool´eennes . . . . . . . . . . . . . . . . . . . . . 115
7.4 Nouvelle approche de compilation pour l’inf´erence lexicographique . . . . . 117
7.5 Comparaison aux travaux connexes . . . . . . . . . . . . . . . . . . . . . . . 121
7.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
8 Compilation de l’inf´erence MSP 123
123
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
8.2 Rappel sur le traitement possibiliste des th´eories des d´efauts. . . . . . . . . 125
8.3 Compilation des th´eories des d´efauts possibilistes . . . . . . . . . . . . . . . 127
8.4 Flexibilit´e de l’approche propos´ee . . . . . . . . . . . . . . . . . . . . . . . . 133
8.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
9 Inf´erence lexicographique `a partir de bases partiellement pr´eordonn´ees137
137
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
9.2 Inf´erence lexicographique bas´ee-compatibles . . . . . . . . . . . . . . . . . . 138
9.3 Pr´ef´erence lexicographique partielle entre sous-bases coh´erentes . . . . . . . 142
9.4 Inf´erence lexicographique bas´ee sur les sous-bases coh´erentes pr´ef´er´ees . . . 149
9.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
´10 Etude comparative 155
155`iv TABLE DES MATIERES
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
10.2 R´esultats de complexit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
10.3 Analyse de prudence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
10.4 Propri´et´es logiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
10.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
11 Gestion de l’incoh´erence en d´etection d’intrusions 187
187
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
11.2 Principe de la d´etection d’intrusions . . . . . . . . . . . . . . . . . . . . . . 189
11.3 Introduction aux logiques de description . . . . . . . . . . . . . . . . . . . . 190
11.4 Repr´esentation en DLs des connaissances en d´etection d’intrusions . . . . . 197
11.5 Nouvelle approche de corr´elation d’alertes bas´ee sur la gestion de l’incoh´erence204
11.6 Cas d’utilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
11.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
12 Conclusion g´en´erale 209
209Introduction g´en´erale
12 INTRODUCTION
Contexte et motivations
La repr´esentation des connaissances et le raisonnement de sens commun a` partir de
celles-ci constituent l’´epine dorsale de l’Intelligence Artificielle. En supposant que ces con-
naissances sont certaines, compl`etes et donc coh´erentes, la logique classique constitue un
outil tr`es satisfaisant d’un point de vue expressivit´e. N´eanmoins, en r´ealit´e, les connais-
sancesdonton disposene sontpastoujoursaussiparfaites.Eneffet, l’incoh´erence survient
dans de nombreux contextes, a` l’image du raisonnement tol´erant les exceptions, le raison-
nement avec incertitude, la r´evision de croyances, la fusion d’informations issues de dif-
f´erentessourcesquipeuventˆetreconflictuelles,etc.Danscecas,lalogiqueclassiquedevient
tr`es vite obsol`ete car l’application de l’inf´erence classique en pr´esence d’incoh´erence con-
duit a` une trivialisation, dans le sens ou` elle permet de d´eduire n’importe quoi (principe
d’ex falso quodlibet sequitur).
Afindepermettrederaisonnerenpr´esenced’incoh´erencesanstrivialisation, diff´erentes
approches ont ´et´e mises au point. D’une mani`ere g´en´erale, ces approches peuvent ˆetre
scind´ees en deux grandes familles. D’une part, on a celles qui affaiblissent la relation
d’inf´erence classique, `a l’instar des logiques paraconsistantes [32] et des approches argu-
mentatives [10, 11]. D’autres part, on a les approches qui affaiblissent les croyances elles
mˆemes telles que les approches bas´ees sur la restauration de la coh´erence.
Les approches bas´ees sur la restauration, auxquelles nous nous int´eressons dans cette
th`ese, consistent a` g´en´erer dans un premier temps des sous-bases coh´erentes pr´ef´er´ees,
ensuite a` appliquer l’inf´erence classique sur ces sous-bases. Ainsi, de telles approches, de
parleurprincipe,sontqualifi´eesdetr`esnaturelles.Enoutre,ellespermettentdetirerprofit
de toute la machinerie d´evelopp´ee dans le cadre de la logique classique. D’ou` la popularit´e
des approches bas´ees sur la restauration de la coh´erence en termes de raisonnement en
pr´esence d’incoh´erence. Maintenant, parmi ces approches, on peut distinguer celles qui
sont d´efinies par rapport a` des bases de croyances totalement pr´eordonn´ees ou stratifi´ees,
et celles qui sont d´edi´ees a` des bases de croyances partiellement pr´eordonn´ees.
Danslecadredebasesdecroyancestotalementpr´eordonn´ees,lescroyances,c’est-a`-dire
les connaissances incertaines, sontmuniesd’unpr´eordretotal quiest une relation r´eflexive
et transitive, via laquelle toutes les croyances sont deux a` deux comparables. Les relations
d’inf´erence les plus fr´equemment utilis´ees dans ce cas sont l’inf´erence possibiliste [45],
l’inf´erence lin´eaire [79], l’inf´erence lexicographique [9, 67] ainsi que l’inf´erence relative a` la
pr´ef´erence pour l’inclusion [21, 28]. Surle plan pratique, ces relations d’inf´erence suscitent
un int´erˆet grandissant. En effet, elles trouvent de plus en plus d’applications dans de
nombreuxdomaines, `a l’image de la s´ecurit´e informatique. Dans ce contexte, citons a` titre
d’exemple, les mod´elisations logiques des politiques de s´ecurit´e informatique, ou` les r`egles
de controˆle d’acc`es pr´esentent souvent des exceptions ce qui g´en`ere des conflits [6]. Ces
mod´elisations s’appuient sur des approches bas´ees sur la restauration de la coh´erence a`INTRODUCTION 3
partir de bases de croyances stratifi´ees. .
Toutefois, d’un point de vue calculatoire, l’expressivit´e additionnelle offerte par ces
relations d’inf´erence s’accompagne d’un saut de complexit´e. En effet, elles sont plus couˆ-
teuses que l’inf´erence classique, qui est d´ej`a un probl`eme calculatoirement ´epineux. Plus
pr´ecis´ement, dans le cas ou` les croyances sont d´ecrites en logique propositionnelle (et non
pas en logique dupremierordre), ces relations d’inf´erencen´ecessitent au moins unnombre
d’appels logarithmique `a un oracle NP, et au pire des cas un nombre d’appels exponentiel
a` un oracle NP. Clairement, cet aspect est tr`es limitatif en pratique, notamment dans des
contextes ou` le temps de r´eponse constitue un facteur pr´epond´erant. Par exemple, pour
la mod´elisation des politiques de controˆle d’acc`es dans un contexte m´edical, il est crucial
qu’un m´edecin puisse avoir rapidement le droit d’acc`es au dossier m´edical d’un de ses
patients en cas d’urgence.
Par ailleurs, la compilation de connaissances [23, 37, 88, 74] est parmi les approches
les plus prometteuses qui permettent d’appr´ehender les probl`emes li´es a` la complexit´e du
raisonnementlogique.Eneffet,cetteapproche,qu’estenpleinexpansion,s’estav´er´eeassez
efficace pour traiter de nombreuses instances de probl`emes en pratique. Le principe sous-
jacent est d’effectuer un pr´etraitement sur la base de connaissances en vue de g´en´erer hors
ligne une base compil´ee a` partir de laquelle le raisonnement en ligne devient plus efficace
par rapport au raisonnement depuis la base initiale, voire mˆeme polynomial. Donc, l’id´ee
directrice est de d´eplacer la surcharge de travail de la phase en ligne vers la phase hors
ligne. Comme la phase hors ligne n’est appel´ee qu’une seule fois, l’effort d´eploy´e lors de la
g´en´eration de la base compil´ee sera amorti par les multiples phases en ligne.
Actuellement,ondisposed’unr´epertoireconsid´erabledelangagesciblesdecompilation
dans le cadre de la logique propositionnelle, qui sont d´eriv´es du langage NNF (pour Nega-
tion Normal Form), et qui sont issus de travaux en Intelligence Artificielle, en v´erification
formelle et en informatique de mani`ere g´en´erale [37]. Ces langages diff`erent d’abord rela-
tivement aux op´erations logiques (telles que la d´eduction de clauses, l’oubli de variables,
le test d’´equivalence, etc) qu’ils permettent d’accomplir en temps polynomial. Ils se dis-
tinguent aussi en termes de leur efficacit´e spatiale connue sous le nom de concision. Ainsi,
les langages DNNF (pour Decomposable Negation Normal Form) et les impliqu´es premier
PI (pour Prime Implicates) revˆetent une importance capitale parmi les langages cibles
de compilation. En effet, ces langages permettent d’effectuer un bon nombre d’op´erations
logiques suffisantes pour de nombreuses applications. De plus, il est connu que DNNF est
plus concis que tous les autres langages cibles de compilation except´e PI. En revanche, on
sait que PI n’est pas plus concis que DNNF mais on ignore jusqu’`a pr´esent l’inverse.
Or, l’application directe de ces langages sur des bases incoh´erentes m`ene, tout comme
l’inf´erence classique, a` une trivialisation. Par exemple, la compilation DNNF d’une base
incoh´erente se r´esume a` la contradiction. Par cons´equent, d’autres approches de compila-
tion en pr´esence d’incoh´erence, notamment pour l’inf´erence a` partir de bases de croyances4 INTRODUCTION
stratifi´ees, ont ´et´e propos´ees tout en exploitant un des langages de compilation classique.
Ces approches comprennent essentiellement la compilation propos´ee par Coste-Marquis et
Marquis [31] et celle introduite par Benferhat et Prade [15] qui se basent sur le langage
DNF,ainsiquecelled´evelopp´eparCayrol,Lagasquie-SchiexetSchiex[27]quis’appuiesur
le langage OBDD. N´eanmoins, en compilation classique, les langages DNF et OBDD sont
loinsd’ˆetreentˆete delisteparrapportaufacteurconcision.D’ou` lapertinenceded´evelop-
per de nouvelles approches de compilation a` partir de bases de croyances stratifi´ees qui
tirent profit de langages plus concis, notamment DNNF et PI, qui sont compl´ementaires
dans ce sens.
Par ailleurs, la deuxi`eme cat´egorie des relations d’inf´erence bas´ees sur la restauration
de la coh´erence, concerne les bases de croyances partiellement pr´e-ordonn´ees. En effet,
dans ceratines applications, les informations proviennentde plusieurssources h´et´erog`enes,
ind´ependanteset souvententach´ees d’incertitude.Alors, pr´eordonnertotalement ces infor-
mations dans ce cas n’est pas naturel, voire mˆeme contre intuitif, et de plus m`ene souvent
a` des r´esultats qui sont trop aventureux ou risqu´es, et donc qui ne sont pas souhaitables.
Ainsi, les bases de croyances partiellement pr´eordonn´ees offrent plus de flexibilit´e que
les bases stratifi´ees dans de nombreuses situations, afin de repr´esenter des informations
incompl`etes, et ce en permettant d’´eviter de comparer des informations incomparables, ou
des informations dont on ignore le degr´e de priorit´e. Le besoin de raisonner en pr´esence
d’incoh´erence a` partir de bases de croyances partiellement pr´eordonn´ees est d’autant plus
important si l’on consid`ere la dynamiquedes croyances. En effet, mˆeme si les informations
disponibles sont totalement pr´eordonn´ees, il se peut que lors de l’utilisation de certains
op´erateursdemisea`jour[63],l’int´egrationd’unenouvelleinformationm`enea`pr´eordonner
partiellement la base de croyances en question. Enfin,de telles bases peuventˆetre utilis´ees
dans une situation ou` l’on a plusieurs agents qui partagent les mˆemes croyances mais
ou` chacun d´efinit son propre pr´eordre total sur ces mˆemes croyances, et donc la fusion
de toutes ces bases de croyances totalement pr´eordonn´ees g´en`ere une base de croyances
partiellement pr´eordonn´ees.
Plusieurs relations d’inf´erence a` partir de bases de croyances partiellement pr´eordon-
n´ees ont´et´e propos´ees. En g´en´eral, ce sontdes extensions des relations d’inf´erencea` partir
de bases de croyances stratifi´ees, telles que l’inf´erence de l’inclusion bas´ee-compatibles
[21, 62] et l’inf´erence d´emocratique [28] qui ´etendent l’inf´erence de l’inclusion. On a aussi
les inf´erences possibilistes forte et faible [5] qui g´en´eralisent l’inf´erence possibiliste.
N´eanmoins, aucune extension n’a ´et´e d´efinie vis-`a-vis de l’inf´erence lexicographique
en d´epit des caract´eristiques int´eressantes dont elle jouit. Par exemple, une analyse psy-
chologique conduite conjointement par un chercheur en Intelligence Artificielle et des psy-
chologues [8] a r´ev´el´e que l’inf´erence lexicographique pr´esente de fortes similarit´es avec
le raisonnement humain non-monotone. En particulier, les participants a` ce test psy-
chologique ont clairement manifest´e une sensibilit´e a` la majorit´e qui est au cœur de l’in-