Théorie de Dempster-Shafer
La thĂ©orie de Dempster-Shafer est une thĂ©orie mathĂ©matique utilisant les fonctions de croyance et le raisonnement plausible. Le but de cette thĂ©orie est de permettre de raisonner dans une situation incertaine. Cette thĂ©orie a Ă©tĂ© dĂ©veloppĂ©e par Arthur P. Dempster et Glenn Shafer. Elle est aussi appelĂ©e thĂ©orie des croyances ou thĂ©orie de lâĂ©vidence.
Formalisme mathématique
Soit un univers, câest-Ă -dire un ensemble contenant tous les Ă©lĂ©ments auxquels on sâintĂ©resse. Lâensemble de ses parties, Ăchec de lâanalyse (SVG (MathML peut ĂȘtre activĂ© via une extension du navigateur)âŻ: rĂ©ponse non valide(«âŻMath extension cannot connect to Restbase.âŻÂ») du serveur «âŻhttp://localhost:6011/fr.wikipedia.org/v1/âŻÂ»âŻ:): {\mathcal {P}}(X)\,\! , est lâensemble de tous les sous-ensembles de , y compris lâensemble vide . Par exemple, si:
alors
Les Ă©lĂ©ments de lâensemble des parties de peuvent ĂȘtre interprĂ©tĂ©s comme des propositions, un Ă©lĂ©ment reprĂ©sentant les Ă©tats quâil contient. Par exemple, on peut interprĂ©ter lâĂ©lĂ©ment comme « la proposition a est vĂ©rifiĂ©e » ou « on est dans lâĂ©tat a », ou encore comme « on est soit dans lâĂ©tat a, soit dans lâĂ©tat b ».
Notion de masse
Les masses sont assignées par une fonction appelée Basic Belief Assignment (BBA) ou mass function (MF) formellement definie comme suit :
La fonction de BBA respecte les propriétés suivantes:
- la masse de lâensemble vide est 0 :
- la somme des masses des autres sous-ensembles vaut 1 :
La masse d'un Ă©lĂ©ment donnĂ© de lâensemble des parties exprime la proportion de toutes les preuves disponibles affirmant que l'Ă©tat actuel est et pas un autre Ă©tat ou un sous-Ă©tat de . La valeur de concerne donc seulement lâĂ©tat et nâapporte aucun crĂ©dit aux sous-ensembles de , chacun dâeux ayant, par dĂ©finition, sa propre masse.
Aujourd'hui, il n'existe pas de méthode rigoureusement définie pour attribuer des masses aux éléments. Cette affectation se fait donc par heuristique, aidée par des fonctions BBA connues.
Combinaison de preuves et de masses
Le problĂšme qui se pose maintenant est de savoir comment combiner deux ensembles indĂ©pendants et leurs masses. La rĂšgle de combinaison originale, connue en tant que rĂšgle de combinaison de Dempster, est une gĂ©nĂ©ralisation du thĂ©orĂšme de Bayes. Ce thĂ©orĂšme met clairement en valeur lâaccord entre des sources multiples et ignore les conflits grĂące Ă un facteur de normalisation. Lâutilisation de ce thĂ©orĂšme pose ainsi problĂšme lorsque des conflits significatifs ont lieu entre diffĂ©rentes sources dâinformation.
Ici, la combinaison ou masse jointe est calculée à partir des deux masses et de la maniÚre suivante :
oĂč
est une mesure du niveau de conflit entre les deux masses. Le facteur de normalisation permet dâignorer ces conflits et dâattribuer toute masse impliquĂ©e dans le conflit Ă lâensemble nul. De ce fait, cette opĂ©ration donne des rĂ©sultats contre-intuitifs face Ă des conflits significatifs, dans certains contextes.
La rÚgle de combinaison de Dempster est prévue pour les cas de monde clos. Une autre rÚgle de combinaison, la rÚgle de combinaison conjonctive, propose une alternative pour les mondes ouverts:
Dans ce cas, lorsqu'il y a une fusion de valeurs conflictuel, ma valeur de n'est plus Ă©gale Ă zĂ©ro. Cela peut ĂȘtre interprĂ©tĂ© de plusieurs façons.
- Une mesure est aberrante.
- La modélisation des fonctions de croyance est imparfaite.
Que ce soit pour la rÚgle de combinaison conjonctive ou la rÚgle de combinaison de Dempster, elles ont les propriétés suivante:
- Commutativité:
- Associativité:
- ĂlĂ©ment neutre :
Dans ces deux cas, les sources doivent ĂȘtre distinctes et fiables.
Une autre rĂšgle de combinaison, la rĂšgle disjonctive, permet la fusion de sources oĂč au moins une des sources est fiable. Elle est calculĂ©e comme suit:
Raisonnement par incertitude et prise de décision
Nous pouvons différencier deux niveaux de raisonnement: le niveau crédal et le niveau pignistique. Le niveau crédal se base sur le raisonnement par incertitude alors que le niveau pignistique se base sur des mesures de probabilité sur les masses. Ces raisonnement permettent à partir d'un ensemble afin de classer les éléments de et donc de prendre une décision sur l'élément de à choisir.
Niveau crédal
Ă partir de la valeur de la masse dâun Ă©tat, on peut dĂ©finir un intervalle de probabilitĂ©. Cet intervalle contient la valeur prĂ©cise de la probabilitĂ© de lâĂ©tat, et est bornĂ© par deux mesures appelĂ©es croyance et plausibilitĂ©:
La croyance d'un ensemble est définie comme la somme des masses de tous ses sous-ensembles (pas nécessairement propres) :
La plausibilité est définie comme la somme des masses de tous les ensembles qui intersectent :
Ces deux mesures sont liées :
De ce fait, la connaissance dâune seule de ces valeurs (masse, croyance ou plausibilitĂ©) suffit Ă dĂ©duire les deux autres.
Niveau pignistique
Comme pour le niveau crédal, nous pouvons utiliser la valeur de masse d'un état mais cette fois ci dans le but d'effectuer une mesure de probabilité. Cette mesure est effectuée comme suit[1]:
Ici, les valeurs et correspondent à leur cardinalité (c'est-à -dire au nombre d'éléments).
Notes et références
- Philippe SMETS, « Constructing the Pignistic Probability Function in a Context of Uncertainty », dans Uncertainty in Artificial Intelligence, Elsevier, (lire en ligne), p. 29â39