Théorie de Dempster-Shafer

Page d’aide sur l’homonymie

Pour les articles homonymes, voir Dempster et Shafer.

Photo de Dempster

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 X {\displaystyle X\,\!} un univers, c’est-à-dire un ensemble contenant tous les éléments auxquels on s’intéresse. L’ensemble de ses parties, P ( X ) {\displaystyle {\mathcal {P}}(X)\,\!} , est l’ensemble de tous les sous-ensembles de X {\displaystyle X\,\!} , y compris l’ensemble vide {\displaystyle \varnothing } . Par exemple, si:

X = { a , b } {\displaystyle X=\left\{a,b\right\}\,\!}

alors

P ( X ) = { , { a } , { b } , X } . {\displaystyle {\mathcal {P}}(X)=\left\{\varnothing ,\left\{a\right\},\left\{b\right\},X\right\}.\,\!}

Les éléments de l’ensemble des parties de X {\displaystyle X\,\!} 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 { a } {\displaystyle \left\{a\right\}} comme « la proposition a est vérifiée » ou « on est dans l’état a », ou encore { a , b } {\displaystyle \left\{a,b\right\}} 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 :

m : P ( X ) [ 0 , 1 ] . {\displaystyle m:{\mathcal {P}}(X)\to [0,1].\,\!}

La fonction de BBA respecte les propriétés suivantes:

  • la masse de l’ensemble vide est 0 :
m ( ) = 0. {\displaystyle m(\varnothing )=0.\,\!}
  • la somme des masses des autres sous-ensembles vaut 1 :
A P ( X ) m ( A ) = 1. {\displaystyle \sum _{A\in {\mathcal {P}}(X)}m(A)=1.\,\!}

La masse m ( A ) {\displaystyle m(A)\,\!} d'un élément donné A {\displaystyle A\,\!} de l’ensemble des parties exprime la proportion de toutes les preuves disponibles affirmant que l'état actuel est A {\displaystyle A\,\!} et pas un autre état ou un sous-état de A {\displaystyle A\,\!} . La valeur de m ( A ) {\displaystyle m(A)\,\!} concerne donc seulement l’état A {\displaystyle A\,\!} et n’apporte aucun crédit aux sous-ensembles de A {\displaystyle A\,\!} , 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 m 1 {\displaystyle m_{1}\,\!} et m 2 {\displaystyle m_{2}\,\!} de la manière suivante :

m 1 , 2 ( ) = 0 {\displaystyle m_{1,2}(\varnothing )=0\,\!}
m 1 , 2 ( A ) = m 1 ( A ) m 2 ( A ) = 1 1 K B C = A m 1 ( B ) m 2 ( C ) {\displaystyle m_{1,2}(A)=m_{1}(A)\oplus m_{2}(A)={\frac {1}{1-K}}\sum _{B\cap C=A\neq \varnothing }m_{1}(B)m_{2}(C)}

K = B C = m 1 ( B ) m 2 ( C ) . {\displaystyle K=\sum _{B\cap C=\varnothing }m_{1}(B)m_{2}(C).\,\!}

K {\displaystyle K\,\!} est une mesure du niveau de conflit entre les deux masses. Le facteur de normalisation 1 K {\displaystyle 1-K\,\!} 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:


m 1 , 2 ( A ) = B C = A m 1 ( B ) m 2 ( C ) {\displaystyle m_{1,2}(A)=\sum _{B\cap C=A}m_{1}(B)m_{2}(C)}

Dans ce cas, lorsqu'il y a une fusion de valeurs conflictuel, ma valeur de m ( ) {\displaystyle m(\varnothing )} 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é: m 1 m 2 = m 2 m 1 {\displaystyle m_{1}\oplus m_{2}=m_{2}\oplus m_{1}}
  • Associativité: m 1 ( m 2 m 3 ) = ( m 1 m 2 ) m 3 {\displaystyle m_{1}\oplus (m_{2}\oplus m_{3})=(m_{1}\oplus m_{2})\oplus m_{3}}
  • Élément neutre m X {\displaystyle m_{X}} : m m X = m {\displaystyle m\oplus m_{X}=m}

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:

m 1 , 2 ( A ) = B C = A m 1 ( B ) m 2 ( C ) {\displaystyle m_{1,2}(A)=\sum _{B\cup C=A}m_{1}(B)m_{2}(C)}

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 P ( X ) {\displaystyle {\mathcal {P}}(X)} afin de classer les éléments de X {\displaystyle X} et donc de prendre une décision sur l'élément de X {\displaystyle X} à 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é:

bel ( A ) P ( A ) pl ( A ) . {\displaystyle \operatorname {bel} (A)\leq P(A)\leq \operatorname {pl} (A).\,\!}


La croyance bel ( A ) {\displaystyle \operatorname {bel} (A)\,\!} d'un ensemble A {\displaystyle A\,\!} est définie comme la somme des masses de tous ses sous-ensembles (pas nécessairement propres) :

bel ( A ) = B B A m ( B ) . {\displaystyle \operatorname {bel} (A)=\sum _{B\mid B\subseteq A}m(B).}

La plausibilité pl ( A ) {\displaystyle \operatorname {pl} (A)\,\!} est définie comme la somme des masses de tous les ensembles B {\displaystyle B\,\!} qui intersectent A {\displaystyle A\,\!} :

pl ( A ) = B B A m ( B ) {\displaystyle \operatorname {pl} (A)=\sum _{B\mid B\cap A\neq \varnothing }m(B)}


Ces deux mesures sont liées : pl ( A ) = 1 bel ( A ¯ ) . {\displaystyle \operatorname {pl} (A)=1-\operatorname {bel} ({\overline {A}}).\,\!}

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]:

P m ( A ) = B X m ( B ) 1 m ( ) | A B | | B | ,   A X {\displaystyle P_{m}(A)=\sum _{\varnothing \neq B\subseteq X}{\frac {m(B)}{1-m(\varnothing )}}{\frac {|A\cap B|}{|B|}},\ \forall A\subseteq X}

Ici, les valeurs | A B | {\displaystyle |A\cap B|} et | B | {\displaystyle |B|} correspondent à leur cardinalité (c'est-à-dire au nombre d'éléments).

Notes et références

  1. Philippe SMETS, « Constructing the Pignistic Probability Function in a Context of Uncertainty », dans Uncertainty in Artificial Intelligence, Elsevier, (lire en ligne), p. 29–39

Voir aussi

Articles connexes

Liens externes

  • (en) What is Dempster-Shafer's model?, Philippe Smets, IRIDIA, Université Libre de Bruxelles [PDF]
  • (en) Belief Function and Applications Society
v · m
Index du projet probabilités et statistiques
Théorie des probabilités
Bases théoriques
Principes généraux
Convergence de lois
Calcul stochastique
Lois de probabilité
Lois continues
Lois discrètes
Mélange entre statistiques et probabilités
Interprétations de la probabilité
Théorie des statistiques
Statistiques descriptives
Bases théoriques
Tableaux
Visualisation de données
Paramètres de position
Paramètres de dispersion
Paramètres de forme
Statistiques inductives
Bases théoriques
Tests paramétriques
Tests non-paramétriques
Application
  • icône décorative Portail des probabilités et de la statistique