Fusion d'informations incertaines sans commensurabilité des échelles de référence, Incommensurable ranked belief bases merging

Julien Rossit

Description

Sous la direction de Salem Benferhat
Thèse soutenue le 10 juillet 2009: Artois
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 propres croyances. Mais lorsque les sources ne partagent pas une signification commune des poids qu'elles utilisent, quel sens cela a-t-il de comparer ou d'agréger ces mêmes poids ? Ainsi, nous étudions dans cette thèse différentes approches de fusion de croyances en l'absence 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’un ensemble infini d’échelles compatibles, mais également au moyen de relations de type Pareto 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é des poids. Nous fournissons une analyse complète de la production des inférences et de la rationalité des opérateurs de fusion définis. En particulier, nous proposons la notion de consensus, souhaitable en l'absence de l'hypothèse de commensurabilité et vérifiée par la plupart de nos opérateurs.
-Intelligence artificielle
-Fusion de croyances
-Incommensurabilité
-Majorité
-Consensus
The problem of merging multiple-source information is crucial for many applications, in particular when one requires to take into account several potentially conflicting pieces of information, such as distributed databases frameworks, multi-agent systems, or distributed information in general. 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 another. This commensurability assumption can be too strong for several applications: comparing or combining ranks does not make sense if sources do not share the same meaning of scales. This thesis proposes different solutions to the problem of incommensurability for ranked beliefs merging. Our first main contribution consists of proposing a natural way to restore commensurability relying on the notion of compatible scales. The second one directly defines a partial pre-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 postulates, 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 operators constitute consensual approaches.
Source: http://www.theses.fr/2009ARTO0405/document

Sujets

• Intelligence artificielle
• Incommensurabilité
• Majorité
• Consensus

Informations

• Publié par: Thesee
• Nombre de lectures: 28
• Langue: Français

Extrait

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̵