Raisonnement à partir d'informations structurées et hiérarchisées : application à l'information archéologique, Reasoning from structured and hierarchized information : application to archeological information

De
Publié par

Sous la direction de Odile Papini, Pierre Drap
Thèse soutenue le 06 mai 2010: Université Paul Cézanne (Aix-Marseille), Aix Marseille 2
La thèse s'inscrit dans le cadre du projet européen VENUS. Dans ce contexte, la photogrammétrie est utilisée pour produire des relevés 3D sur les objets. La connaissance sur ces objets provient à la fois de l'archéologie sous-marine et de la photogrammétrie. Les informations étant structurées, hiérarchisées et parfois incomparables, nous nous sommes intéressés aux bases de croyance partiellement préordonnées. Par ailleurs, l'acquisition des données peut conduire à l'apparition d'incohérence. Nous avons étendu l'approche des R-ensembles à la restauration de la cohérence. Nous avons également proposé un cadre de travail pour la révision de bases de croyance partiellement préordonnées et deux relations d'inférence lexicograhique. nous avons fourni pour ces approches une mise en oeuvre en utilisant la programmation logique avec ASP. Finalement, nous avons implanté notre méthode de restauration de la cohérence dans le contexte de VENUS et nous l'avons testé sur les relevés issus du projet.
-Restauration de la cohérence
-Révision
-Inférence
-Préodre partiel
-R-ensemble
This PHD has been performed within the European VENUS project. In this context, photogrammetry is used to produced 3D survey on objects and the knowledge on studied artefacts comes from both underwater archaeology and photogrammetry. This information being structured, hierachized and sometimes incomparable, we focused on partially preordered belief bases. Data acquisition possibly leads to inconsistency. We extended the Removed Set approach to inconsistency handling. To compare subsets of formulae to remove in order to restore consistency, we introduced the lexicographic comparator. Moreover, we proposed a new framework for the revision of partially preordered belief bases and two lexicographic inference relations. We proposed an implementation stemming from ASP. Finally, we implemented our inconsistency handling method in the VENUS context and we provided an experimental study on 3D surveys of the project.
-Inconsistency handling
-Revision
-Inference
-Partial preorder
-Removed set
Source: http://www.theses.fr/2010AIX22032/document
Publié le : jeudi 27 octobre 2011
Lecture(s) : 41
Tags :
Nombre de pages : 272
Voir plus Voir moins

´ ´UNIVERSITE DE LA MEDITERRANEE - U.F.R. SCIENCES
´ ´ECOLE DOCTORALE DE MATHEMATIQUES ET
INFORMATIQUE E.D. 184
`THESE
pr´esent´ee pour obtenir le grade de
´ ´ ´Docteur de l’Universite de la Mediterranee
Sp´ecialit´e : Informatique
par
Mariette SERAYET
Raisonnement `a partir d’informations
structur´ees et hi´erarchis´ees :
Application `a l’information arch´eologique
soutenue le 6 mai 2010 devant le jury compos´e de
Marie-Odile CORDIER Professeur a` l’Universit´e de Rennes 1 (Rapporteur)
Nadia CREIGNOU a` l’Universit´e de la M´editerran´ee (Examinatrice)
´Olivier CURE Maˆıtre de conf´erence `a l’Universit´e Paris-Est (Invit´e)
Pierre DRAP Charg´e de recherche CNRS, LSIS (Co-directeur)
Antoinette HESNARD Directrice de recherche CNRS, CCJ (Examinatrice)
Sylvain LAGRUE Maˆıtre de conf´erence `a l’Universit´e d’Artois (Invit´e)
J´erˆome LANG Directeur de recherche CNRS, LAMSADE (Rapporteur)
Odile PAPINI Professeur a` l’Universit´e de la M´editerran´ee (Directrice)Th`ese pr´epar´ee dans le laboratoire des Sciences de l’Information et des Syst`emes
LSIS - UMR CNRS 6168
au sein de l’universit´e de la M´editerran´ee et de l’universit´e Paul C´ezanne
et financ´ee par le projet europ´een VENUS n˚(IST-034924).A mes parents,Remerciements
En premier lieu, je souhaite remercier Marie-Odile Cordier et J´erˆome Lang pour
l’int´erˆet qu’ils ont port´e a` mon travail mais aussi pour les conseils qu’ils m’ont donn´e
pour l’am´elioration de mon manuscrit. Je remercie ´egalement Nadia Creignou et An-
toinetteHesnardpouravoiraccept´ed’ˆetremembresdujuryquiaexamin´emontravail.
JeremercieOdilePapinietPierreDrapd’avoirdirig´ecetteth`ese,dem’avoirencou-
rag´eeetdem’avoirfaitd´ecouvrirdenouveauxdomaines.Leurrigueuretleurscritiques
m’ont permis de mener `a bien ce travail.
Je tiens `a remercier ´egalement le projet europ´een VENUS dont le financement m’a
permis de r´ealiser cette th`ese. J’en profite a` ce titre pour remercier tous les partenaires
de ce projet. Je remercie Olivier Cur´e pour notre collaboration et sa pr´esence lors de
masoutenance.Jesouhaiteremercier´egalementmongrandfr`eredeth`ese,JulienS.qui
a su parfaitement jouer son rˆole. Quelques lignes ne suffiraient pas pour lui exprimer
toute ma reconnaissance.
Mes prochains remerciements vont `a Salem Benferhat, Sylvain Lagrue et Safa Yahi
duCRILdeLenspournotrecollaborationpendantcetteth`eseainsiquepourlapr´esence
de Sylvain pour ma soutenance.
Je tiens a` remercier ensuite les membres de mon ´equipe (INCA), je n’aurais pu
trouvermeilleurenvironnementdetravail.Jeremercietoutsp´ecialementPhilippepour
la confiance qu’il m’a accord´e lors des enseignements qu’il m’a confi´es pendant ces
ann´ees et Cyril T. qui a toujours ´et´e `a mon ´ecoute en tant que coll`egue et ami. Je
souhaiteremercierR´egisetC´edricP.pouravoirpartag´elebureaupendantcesderniers
moisetenparticulier,merci`aC´edricP.pourlecaf´edumatin.JeremercieEricetJulien
H. pour toutes les discussions enrichissantes que nous avons pu avoir. Travailler avec
vous tous fut un r´eel plaisir.
Lors de mon arriv´ee a` l’ESIL, j’ai ´et´e chaleureusement accueillie par l’´equipe I&M
(remerciement sp´ecial pour Bernard et sa femme) et plus particuli`erement par les
th´esards. Nous avons partag´e des bons moments lors de soir´ees ou de d´ejeuners pour
nousa´ererl’esprit.Lasolidarit´edontvousavezfaitpreuvem’abeaucouptouch´ee:merci
a`Guigui,Greg,Van,Alaa,Thomas,Ludo,Hung,Christophe,FlorianetKheiredine.Je
souhaiterais remercier sp´ecialement Adrien (mon coloc de bureau;-)) et Dimitri pour
tous les bons moments pass´es tous les trois. J’esp`ere garder votre amiti´e longtemps et
on se voit quand vous voulez pour un sandwich a` Montr´eal! Une autre personne m´erite
des remerciements sp´eciaux, V´eronique (surnomm´ee maman V´ero), elle a toujours su8 Remerciements
ˆetre a` mon ´ecoute et m’a consol´ee un nombre de fois impressionnant, elle est devenue
au fil de ces ann´ees une amie tr`es ch`ere. J’en profite´egalement pour remercier Nathalie
et Marie pour leur gentillesse et plus g´en´eralement tout le personnel de l’ESIL.
Mes plus grands remerciements vont a` mes parents. Ils m’ont toujours soutenue
et encourag´ee dans mes choix. Merci de m’avoir transmis cet esprit critique, cette
pers´ev´erance et plein d’autres choses. Un immense merci `a ma soeur, Maud, qui a
toujours su trouv´e les bons mots pour me remotiver. Tu vas enfin pouvoir dire que
ta soeur est docteur! J’en profite pour remercier Nico! Je remercie ´egalement mon
“petit” fr`ere, Cˆome et sa p´etillante Marine pour leur bonne humeur. Un grand merci
a` l’ensemble des autres membres de ma famille ainsi que mon parrain pour avoir ´et´e `a
mes cotˆ ´es.
L’aventure de la th`ese a ´et´e l’occasion de faire de belles rencontres. La plus belle
de ces rencontres reste celle de C´edric. Tu as r´eussi `a me soutenir pendant ces ann´ees
malgr´e les milliers de kilom`etres qui nous s´eparent. Je te remercie pour tout ce que
tu m’apportes. Une nouvelle aventure commence pour nous et je sais que gracˆ e a` ton
soutien, ce sera une autre belle r´eussite. J’en profite ´egalement pour remercier toute
ma belle famille, les week-ends ni¸cois ´etaient un bol d’air a` chaque fois, merci a` Jean-
Claude, Lyliane et Cynthia pour ces bons moments. Je n’oublie pas le clan des Nˆımois
pour m’avoir accueillie et divertie lors de week-ends sympathiques et inoubliables!
J’ai toujours pu compter sur mes ami(e)s qui ont su me soutenir chacun a` leur
mani`ere pendant ces ann´ees de th`ese. Corinne qui a sans cesse pris de mes nouvelles
alors que je croulais sous le travail. Je remercie ´egalement Manu, Romain, Schnob’ et
C´ecilepourtouteslesfoisou`ilsm’ont´ecout´eeetsoutenueparMSNouparmail!Merci`a
R´emi pour les bons restos que l’on a d´ecouvert sur Marseille, c’´etait un plaisir a` chaque
fois. Etant pass´e par l`a, tu m’as toujours ´ecout´ee et conseill´ee dans les moments de
doute. Un grand merci `a Claire et Elodie qui malgr´e la distance ont toujours su trouver
les mots pour m’encourager jusqu’`a la fin. Enfin, je voudrais remercier la Shrink family
sur qui j’ai toujours pu compter : Raf, Flo, Jean-Luc, Emilie, Fiona et Jack merci pour
les soir´ees, les r´eveillons, les concerts, les pique-niques, les anniversaires, ... et pour
tous les bons moments a` venir!
La derni`ere personne que je souhaite remercier est ma marraine. Elle a ´et´e pa-
radoxalement la plus pr´esente dans mes pens´ees lorsque la solitude et les doutes se
faisaient trop lourds, marraine, je ne t’oublie pas et j’esp`ere que de l`a-haut, tu es fi`ere
de moi.Table des mati`eres
Introduction 15
I Pr´eliminaires 21
1 Outils 23
1.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.2 Logique propositionnelle . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.2.1 Le langage de la logique propositionnelle . . . . . . . . . . . . . . 24
1.2.2 Aspect axiomatique de la logique propositionnelle . . . . . . . . 24
1.2.3 Aspect s´emantique de la logique propositionnelle . . . . . . . . . 26
1.3 Logique des pr´edicats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.3.1 Le langage de la logique des pr´edicats . . . . . . . . . . . . . . . 28
1.3.2 Aspect axiomatique de la logique des pr´edicats . . . . . . . . . . 30
1.3.3 Aspect s´emantique de la logique des pr´ . . . . . . . . . . . 31
1.4 Programmation logique avec s´emantique de mod`eles stables . . . . . . . 34
1.4.1 Programme logique normal . . . . . . . . . . . . . . . . . . . . . 34
1.4.2 basique . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.4.3 avec s´emantique de mod`eles stables . . . . . . . . . . 35
1.4.4 Les solveurs ASP . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
II Etat de l’art 37
2 Restauration de la coh´erence 39
2.1 Pr´eliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.1.1 Ordres et pr´eordres. . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.1.2 Bases de croyances . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.2 Sous-bases coh´erentes pr´ef´er´ees . . . . . . . . . . . . . . . . . . . . . . . 41
2.2.1 Base de croyances non ordonn´ees . . . . . . . . . . . . . . . . . . 42
2.2.2 Base de croyances totalement pr´eordonn´ees . . . . . . . . . . . . 42
2.2.3 Base de croyances partiellement pr´eordonn´ees . . . . . . . . . . . 44
2.3 Minimisation de l’incoh´erence . . . . . . . . . . . . . . . . . . . . . . . . 4610 Table des mati`eres
2.3.1 Restauration de la coh´erence et diagnostic . . . . . . . . . . . . . 46
2.3.2 de la coh´ et sous-formules minimales incon-
sistantes (MUS) . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.3.3 Traitement local de l’incoh´erence . . . . . . . . . . . . . . . . . . 49
2.4 Affaiblissement par oubli de variables. . . . . . . . . . . . . . . . . . . . 50
3 Inf´erence en pr´esence d’incoh´erence 53
3.1 Inf´erence pour des bases de croyances non ordonn´ees . . . . . . . . . . . 54
3.1.1 Les principes d’inf´erence . . . . . . . . . . . . . . . . . . . . . . . 55
3.2 Inf´erence pour des bases de croyances totalement pr´eordonn´ees . . . . . 56
3.2.1 Les principes d’inf´erence . . . . . . . . . . . . . . . . . . . . . . . 56
3.2.2 Les relations d’inf´ non-monotone . . . . . . . . . . . . . . 58
3.3 Inf´erence pour des bases de croyances partiellement pr´eordonn´ees . . . . 60
3.3.1 Extension bas´ee sur les compatibles . . . . . . . . . . . . . . . . 60
3.3.2 directe des inf´erences . . . . . . . . . . . . . . . . . . . 61
4 R´evision de croyances 65
4.1 La r´evision selon AGM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.2 Les postulats KM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.3 Quelques approches de r´evision . . . . . . . . . . . . . . . . . . . . . . . 68
4.3.1 Approches s´emantiques . . . . . . . . . . . . . . . . . . . . . . . 68
4.3.2ches syntaxiques . . . . . . . . . . . . . . . . . . . . . . . . 69
4.4 R´evision it´er´ee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.4.1 Les postulats de Darwiche et Pearl . . . . . . . . . . . . . . . . . 74
4.4.2 Quelques op´erateurs . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.5 R´evision d’´etats ´epist´emiques repr´esent´es par des pr´eordres partiels . . . 78
4.5.1 Les postulats KM r´evis´es . . . . . . . . . . . . . . . . . . . . . . 78
4.5.2 Caract´erisationdespostulatsdeDarwicheetPearlpourdespr´eordres
partiels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.5.3 Quelques op´erateurs . . . . . . . . . . . . . . . . . . . . . . . . . 80
III Raisonnement`apartird’informationspartiellementpr´eordonn´ees
85
5 Restauration de la coh´erence par R-ensembles 87
5.1 Comparateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.1.1 Comparateur faible . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.1.2 lexicographique . . . . . . . . . . . . . . . . . . . . 91
5.2 Approche syntaxique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.3che s´emantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.4 Equivalence syntaxique/s´emantique . . . . . . . . . . . . . . . . . . . . . 103
5.5alence R-ensembles/MCONS . . . . . . . . . . . . . . . . . . . . . 104

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.

Diffusez cette publication

Vous aimerez aussi