Raisonnement en présence d'incohérence : de la compilation de bases de croyances stratifiées à l'inférence à partir de bases de croyances partiellement pré-ordonnées, Reasoning under inconsistency : from the compilation of stratified belief bases to reasoningfrom partially preordered belief bases

De
Publié par

Sous la direction de Alger Institut National de formation en Informatique, Salem Benferhat, Habiba Drias
Thèse soutenue le 04 décembre 2009: Artois
Nous nous intéressons dans cette thèse aux approches basées sur la restauration de la cohérence à partir de bases de croyances stratifiées ainsi qu'à partir de bases de croyances partiellement préordonnées (BCPP). Dans le premier cas, nous nous attaquons aux problèmes de complexité en proposant trois nouvelles approches de compilation que nous qualifions de flexibles en étant paramétrées par n'importe quel langage cible de compilation. La première concerne l'inférence possibiliste et s'adapte facilement à l'inférence linéaire. La seconde approche se rapporte à l'inférence lexicographique et se base sur la notion de contraintes de cardinalité Booléennes. Nous introduisons aussi une nouvelle compilation pour l'inférence MSP (pour Minimum de Specificity Principle). En ce qui concerne le raisonnement à partir de BCPPs qui offrent plus de flexibilité dans de nombreuses situations, notre première contribution consiste en l'introduction d'une extension de l'inférence lexicographique classique qui revêt un vif intérêt. La seconde contribution dans ce même cadre, est l'étude comparative des différentes relations d'inférence à partir de BCPPs relativement à la complexité, les propriétés logiques et la prudence. Une dernière contribution est l'application du raisonnement en présence d'incohérence dans le cadre de la détection d'intrusions coopérative. En effet, nous proposons une nouvelle approche de corrélation d'alertes. Cette approche se base sur le raisonnement à partir de BCPPs exprimées en logiques de description qui sont bien adaptées à la représentation des informations structurées tout en garantissant la décidabilité du raisonnement.
-Raisonnement en présence d'incohérence
-Compilation
-Logiques de description
-Détection d'intrusions
-Logique possibiliste
-Inférence lexicographique
-Inférence linéaire
-Complexité
-Prudence
-Propriétés logiques
In this thesis, we are interested in coherence based approaches from both stratified belief bases and partially preordered belief bases (PPBB). In the first case, we tackle the complexity problems by proposing three new compilation approaches. The first one is about the possibilistic inference and applies easily to linear inference. The second approach is relative to lexicographic inference and is based on Boolean cardinality constraints. We also introduce a novel compilation approach for MSP entailment (MSP for Minimum Specificity Principle). As to reasoning from PPBBs which offer much more flexibility in many situations, our first contribution consists in extending the lexicographic inference which has interesting properties. The second contribution is a comparative study of the different inference relations from PPBBs with respect to three key dimensions, namely the complexity, the logical properties and the cautiousness. The last contribution is the application of reasoning under inconsistency in the case of intrusion detection. More precisely, we propose a new correlation approach. This latter is based on reasoning from PPBBs expressed in description logics, which are suitable to represent structured informations by ensuring the decidability of reasoning.
Source: http://www.theses.fr/2009ARTO0409/document
Publié le : lundi 31 octobre 2011
Lecture(s) : 30
Nombre de pages : 227
Voir plus Voir moins

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-

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.