Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

Universitéd’Artois FacultédessciencesJeanPerrin
Fusiond’informationsincertaines
sanscommensurabilitédeséchellesderéférence
THÈSE
pourl’obtentiondugradede
Docteurdel’Universitéd’Artois
(spécialitéinformatique)
par
Julien ROSSIT
devantlejurycomposéde
Odile PAPINI ProfesseurdesUniversités,UniversitédelaMéditerranée (rapporteur)
Marie-Anne WILLIAMS ResearchProfessor,UniversityofTechnology,Sydney,Australia
Salem BENFERHAT ProfesseurdesUniversités,Universitéd’Artois (directeurdethèse)
Richard BOOTH Lecturer,MahasarakhamUniversity,Thailand (examinateur)
Sébastien KONIECZNY ChargédeRechercheCNRS,CRIL (e
Sylvain LAGRUE MaîtredeConférences,Universitéd’Artois (co-directeurdethèse)
Pascal NICOLAS ProfesseurdesUniversités,Universitéd’Angers (examinateur)
CentredeRechercheenInformatiquedeLens(CRIL) Juillet2009Tabledesmatières
Introduction 1
Delanécessitédelafusiondecroyances . . . . . . . . . . . . . . . . . . . . . . . . . 2
Delacommensurabilitédessources . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Objectifsdelathèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Plandumémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1 Représentationetévolutiondescroyancesindividuellesd’unagent 11
1.1 Introductionàlalogiquepropositionnelle . . . . . . . . . . . . . . . . . . . . . 12
1.2 Logiquespondérées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3 Approchesqualitativesdelagestiondesincohérences . . . . . . . . . . . . . . . 21
1.4 Révisiondescroyances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.5 Synthèseduchapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2 Fusionetreprésentationdescroyancescollectives 39
2.1 Fusiondebasesdecroyancespropositionnelles . . . . . . . . . . . . . . . . . . 40
2.2 Fusionpossibiliste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.3 Représentationparlespolynômesetfusion . . . . . . . . . . . . . . . . . . . . 49
2.4 Synthèseduchapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3 Fusiondecroyancespondéréesetproblèmesd’incommensurabilité 51
3.1 Fusiondebasesdecroyancespondérées . . . . . . . . . . . . . . . . . . . . . . 52
3.2 Surleproblèmedelacommensurabilité . . . . . . . . . . . . . . . . . . . . . . 58
3.3 Commensurabilitéetchoixsocial . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.4 Échellescompatibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.5 Synthèseduchapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
iii TABLEDESMATIÈRES
4 Fusionincommensurableetcadreégalitaire 67
4.1 Fusionbaséesurlemaximum . . . . . . . . . . . . . . . . . . 68
4.2 Propriétéslogiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.3 Synthèseduchapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5 Fusionincommensurableetcadreutilitaire 99
5.1 Fusionbaséesurlasomme . . . . . . . . . . . . . . . . . . . 100
5.2 Propriétéslogiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.3 Synthèseduchapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6 Fonctionsdesélectiond’échellescompatibles 119
6.1 Sélectiond’échellescompatiblesparticulières . . . . . . . . . . . . . . . . . . . 120
6.2 Classesdeséchellesaffinesetlinéaires . . . . . . . . . . . . . . . . . . . . . . . 122
6.3 Classedestranslatives . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
6.4 Classedeséchellesbornées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.5 Choisiruneéchellecompatibleunique . . . . . . . . . . . . . . . . . . . . . . . 153
6.6 Synthèseduchapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
7 Uneétudecomparative 159
7.1 Relationentreapprocheégalitaireetutilitairedanslecadreincommensurable . . 160
7.2 Surlaprudencedelasélectiond’échellesparticulières . . . . . . . . . . . . . . 164
7.3 Récapitulatifdespropriétéslogiques . . . . . . . . . . . . . . . . . . . . . . . . 169
7.4 Synthèseduchapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
Conclusion 173Résumé
Le problème de fusion d’informations survient dès qu’il faut prendre en compte des bases
de données distribuées, des systèmes multi-agents ou des informations distribuées en général. La
plupart des approches de fusion proposées dans la littérature reposent sur des opérateurs d’agré-
gation : ceux-ci combinent les degrés de cohérence des différentes interprétations vis-à-vis des
sources à fusionner, eux-même fortement dépendants des poids que ces sources accordent à leurs
proprescroyances.Maislorsquelessourcesnepartagentpasunesignificationcommunedespoids
qu’ellesutilisent,quelsenscelaa-t-ildecompareroud’agrégercesmêmespoids?
Ainsi, nous étudions dans cette thèse différentes approches de fusion de croyances en l’ab-
sence de commensurabilité des échelles utilisées. Nous proposons tout d’abord une première mé-
thode, reposant sur la notion d’échelle compatible, que nous appliquons à des opérateurs basés
sur la somme et sur le maximum. Les opérateurs résultants peuvent être caractérisés au moyen
d’unensembleinfinid’échellescompatibles,maiségalementaumoyenderelationsdetypePareto
sur l’ensemble des mondes possibles. Puis nous étudions plus particulièrement certaines familles
d’échelles compatibles afin de caractériser des opérateurs moins prudents et prenant en compte
l’intensitédespoids.Nousfournissonsuneanalysecomplètedelaproductiondesinférencesetde
la rationalité des opérateurs de fusion définis. En particulier, nous proposons la notion de consen-
sus, souhaitable en l’absence de l’hypothèse de commensurabilité et vérifiée par la plupart de nos
opérateurs.
Abstract
The problem of merging multiple-source information is crucial for many applications, in par-
ticularwhenonerequirestotakeintoaccountseveralpotentiallyconflictingpiecesofinformation,
such as distributed databases frameworks, multi-agent systems, or distributed information in ge-
neral. The relevant pieces of information are provided by different sources and all existing pieces
of information have to be confronted to obtain a global and coherent point of view. This problem
is well-known as the data fusion problem. Most of existing merging methods are based on the
following assumption : ranks associated with beliefs are commensurable from one source to ano-
ther. This commensurability assumption can be too strong for several applications : comparing or
combiningranksdoesnotmakesenseifsourcesdonotsharethesamemeaningofscales.
This thesis proposes different solutions to the problem of incommensurability for ranked be-
liefs merging. Our first main contribution consists of proposing a natural way to restore commen-
surabilityrelyingonthenotionofcompatiblescales.Thesecondonedirectlydefinesapartialpre-
order between interpretations in a way similar to the one based on the Pareto criterion. Moreover,
this thesis introduces several inference relations based on some selection functions of compatible
scales. We analyze the impact of these selection functions on the satisfaction of rational postu-
lates, and on the prudence of merging operators. In particular we introduce a stronger version of
the fairness postulate, called the consensus postulate. We show that most of our defined merging
operatorsconstituteconsensualapproaches.Introduction
Un enjeu actuel important, activement étudié dans le domaine de l’intelligence artificielle, ré-
sidesanscontestedanslareprésentationetlagestiond’informationsincertainesquepeutrecueillir
et manipuler un agent autonome sur son environnement. Les solutions mises en oeuvre doivent
prendre en compte et tirer parti de la nature complexe et évolutive du monde qui l’entoure. Cet
agent ne dispose alors que de croyances, elles aussi incertaines, sur l’état de son environnement.
Ces croyances doivent lui permettre de prendre les meilleures décisions possibles à chaque ins-
tant. La représentation qu’il emploie doit donc lui permettre de raisonner à partir d’informations
incertaines, dans le but d’en dériver les conclusions lui permettant d’agir de façon appropriée.
Cependant, de part la nature incertaine des informations dont il dispose, il arrive parfois qu’une
nouvelle observation vienne contredire les croyances actuelles d’un agent. La représentation des
croyances adoptée par cet agent doit ainsi permettre la prise en compte de l’évolution et de la
dynamique de ces croyances : comment intégrer ces nouvelles informations, même si elles sont
contradictoiresavecsareprésentationactuelledumonde,sanslaissercetagentdansunétatd’igno-
rancetotale?
Différentsformalismesontainsiétéproposésdanslalittératureafindereprésenterlescroyances
que possède un agent sur le monde. Dans ce sens, le terme croyance désigne une information
incertaine qu’il est possible d’obtenir d’une source. Parmi ces différents formalismes, certains
permettent de quantifier la fiabilité, ou l’incertitude, relative des informations disponibles, en
leur associant par exemple un degré de possibilité [DLP94], un ordinal [Spo88] ou encore un
polynôme [Pap01]. Certaines approches ont également été proposées afin de permettre la révi-
sion[AGM85],lamiseàjour[KM92],lerenforcement[KPP08b]ouencorelaconfluence[KPP08a]
des croyances d’un agent. De plus, lorsque l’agent s’informe sur son environnement par l’inter-
médiairedeplusieurssourcesdistinctes,d’autresapprochespermettentlafusiondesinformations,
potentiellementcontradictoires,obtenuesdecesdifférentessources[Lin96,Rev97,KPP02].
12 INTRODUCTION
Delanécessitédelafusiondecroyances
La fusion d’informations en provenance de sources multiples est un problème important dans
+le cadre de la représentation des croyances [Lin96, Rev97, BHA 01, KPP02]. En effet, pour de
nombreuses applications de la vie courante, dont l’exemple le plus symptomatique est le web, la
tendance est à la distribution de l’information. Ce problème est ainsi étudié dans différents do-
maines tels que les systèmes d’information coopératifs, les bases de données distribuées, les sys-
tèmes multi-agents, etc. Dans de nombreuses situations, les différentes informations concernant
un problème donné sont fournies par différentes sources bien distinctes. Prises individuellement,
ces informations sont bien souvent incomplètes, et l’intégralité de ces points de vue partiels doit
alorsêtrerassemblées,oufusionnées,afind’obtenirunpointdevuecohérentetglobalsurcepro-
blème. Lorsque ces informations sont complémentaires, il est possible de simplement prendre en
compte leur union. Mais que faire lorsque les différentes sources considérées fournissent des ren-
seignementscontradictoires?Leprincipedelafusiond’informationsestdetirerprofitd’unmaxi-
mum d’informations complémentaires et non contradictoires disponibles, soit en d’autres termes
de déterminer une information globale, la plus proche possible des informations fournies indi-
viduellement. Prenons l’exemple de la prise en compte de différents témoignages, dans le cadre
d’une enquête policière. Dans ce genre de situation, différents témoins d’une scène fournissent
des informations incomplètes, plus ou moins certaines, en fonction de ce qu’ils peuvent avoir vu
ou entendu. Certaines de ces informations peuvent alors être totalement éronnées, et la réunion
de ces informations mène alors à une situation contradictoire. Cet exemple illustre clairement la
subjectivité des informations fournies par les sources prises en compte : en effet, même si chaque
témoin ne rapporte que les faits qui lui semblent avérés, ces mêmes faits dépendent entièrement
de ses capacités personnelles à voir ou entendre distinctement, et de sa localisation vis-à-vis de la
scène.Commentfairealors,pourobtenirunevisiond’ensembledelascène,àlafoiscohérenteet
lapluscomplètepossible?
Ce problème de fusion a largement été étudié d’un point de vue axiomatique dans la litté-
rature [Rev93, LS95, LM99]. Dans le cadre de notre étude, nous nous focalisons sur l’axioma-
tisation proposée dans [KPP98, KPP02] par Konieczny et Pino Pérez, présentant la particularité
d’être étroitement liée à celle proposée, dans le cadre de la révision des croyances [AGM85], par
Alchourrón,Gärdenfors,etMakinson.Intuitivement,cetensembledepostulatsderationalitétente
dedécrirelecomportementidéald’unopérateurdefusion.D’unpointdevuesémantique,lethéo-
rème de représentation qui lui est alors associé permet de présenter le problème de fusion comme
la recherche des interprétations minimales selon un ordre induit par les sources sur l’ensemble
des mondes possibles. D’autres postulats de rationalité complémentaires ont été proposés afin de
caractériserlesdifférentesattitudesqu’ilestpossibled’adopterpourrésoudrelesconflitsentreles
sources.Parmicelles-ci,ilestpossiblededistinguerlesdeuxtypesd’approchesuivants:
– l’approche égalitaire, selon laquelle chaque point de vue est considéré comme d’égale im-INTRODUCTION 3
portance, et aucun d’eux, même s’il est minoritaire, ne saurait être écarté. Ce type d’ap-
prochetentedeprendreencomptechaquepointdevuedisponibleetd’établiruncompromis
entrelesinformationsincomplètesexpriméesparlessources.Ainsi,lesopérateursadoptant
ce type d’attitude essaient de minimiser l’insatisfaction individuelle de chaque source, et
vérifient le postulat d’indépendance de la majorité : intuitivement, ce postulat assure le
fait que le résultat de la fusion n’est pas sensible à la répétition de l’information. Repre-
nonsl’exempledestémoignages:pourcetyped’approche,chaquepointdevueexistantest
considérécommed’égaleimportancevis-à-visdesautres,ettouteinformationapportéepar
les témoins est prise en compte, sans toutefois tenir compte de leurs redondances. Il arrive,
en effet, qu’une information minoritaire soit totalement fondée, dans des situations où, par
exemple, le témoin qui la fourni était le seul en mesure de distinguer clairement les faits.
Cetteinformationnedoitpasêtreécartée;
– l’approcheutilitaire,selonlaquellelapriseencomptedel’ensembledesinformationsdispo-
niblesdansleurglobalitéestprioritaireaudelàdelapriseencomptedesdifférentspointsde
vueprisindividuellement.Cetyped’approchepermetdediscriminerlessituationsd’incohé-
renceportantsurcertainesdonnéesenexploitantlaredondancedesinformationsdisponibles
sur le monde. De cette façon, les opérateurs adoptant ce type d’attitude tentent de minimi-
ser l’insatisfaction globale du groupe et satisfont le postulat de majorité, également connu
sous le terme d’archimédianité [Pat02] : intuitivement, cette propriété décrit le fait que, si
une information est suffisamment répétée parmi les bases de croyances considérées, alors
cettedoitêtredérivéedurésultatdelafusion.Considéronsànouveaul’exemple
des témoignages. Lorsque différents témoins fournissent des informations contradictoires,
comment les départager, et obtenir une conclusion dans cette situation d’ignorance totale?
Lesapprochesmajoritairesconsidèrentquelespointsdevuelesplusrépandussontlesplus
plausibles, puisque plusieurs témoins sont en accord sur l’observation d’un même fait. Ce
type d’approche requiert cependant l’indépendance des sources : concernant l’exemple des
témoignages, les différents témoins ne doivent pas s’être échangé d’informations avant de
relaterlesfaitsindividuellement.
De nombreuses approches pratiques ont été proposées pour résoudre le problème de fusion.
Ces approches dépendent fortement du formalisme employé pour la représentation des informa-
tions. Ainsi, certains opérateurs ont été proposés, dans la littérature, afin de fusionner des bases
decroyancespropositionnelles[Lin96,Rev97,KPP02]:cesopérateursreposentsurunenotionde
distance de l’information générale retenue, vis-à-vis des informations individuellement fournies
par chaque source. Il existe également d’autres opérateurs de fusion, adaptés aux cas où l’incer-
titude associée aux croyances est codée par le biais de degrés de possibilité [BDKP00b] ou de
polynômes [DPS06]. Ce type d’opérateur repose sur l’agrégation des degrés, que chaque base de
croyancesconsidéréepermetd’induiresurlesdifférentsmondespossibles.4 INTRODUCTION
Delacommensurabilitédessources
Dans le cadre de notre étude, les informations incertaines sont représentées au moyen de
croyances pondérées. Dans ce cadre, chaque source associe un entier aux informations qu’elle
fournit, dans le but d’en quantifier la fiabilité. Différentes approches ont été proposées, dans la
littérature, afin de fusionner ce type de bases de croyances. Celles-ci reposent sur l’intuition sui-
vante : chaque base de croyances pondérées permet d’associer un poids aux différentes interpré-
tations possibles du monde; les interprétations sont alors préférées respectivement au résultat de
l’agrégation des poids qui leur sont ainsi associés. Ces différentes approches reposent cependant
sur certaines hypothèses implicites. En particulier, lorsque les sources associent des poids aux in-
formations,danslebutd’enquantifierl’incertitude,celles-cidoiventalorspartagerlasignification
qu’ellesaccordentauxéchellesdepoidsqu’ellesutilisent.Autrement,quelsenscelaa-t-ild’agré-
gercesmêmespoidsunefoisceux-ciassociésauxinterprétations?
Ce problème est étroitement lié à ceux de la mesurabilité et de l’intercomparabilité des utili-
tés, connus dans le domaine de la théorie du choix social. Le but de cette dernière est d’obtenir
lespréférencesd’ungroupeàpartirdespréférencesindividuellesdesindividusissusdecegroupe.
Certaines approches proposées pour ce problème permettent alors aux individus d’associer des
utilités aux différentes alternatives disponibles : ces utilités sont ensuite agrégées afin d’obtenir
les alternatives préférées du groupe. Différents problèmes sous-jacents à ce type d’approche ont
été soulevés dans la littérature [Arr63, Sen82]. Le premier de ces problèmes est celui de la me-
surabilité des utilités de chaque individu : pourquoi un individu choisit-il une échelle d’utilité en
particulier et non une autre? Tient-il compte de certaines notions d’homogénéité, de linéarité ou
encore d’intensité reliant les différentes utilités qu’il exprime? De façon similaire, pour le pro-
blème de la fusion de bases de croyances pondérées, rien ne nous renseigne sur la provenance, ni
même sur la signification, des poids associés aux informations obtenues d’une source. Le second
problème identifié est celui de l’intercomparabilité : même si la mesurabilité des utilités est ad-
mise,rienn’indiquequecesutilitéssoientcomparablesd’unesourceàl’autre.End’autrestermes,
siunindividuchoisituneéchelled’utilitéparticulièrepourquantifiersespréférencessurlesalter-
natives disponibles, rien n’indique que les autres individus aient choisi la même. Ce problème est
intimementliéàceluiquenousidentifionssousletermedecommensurabilitédessourcesdansle
cadredelafusiondebasesdecroyancespondérées.
Il existe de nombreux exemples du problème de commensurabilité dans la pratique. Prenons
l’exempled’uneenquêtedesatisfactionauprèsdeclients:lorsquel’ondemandeàdifférentesper-
sonnes d’évaluer, sous forme d’une note, la qualité de différents produits, ou encore de certains
services,peut-ondirequedeuxpersonnesattribuantlamêmenoteàdeuxproduitsdistinctslesap-
précientdemanièreégale?Delamêmefaçon,unexempled’incommensurabilité,tiréde[Kel06],
concerne la mesure de l’activité d’un cerveau. En effet, il existe deux mesures possible pour cette
dernière : la température du cerveau, et le quotient intellectuel de l’individu. Bien que ces deux