Accueil
Blog
Décider en présence d’imprécision

Technologie

Décider en présence d’imprécision

Comment décider en présence d’imprécision ?

S. Sochacki, PhD in Computer Science

A2D, ZA Les Minimes, 1 rue de la Trinquette, 17000 La Rochelle, FRANCE

1 Introduction

Imprécision/incertitude/conflit
AI Act, explicabilité

Comment décider en informatique ? Sur quoi se base un système automatique pour prendre une décision ? Bien souvent, ce genre de système s’appuie sur un principe de règles de décision (souvent probabilistes), ou encore sur une approche pignistique (un niveau entièrement dédié à la prise de décision et clairement séparé de la modélisation des données).

Bien qu’une très grande partie des applications traitement d’images grand public soit tournée vers l’amélioration, la restauration ou le traitement des photographies ; dans le cadre industriel, les applications visées portent sur la prise de décision à partir des images. Si les classes d’information utilisées à cette fin sont connues (texture, forme, couleur), elles ne présentent pas toutes le même intérêt dans l’aide à la prise de décision. Dés lors, différentes formes d’apprentissage ont été développées pour identifier le meilleur assemblage possible des informations. Des dizaines de solutions existent pour répondre à cette question, certaines même combinent plusieurs de ces approches pour optimiser au maximum la prise de décision.

Néanmoins, si toutes les classes d’information, et de façon plus fine tous les opérateurs d’extraction d’information (moments de Zernike, attributs D’Haralick, pour n’en citer que deux), ne présentent pas le même intérêt pour la prise de décision, les informations extraites sont quant à elles jugées toutes de même qualité. Or, le traitement d’images provient pour partie du traitement du signal et par là même, du monde de la physique et plus particulièrement de la métrologie. Nous sommes donc bien loin d’un monde binaire, où l’information est vraie ou fausse mais certaine quant à son affectation. En métrologie, la mesure n’existe que liée à un critère de précision ou tolérance. Ce critère quantifie la plage de valeurs au sein de laquelle la mesure se situe avec une bonne certitude. Ce point de vue typique de la métrologie conduite avec des appareils à aiguille est bien souvent oublié lors du passage au numérique. Pourtant, tout scientifique reste sceptique lors de l’annonce d’un résultat avec plus de 3 chiffres derrière la virgule (lorsque cette précision n’a pas été justifiée au préalable).

A2D s’applique à développer des applications utilisant des algorithmes de prise de décision pour répondre à ces nouveaux besoins, en respectant les contraintes liées à l’IA de confiance (AI Act $^1$ , ISO/IEC 42001 $^2$ ) et à la sobriété énergétique. En pratique, nous concevons des applications de traitement et d’analyse de données permettant de comprendre les scènes d’extérieur, numérisées en vue d’y détecter des zones d’intérêt précises, dépendant des usages Métier.

Nous nous applicons également à fournir, à tout moment au cours du traitement de l’information, une explicapibilité quant aux résultats obtenus et aux choix proposés par la machine.

2 Approche probabiliste

Puisque nous cherchons à proposer une nouvelle extension aux outils de prise de décision, il nous apparaissait important de rester dans le cadre des outils à fond mathématique, par opposition aux outils construits sur des bases de règles. Comme les probabilités sont au cœur de ces approches, nous avons choisi de démarrer cette étude à partir de ce formalisme.

Classiquement, nous appelons probabilité, l’évaluation du caractère probable d’un évènement. Elle est représentée par un nombre réel compris entre 0 et 1, indiquant le degré de risque (ou de chance) que l’évènement se produise. Dans l’exemple typique du lancer de pièce de monnaie, l’évènement « coté pile » présente une probabilité de $1/2$ , ce qui signifie qu’après avoir lancé la pièce un très grand nombre de fois, la fréquence d’apparition de « coté pile » sera de $1/2$ .

En probabilité, un évènement peut être à peu près tout ce que l’on imagine, pouvant se produire ou non. Cela peut être le fait qu’il fasse beau demain ou le fait d’obtenir le chiffre 6 en lançant un dé. La seule contrainte est de pouvoir vérifier l’évènement ; il est tout à fait possible de vérifier s’il fera beau demain (évènement que l’on mesure de façon personnelle, le lendemain, en fonction de ses goûts en matière d’ensoleillement, de température etc.), ou si on arrive à obtenir un chiffre 6 avec un dé.

Nous dirons qu’un évènement ayant une probabilité de 0 est impossible, tandis qu’un évènement ayant une probabilité de 1 est certain.

Notons que la probabilité est un outil de prédiction d’évènements du monde réel, et non un outil d’explication de celui-ci. Il s’agit d’étudier des ensembles en les mesurant.

2.1 Définitions

Une expérience est dite aléatoire quand son résultat n’est pas prévisible. Définissons alors $\mathcal{E}$ , une expérience aléatoire ayant pour résultat $\omega$ un élément de $\Omega$ , l’ensemble de tous les résultats possibles, appelé univers des possibles ou référentiel.

Soit $\mathcal{P}(\Omega)$ l’ensemble des parties de $\Omega$ . Un événement est alors une proposition logique liée à une expérience, relative au résultat de celle-ci.

Notons $\mathcal{A}$ l’ensemble des événements et sous-ensemble de $\mathcal{P}$ . Pour tout $A\in\mathcal{A}$ et $B\in\mathcal{A}$ :

$A \cup B$ désigne la réalisation de $A$ ou $B$
$A \cap B$ désigne la réalisation de $A$ et $B$
$\bar{A}=\Omega\backslash A$ désigne le contraire de $A$
$\Omega$ est l’événement certain
$\emptyset$ est l’événement impossible

Quand le référentiel $\Omega$ est fini, $\mathcal{A}$ désigne toutes les parties de $\Omega$ , noté habituellement $2^\Omega$ . Quand le référentiel est $\mathbb{R}$ (ou un intervalle de $\mathbb{R}$ ) la notion de tribu permet de définir $\mathcal{A}$ :

$\mathcal{A}\subseteq\mathcal{P}(\Omega)$
$\emptyset\in\mathcal{A}$
$\forall\{A_1,\ldots,A_n\}\in\mathcal{A}$ , $\bigcup_iA_i\in\mathcal{A}$ et $\bigcap_iA_i\in\mathcal{A}$
$\bar{A}\in\mathcal{A}$ $\forall A\in\mathcal{A}$

Une mesure de probabilité sur un espace mesurable $(\Omega,\mathcal{A})$ est une fonction de $\mathcal{A}$ dans $[0,1]$ telle que :

$P(\Omega)=1$
Pour tous les éléments $A$ et $B$ incompatibles (i.e. $A\cap B=\emptyset$ ), $P(A\cup B)=P(A)+P(B)$

Le nombre $P(A)$ quantifie dans quelle mesure l’événement $A\subseteq\Omega$ est probable.

Dans le cas du lancer de dé, nous pouvons affirmer que $\Omega=\{1,2,3,4,5,6\}$ représente l’ensemble des 6 faces du dé. Ainsi, la probabilité d’obtenir un chiffre compris entre 1 et 6 est certaine, donc égale à 1. Nous écrirons donc $P(1\cup 2\cup 3\cup 4\cup 5\cup 6)=P(\Omega)=1$ .

De la même façon, la probabilité d’obtenir 1 (ou 2, ou 3, ou 4 etc.) est de 1/6. Donc, $P(1)=P(2)=...=P(6)=\frac{1}{6}$ .

En lien avec $P$ , dans le cas où $\Omega$ est fini, une distribution de probabilité est définie comme une fonction $p$ de $\Omega$ dans $[0,1]$ , telle que :

(2.1.1) $\begin{equation*} P(A)=\sum_{\omega\in A}p(\omega) \;\;\;\; \forall A\subseteq\Omega \end{equation*}$

avec la condition de normalisation :

(2.1.2) $\begin{equation*} \sum_{\omega\in\Omega}p(\omega)=1 \end{equation*}$

Notons que $P(A)+P(\bar{A})=1$ .

2.2 Règle de Bayes

L’introduction d’un modèle statistique conduit à une théorie de la décision directement applicable, en principe, au problème de la classification. Cette application repose essentiellement sur la règle de Bayes qui permet d’évaluer des probabilités a posteriori (c’est à dire après l’observation effective de certaines grandeurs) connaissant les distributions de probabilité conditionnelles a priori (c’est-à-dire indépendantes de toute contrainte sur les variables observées). Les probabilités nécessaires à la prise de décision selon la règle de Bayes sont apportées par un (ou plusieurs) classifieur statistique qui indique la probabilité d’appartenance d’un individu donné à chaque classe du problème.

En théorie des probabilités, le théorème de Bayes énonce des probabilités conditionnelles : étant donné deux évènements $A$ et $B$ , le théorème de Bayes permet de déterminer la probabilité de $A$ sachant $B$ , si l’on connaît les probabilités : de $A$ , de $B$ et de $B$ sachant A. Pour aboutir au théorème de Bayes, il faut partir d’une des définitions de la probabilité conditionnelle : $P(A|B)P(B)=P(A \cap B)=P(B|A)P(A)$ , en notant $P(A \cap B)$ la probabilité que $A$ et $B$ aient lieu tous les deux. En divisant de part et d’autre par $P(B)$ , on obtient $P(A|B)=P(B|A)P(A)/P(B)$ soit le théorème de Bayes. Chaque terme du théorème de Bayes a une dénomination usuelle. Le terme $P(A)$ est la probabilité a priori de A. Elle est « antérieure » au sens qu’elle précède toute information sur $B$ . $P(A)$ est aussi appelée la probabilité marginale de $A$ . Le terme $P(A|B)$ est appelée la probabilité a posteriori de $A$ sachant $B$ (ou encore de $A$ sous condition $B$ ) . Elle est « postérieure », au sens qu’elle dépend directement de $B$ . Le terme $P(B|A)$ , pour un $B$ connu, est appelé la fonction de vraisemblance de $A$ . De même, le terme $P(B)$ est appelé la probabilité marginale ou a priori de $B$ .

Mais, comme énoncé précédemment, les valeurs des probabilités utilisées par la règle de Bayes sont apportées par des classifieurs statistiques, voire tout simplement par estimation des lois de probabilités de chacune des classes.

2.3 Prise de décision statistique

Depuis l’hypothèse sur les lois de probabilités des classes du problème (et ses tests de validation) jusqu’à la mesure de la distance au centre de chaque classe en passant par différentes formes d’estimation de modèle, il existe dans le domaine des statistiques un très grand nombre de méthodes et notre propos n’est pas d’en faire une étude exhaustive mais de comparer les théories (statistiques, théorie de la décision…) sur le principe.

Sachons seulement qu’il existe notamment deux types d’approches statistiques : les classifieurs linéaires et les classifieurs quadratiques. Les premiers sont appelés ainsi car leur approche consiste à partitionner l’espace des attributs de façon simple, à partir de droites, chaque droite symbolisant la frontière entre deux classes, comme l’illustre la frontière en vert sur la figure 2.3.1. La seconde approche est plus complexe car elle tente d’estimer la forme des frontières entre les régions, c’est ainsi que l’on obtient la séparation circulaire entre les classes.

exlinquad — Figure 2.3.1 – Frontières selon un classifieur linéaire (Bayes-Normal-1) et un classifieur quadratique (Bayes-Normal-2)

2.3.1 Classifieur Bayesien [93][4][14]

La théorie de la décision de Bayes est une approche statistique du problème. Elle est basée sur les hypothèses suivantes :

Le problème de la décision est exprimé en terme de probabilités
La valeur des probabilités a priori du tirage d’une classe est connue

Soit $\omega$ , une variable aléatoire représentant l’état de l’individu ( $\omega_j$ si l’individu appartient à la classe $j$ ).

Soit $\Omega=\{\omega_1,\ldots,\omega_S\}$ ensemble des $S$ états possibles ou classes d’un problème.

L’ensemble des probabilités a priori $p(\omega_1), p(\omega_2), \ldots$ est calculé à partir des d’observations réalisées sur le système étudié. En l’absence d’autres informations, il ne reste d’autre choix que d’écrire $p($ individu $= \omega_i)=p(\omega_i)$ . Mais s’il est possible d’obtenir d’autres informations (mesures), alors $p(x|\omega_j)$ , densité de probabilité de $x$ sachant que l’individu est $\omega_j$ , ou densité de probabilité conditionnelle à son appartenance à $\omega_j$ , est calculable.

$p(\omega_j)$ est donc la probabilité d’apparition a priori de la classe $\omega_j$ et $p(\omega_j|x)$ est la probabilité que la forme caractérisée par le vecteur $x$ appartienne à $\omega_j$ .

Dans ce cas, nous disposons de $x=\{x_1 \ldots x_d\}$ , le vecteur aléatoire (mesures ou situation) sur ${\mathbb{R}}^d$ . Le problème devient alors : soit un individu et sa mesure $x$ . Comment décider à quelle catégorie ( $\omega_j$ ) affecter cet individu ?

La règle de Bayes donne la réponse :

(2.3.1.1) $\begin{equation*} \protect p(\omega_j|x) = \frac{p(x|\omega_j)p(\omega_j)}{p(x)} \,\,\, , \,\,\, j\in\{1,S\} \end{equation*}$

avec

(2.3.1.2) $\begin{equation*} p(x) = \sum_{j=1}^{S}p(x|\omega_j)p(\omega_j) \end{equation*}$

où $S$ est le nombre de classes différentes et $p(x)$ la distribution de probabilité pour l’ensemble des individus (densité de probabilité du vecteur $x$ ), dans laquelle les échantillons de chaque classe $\omega_j$ apparaissent proportionnellement aux probabilités a priori $p(\omega_j)$ ; c’est le facteur de normalisation.

La règle de décision est alors la suivante :

décider $\omega_j$ si $p(\omega_j|x)=max_{i=1,n}(p(\omega_i|x))$ Ainsi, il devient possible d’énumérer $A=\{\alpha_1,\ldots,\alpha_k\}$ l’ensemble des $a$ décisions possibles.

Il reste à présent à exprimer les densités de probabilité conditionnelle. Pour cela, rappelons l’inégalité de Bienaymé-Tchebicheff :
Soient $X_1, X_2, ..., X_n$ des variables aléatoires indépendantes, toutes d’espérance $\mu$ et de variance $\sigma^2$ . Soit $\bar{X}=\frac{1}{n}\sum_{i=1}^{n}X_i$ alors pour tout $d>0$ :

(2.3.1.3) $\begin{equation*} P(|\bar{X}-\mu|\geq d)\leq \frac{\sigma^2}{nd^2} \end{equation*}$

La probabilité qu’une variable aléatoire s’écarte de plus de d de sa valeur moyenne est d’autant plus faible que sa variance est petite et que d est grand. En particulier (Loi des grands nombres) [7] :

(2.3.1.4) $\begin{equation*} P(|\bar{X}-\mu|\geq d)\longrightarrow 0 \,\,\, quand \,\,\, n\rightarrow +\infty \end{equation*}$

Si $n\geq 30$ , il est admis, en appliquant le théorème central-limite (qui affirme intuitivement que toute somme de variables aléatoires indépendantes et identiquement distribuées tend vers une variable aléatoire gaussienne), que $X_1+X_2+...+X_n$ suit pratiquement une loi Normale. Rappelons que la densité d’une loi Normale est de la forme (sur une dimension) :

(2.3.1.5) $\begin{equation*} x \sim N(\mu, \sigma^2),\,\,\, f(x) = \frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{1}{2}(\frac{x-\mu}{\sigma})^2} \end{equation*}$

Enfin, nous savons que l’espérance mathématique d’une variable aléatoire peut être estimée ponctuellement par :

(2.3.1.6) $\begin{equation*} \mu \simeq \bar{X}=\frac{1}{n}\sum_{i=1}^{n}X_i \end{equation*}$

Donc, pour notre mesure $x$ , les échantillons sont supposés suivre une loi Normale $N(\bar{x},\sigma^2)$ dont la densité de probabilité sera exprimée sous forme matricielle :

(2.3.1.7) $\begin{equation*} P(x)= \frac{1}{2\pi^{\frac{n}{2}}|\Phi|^\frac{1}{2}}\exp\{-\frac{1}{2}(x-\bar{x})^t[\Phi]^{-1}(x-\bar{x})\} \end{equation*}$

avec $\bar{x}$ moyenne d’une classe, $[\Phi_k]$ matrice de covariance de la classe $k$ et $|\Phi_k|$ déterminant de la matrice de covariance de la classe $k$ .

La probabilité conditionnelle est donc exprimée par l’équation suivante :

(2.3.1.8) $\begin{equation*} P(x|\omega_k)= \frac{1}{2\pi^{\frac{n}{2}}|\Phi_k|^\frac{1}{2}}\exp\{-\frac{1}{2}(x-\bar{x}_k)^t[\Phi_k]^{-1}(x-\bar{x}_k)\} \end{equation*}$

L’opération de classification consistera à calculer pour chaque mesure $x$ sa probabilité d’appartenance à toutes les classes, et de l’affecter à la classe qui vérifie la probabilité a posteriori maximum.

2.3.2 Les k-plus proches voisins (KPPV ou KNN)

Cette approche consiste à prendre dans l’espace des attributs un nombre donné ( $k$ ) d’individus connus, individus choisis dans le voisinage de l’individu dont on cherche à estimer la classe d’appartenance. C’est à la connaissance des classes représentées dans ce voisinage que se fait l’étiquetage de l’individu inconnu.

La règle des k-plus proches voisins a été formalisée par Fix et Hodges [5] dans les années 50. Cette règle consiste à baser le choix du voisinage $\mathbb{R}$ sur le nombre d’observations qu’il contient fixé à $k$ parmi le nombre total d’observations $m$ . Autrement dit, il s’agit de sélectionner dans l’ensemble des observations, un sous-ensemble de $k$ individus. C’est le volume $V_k$ de $\mathbb{R}$ qui est variable. L’estimateur de la densité de probabilité s’exprime alors de la façon suivante :

(2.3.2.1) $\begin{equation*} \hat{P}(x)=\frac{k}{m\times V_k} \end{equation*}$

Cette estimation n’est valable que dans les conditions suivantes :

$\begin{equation*} \left\{ \begin{array}{ccc} \lim_{m\rightarrow +\infty}V_k&=&0\\ \lim_{m\rightarrow +\infty}\frac{k}{V_k}&=&0 \end{array} \right. \end{equation*}$

La première hypothèse correspond à un espace complètement occupé par les observations : quand le nombre d’observations est infini, ces observations occupent l’espace de façon uniforme. La seconde hypothèse considère que, pour un nombre infini d’observations, tout sous-ensemble de cardinal $k$ est occupé par un nombre infini d’éléments répartis uniformément.

Dans le cadre de la classification supervisée, la loi de probabilité conditionnelle peut être approximée par :

(2.3.2.2) $\begin{equation*} \hat{P}(x|\omega_q)=\frac{k_q}{m_q\times A} \end{equation*}$

où $k_q$ est le nombre d’observations contenues dans le volume $V_k$ appartenant à la classe d’étiquette $\omega_q$ et $m_q$ le nombre total d’observations appartenant à la classe $\omega_q$ . La loi a posteriori d’observation d’une étiquette conditionnellement à une observation s’obtient avec la règle de Bayes :

(2.3.2.3) $\begin{equation*} \hat{P}(\omega_q|y)=\frac{P(\omega_q)\hat{P}(y|\omega_q)}{\sum_k P(\omega_k)\hat{P}(y|\omega_k)}=\frac{P(\omega_q)\frac{k_q}{m_q\times V_k}}{\hat{P}(y)}=\frac{P(\omega_q)\times m}{m_q}\frac{k_q}{k} \end{equation*}$

Le choix de $k$ est lié à la base d’apprentissage. Prendre $k$ élevé permet d’exploiter au mieux les propriétés locales mais nécessite un grand nombre d’échantillons pour contraindre le volume du voisinage à rester petit. Bien souvent, $k$ est choisi comme la racine carrée du nombre moyen d’élément par classe soit $\sqrt{\frac{m}{c}}$ [2].

2.4 Synthèse

Mais comment alors choisir autre chose que ce qui est statistiquement le plus probable ?

Se pose alors le problème de la mesure d’une précision d’une décision accompagnée de la production d’une mesure de la précision, même si le problème peut être cette mesure.

3 Théorie de l’évidence

Le modèle des croyances transférables MCT (TBM : transferable belief model) est un cadre formel générique développé par Philippe Smets [20] pour la représentation et la combinaison des connaissances. Le TBM est basé sur la définition de fonctions de croyance fournies par des sources d’information pouvant être complémentaires, redondantes et éventuellement non-indépendantes. Il propose un ensemble d’opérateurs permettant de combiner ces fonctions. Il est donc naturellement employé dans le cadre de la fusion d’informations pour améliorer l’analyse et l’interprétation de données issues de sources d’informations multiples. Ce cadre correspond naturellement à celui qui nous préoccupe par son aspect de prise de décision grâce à différentes informations issues de différents attributs.

L’un des points fondamentaux qui caractérisent le TBM est la différenciation des niveaux de représentation des connaissances et de décision. Cette différenciation est beaucoup moins prépondérante pour d’autres approches, particulièrement pour le modèle probabiliste pour lequel la décision est souvent le seul objectif visé. Les mécanismes de raisonnement du TBM sont donc regroupés en deux niveaux comme illustré sur la figure 3.1 :

Le niveau crédal : siège de la représentation des connaissances (partie statique), des combinaisons et du raisonnement sur ces connaissances (partie dynamique)
Le niveau pignistique indiquant une prise de décision en prenant éventuellement en compte le risque et/ou le gain associés à cette décision.

MCT — Figure 3.1 – Mécanismes du modèle des croyances transférables

Dans le cadre de la représentation sous forme de chaîne de traitements, nous nous retrouvons confrontés au problème de l’observation du même événement par plusieurs sources, et de la combinaison de l’information apportée par ces sources (voir figure 3.2), imposant les questions suivantes :

Comment représenter la connaissance d’une source d’information sous forme de fonctions de croyance et quels avantages peut-on tirer d’une telle représentation?
Comment combiner plusieurs sources de fonctions de croyance afin de résumer l’information et d’améliorer la prise de décision?
Comment prendre une décision à partir des fonctions de croyance?

fusion — Figure 3.2 – Chaîne de traitements

3.1 Présentation

Considérons l’exemple d’une reconnaissance de chiffres manuscrits. Les chiffres possibles pouvant être écrits sont appelés hypothèses et l’ensemble des hypothèses forment le cadre de discernement généralement noté $\Omega$ . Pour notre exemple, $\Omega=\{\omega_0,\omega_1,\omega_2,\omega_3,\omega_4,\omega_5,\omega_6,\omega_7,\omega_8,\omega_9\}$ où $\omega_i$ est le symbole représentant le chiffre $i$ . Deux hypothèses ne pouvant être vraies simultanément (on ne peut écrire un symbole représentant à la fois plusieurs chiffres), elles sont supposées être exclusives, ce qui se traduit par une intersection nulle entre elles (i.e. $\{\omega_1\}\cap\{\omega_3\}=\emptyset$ ). Supposons maintenant que le document que nous sommes en train d’étudier soit dégradé, ou bien que le chiffre soit très mal écrit, un lecteur donnerait alors un avis pondéré sur ce chiffre, faisant de lui une source d’information. Avec sa connaissance disponible, le lecteur affirme qu’il s’agit soit du chiffre $\omega_1$ , soit $\omega_7$ ou soit $\omega_9$ . La question est de savoir comment représenter cette information.

Dans le cadre de la théorie des probabilités, la réponse est donnée par le principe d’équiprobabilité, c’est à dire que chaque chiffre se voit attribué la même probabilité ( $\frac{1}{3}$ ) de sorte que la somme de toutes les probabilités soit égale à 1. Ainsi, la distribution des probabilités pour ce chiffre est égale à :

$\begin{equation*} P(\omega_1)=P(\omega_7)=P(\omega_9)=\frac{1}{3} \end{equation*}$

Cette probabilité n’est affectée qu’à des hypothèses prises seules (appelées également singletons).

En théorie de l’évidence, la notion principale est celle de fonctions de croyance au sein de laquelle la connaissance est modélisée par une distribution de masses de croyance. Dans notre exemple, toute la masse de croyance (une unité entière comme avec les probabilités) est affectée à l’union de toutes les hypothèses, soit la proposition $\{\omega_1,\omega_7,\omega_9\}$ :

$\begin{equation*} m(\{\omega_1,\omega_7,\omega_9\})=1 \end{equation*}$

Comme nous pouvons le constater, cette masse ne nous donne aucune information concernant la croyance de chacune des hypothèses ( $\omega_1$ , $\omega_7$ et $\omega_9$ ) qui la compose. Nous pouvons dire alors que la masse de croyance modélise explicitement le doute (ou l’ignorance) sur cet ensemble d’hypothèses. Pour revenir à la théorie des probabilités, la valeur de la probabilité sur une union d’hypothèses découle implicitement de la probabilité sur les singletons, probabilité établie à partir de la somme de toutes les probabilités privée de la partie commune, c’est à dire la probabilité de l’intersection. Soit par exemple :

$\begin{equation*} P(\{\omega_1,\omega_7\})=P(\omega_1)+P(\omega_7)-P(\{(\omega_1,\omega_7)\}) \end{equation*}$

Ici, la probabilité sur $P(\{(\omega_1,\omega_7)\})$ représente la partie commune des évènements « Le chiffre est 1 » et « Le chiffre est 7 » que nous devons retirer afin de ne pas compter les évènements deux fois. Dans le cas où les hypothèses sont exclusives (cas que nous retrouverons tout au long de cet article), on obtient :

$\begin{equation*} \{\omega_1\}\cap\{\omega_7\}=\emptyset \Rightarrow P(\{(\omega_1,\omega_7)\})=0 \Rightarrow P(\{\omega_1,\omega_7\})=P(\omega_1)+P(\omega_7) \end{equation*}$

en prenant en compte le fait que $P(\emptyset)=0$ par définition.

Contrairement aux probabilités, une fonction de masse sur une union d’hypothèses n’est pas égale à la somme des masses des hypothèses composant l’union [10], et c’est justement grâce à cette propriété que nous représentons le doute entre des hypothèses. De plus, les fonctions de croyance ont pour avantage d’être génériques, car elles sont la représentation mathématique d’un sur-ensemble de fonctions de probabilités. En effet, une distribution de masses, où seules les hypothèses singletons ont une masse non nulle, est interprétable comme une distribution de probabilités. Klir et Wierman expliquent dans [10] que les fonctions de croyance généralisent mathématiquement les fonctions de possibilités et que chacune de ces fonctions (probabilités, possibilités et croyances) possède des caractéristiques particulières et permettent de modéliser la connaissance différemment.

Voyons à présent le formalisme mathématique des fonctions de croyance, basé sur les modèles de Dempster [6][7], Shafer [15], des croyances transférables [20] et sur le modèle des Hints [9]. Pour ce travail, nous nous sommes restreints au cadre axiomatisé et formalisé du modèle des croyances transférables développé par P. Smets.

3.2 Formalisme

3.2.1 Introduction

Si nous revenons au problème de la gestion de sources multiples d’informations (comme illustré par la figure 3.2), ce que nous cherchons à faire est de déterminer l’état réel $\omega_0$ du système étudié en utilisant plusieurs observations issues de plusieurs observateurs. Dans notre cas, $\omega_0$ sera la décision à produire et les différents attributs fournissent les observations sur le système.

Nous supposons que cet état $\omega_0$ prend des valeurs discrètes $\omega_k$ (les hypothèses) et que l’ensemble des $N$ hypothèses possibles est appelé cadre de discernement (ou \textbf{univers de discours}), noté généralement :

(3.2.1.1) $\begin{equation*} \Omega=\{\omega_1,...,\omega_k,...,\omega_N\}=\bigcup_{k=1}^{N}\{\omega_k\} \end{equation*}$

Le nombre total d’hypothèses composant $\Omega$ est appelé cardinal et s’écrit comme $|\Omega|=N$ . Comme nous l’avons vu précédemment, toutes les hypothèses sont considérées exclusives.

L’ensemble des observateurs du système (les capteurs de la figure 3.2) fournit un avis pondéré, représenté grâce à une fonction de croyance, à propos de son état réel $\omega_0\subseteq \Omega$ . Nous appelons alors ces capteurs, des sources de croyance.

3.2.2 Fonctions de masse

Notons $2^\Omega$ l’espace formé de toutes les parties de $\Omega$ , c’est à dire l’espace rassemblant tous les sous-ensembles possibles formés des hypothèses et unions d’hypothèses, soit :

$\begin{equation*} 2^\Omega=\{\emptyset,\{\omega_1\},\{\omega2\},\{\omega_1,\omega_2\},\{\omega_3\},\{\omega_1,\omega_3\},\{\omega_2,\omega_3\},\{\omega_1,\omega_2,\omega_3\},...,\{\omega_1,...,\omega_N\}\} \end{equation*}$

Soit $A$ une proposition telle que $A\subseteq\Omega$ , par exemple $A=\{\omega_1,\omega_2\}$ . $A$ représente explicitement le doute entre les hypothèses qui la compose ( $\omega_1$ et $\omega_2$ ). Comme nous l’avons vu plus haut, les masses de croyances sont non-additives, ce qui est une différence fondamentale avec la théorie des probabilités. Ainsi, la masse de croyance $m(A)$ allouée à $A$ ne donne aucune information à propos des hypothèses et sous ensembles composant $A$ [10].

Nous pouvons définir une distribution de masses de croyance (BBA : basic belief assignment) comme un ensemble de masses de croyance concernant des propositions quelconques $A\subseteq\Omega$ vérifiant:

(3.2.2.1) $\begin{equation*} \sum_{A\subseteq\Omega}m(A)=1 \end{equation*}$

Chacun des capteurs observant le système apportera sa propre distribution de masse.

La masse $m(A)$ fournie par un capteur est la part de croyance de ce capteur en la proposition « $\omega_0\in B$ » où $\omega_0$ est l’état réel du système observé. Tout élément $B$ de masse non nulle (soit $m(B)>0$ ) est appelé élément focal de la distribution de masses de croyance. Ramasso [13] présente dans son mémoire de Thèse un ensemble notable de distributions de masses de croyance.

Quand l’univers du discours contient la totalité des hypothèses possibles (c’est à dire lorsqu’il est exhaustif), il contient forcément l’hypothèse permettant de décrire le système observé. Dans le cas contraire, le cadre de discernement n’est pas adapté au problème traité.

A partir du moment où $\Omega$ est exhaustif, la masse de l’ensemble vide est nulle ( $m(\emptyset)=0$ ), la masse est dite normale, et la problématique entre alors dans le cadre d’un monde fermé comme dans le cas du modèle de Shafer [15].

Dans le cas du modèle des croyances transférables, l’univers du discours peut être non exhaustif; la masse de l’ensemble est non nulle ( $m({\emptyset})\neq 0$ ) et elle est dite sous normale et dans ce cas, la problématique s’inscrit dans le cadre d’un monde ouvert. Ce type de construction permet de redéfinir, par exemple, le cadre de discernement en ajoutant une hypothèse en fonction de la masse de l’ensemble vide, comme une hypothèse de rejet. Les hypothèses de rejet correspondent à des états du genre « je ne sais pas » , permettant en fin de chaîne de rejeter un individu pour lequel le doute est trop grand au lieu de prendre le risque de le classer malgré tout. Pour passer d’un monde ouvert à un monde fermé, il faut redistribuer la masse de l’ensemble vide sur les autres sous-ensembles de l’espace $2^\Omega$ [11].

Pour résumer ce que nous avons vu jusqu’à présent, la fonction de masse est déterminée a priori, sans nécessiter de considérations probabilistes. Elle peut correspondre à l’attribution, de façon subjective, de degrés de crédibilité en la réalisation des différents évènements envisageables sur $\Omega$ , par un observateur.

L’attribution des valeurs de $m$ sert à exprimer le degré avec lequel l’expert ou l’observateur juge que chaque hypothèse est susceptible de se réaliser. Ainsi, $m(\Omega)$ décrit son imprécision relativement à ces degrés.

3.2.3 La règle de combinaison de Dempster

Si nous revenons à la figure 3.2, nous constatons que le problème qui se pose est la fusion d’information, consistant à combiner des informations hétérogènes issues de plusieurs sources afin d’améliorer la prise de décision [3].

Voyons à présent un outil formel développé dans le cadre du modèle des croyances transférables permettant la fusion d’information. Nous posons l’hypothèse que les sources sont distinctes [16][21][22][23] par analogie avec l’indépendance des variables aléatoires en statistique.

Il peut arriver que pour la même hypothèse, deux capteurs apportent une information complètement différente. D’un point de vue formel, lors de la combinaison de deux fonctions de masse de croyance $m_1$ et $m_2$ , l’intersection entre les éléments focaux peut être vide. La fonction de masse de croyance résultat dans cette combinaison sera non nulle sur l’ensemble vide. Cette valeur quantifie alors la discordance entre les sources de croyance, et est appelée conflit [17]. Une normalisation peut être effectuée, ramenant la règle de combinaison conjonctive à la règle orthogonale de Dempster [6][7] (notée $\oplus$ ) utilisée dans le modèle de Shafer [15][18] :

(3.2.3.1) $\begin{eqnarray*} m_{1\oplus 2}(A)=(m_1 \oplus m_2)(A)=\left\{ \begin{array}{lccc} \frac{m_{1\overlay{\cap}{\bigcirc}2}(A)}{1-m_{1\overlay{\cap}{\bigcirc}2}(\emptyset)}, & \forall A\subseteq\Omega & \mathrm{si }&A\neq\emptyset\\ 0 & & \mathrm{si }&A=\emptyset\\ \end{array} \right. \end{eqnarray*}$

Une autre façon d’écrire cette règle de combinaison est :

(3.2.3.2) $\begin{eqnarray*} m(A)=\frac{\sum_{B\cap C=A}m_1(B)m_2(C)}{\sum_{B\cap C\neq0}m_1(B)m_2(C)} & \forall A\subseteq\Omega \end{eqnarray*}$

Avec, pour mesure du conflit entre les sources :

(3.2.3.3) $\begin{equation*} K = \sum_{B\cap C=0}m_1(B)m_2(C) \end{equation*}$

3.2.4 Un affaiblissement simple

La règle d’affaiblissement simple pour intégrer la fiabilité des sources. L’application de la règle de combinaison disjonctive peut s’avérer trop conservatrice lorsque les sources de fonctions de masse de croyance ne sont pas fiables. Elle peut ainsi mener à une fonction de masse de croyance complètement non-informative (vide). Dans certaines applications, il est cependant possible de quantifier la fiabilité ce qui permet d’appliquer une règle de combinaison moins conservatrice dans le cas de sources non fiables.

La prise en compte de la fiabilité dans le cadre des fonctions de croyance porte le nom d’affaiblissement car le processus consiste à pondérer la masse des éléments d’une fonction de masse de croyance. Les premiers travaux sur l’affaiblissement dans le cadre des fonctions de croyance ont été développés par Shafer [15], axiomatisés par Smets [16] et généralisés par Mercier et Denœux [12]. L’affaiblissement généralisé a été appelé affaiblissement contextuel.

L’affaiblissement simple de Shafer d’une fonction de masse de croyance $m$ est défini comme la pondération de chaque masse $m(B)$ de la distribution par un coefficient $(1-\alpha)$ appelé fiabilité et où $\alpha\in[0,1]$ est le taux d’affaiblissement.

Formellement :

(3.2.4.1) $\begin{eqnarray*} m^\alpha(B) =& (1-\alpha).m(B),&\forall B\subset\Omega\\ m^\alpha(\Omega) =& (1-\alpha).m(\Omega)+\alpha \end{eqnarray*}$

Par le principe du minimum d’information (entropie maximale), le reste de la masse (après pondération) est transféré sur l’élément d’ignorance $\Omega$ . Plus la source est fiable (et plus le taux d’affaiblissement $\alpha$ est faible), moins la fonction de masse de croyance est modifiée alors que, plus la fiabilité diminue, plus la fonction de masse de croyance issue de l’affaiblissement tend vers la fonction de masse de croyance vide.

3.3 La décision pignistique

A partir de l’ensemble des fonctions de croyance fournies par tous les capteurs, et suite à leur combinaison par la règle de Dempster, nous obtenons une fonction de croyance unique pour chacune des hypothèses possibles modélisant la connaissance du système. Il faut ensuite, à partir de cette connaissance, prendre une décision sur l’une des hypothèses.

Notons que les hypothèses du système ne représentent pas forcément les seules classes possibles (i.e. les 26 lettres de notre alphabet). Il est également possible de créer une nouvelle hypothèse qui correspondrait à l’évènement « aucune des hypothèses connues ». On parle alors de rejet, c’est à dire que l’individu inconnu n’est pas réinjecté dans la chaîne, il est tout simplement classé comme « impossible à reconnaître ». La mesure du conflit des capteurs lors de la fusion de Dempster (voir l’equation 3.2.3.3) est aussi une mesure sur laquelle le système peut se baser pour rejeter l’individu.

Les systèmes de fusion d’information, qu’ils soient basés sur la théorie des probabilités, des possibilités ou des fonctions de croyance, ont pour finalité la prise de décision et l’analyse de cette décision. Prendre une décision consiste à choisir une hypothèse sur un cadre de pari, généralement le cadre de discernement $\Omega$ . La prise de décision peut être réalisée de façon automatique ou laissée à la responsabilité de l’utilisateur final (par exemple dans le cas de de l’aide au diagnostique dans le domaine de la Médecine).

Dans le cadre du modèle des croyances transférables, la phase de décision s’appuie sur la distribution de probabilités pignistiques notée $\textrm{BetP}\{m\}$ à partir de la distribution de masse $m$ [19]. La transformée pignistique consiste à répartir de manière équiprobable la masse d’une proposition $B$ sur les hypothèses contenues dans $B$ .

Formellement :

(3.3.1) $\begin{eqnarray*} \textrm{Bet}\{m\}: & \Omega\rightarrow[0,1]\\ & \omega_k\mapsto\textrm{BetP}\{m\}(\omega_k) \end{eqnarray*}$

où $\textrm{BetP}\{m\}(\omega_k),\forall\omega_k\in\Omega$ est donnée par :

(3.3.2) $\begin{equation*} \textrm{BetP}\{m\}(\omega_k)=\frac{1}{(1-m(\emptyset))}\sum_{B\subseteq\Omega,\omega_k\in B}\frac{m(B)}{|B|} \end{equation*}$

La décision est généralement prise en choisissant l’élément $\omega_k$ possédant la plus grande probabilité pignistique :

(3.3.3) $\begin{equation*} \omega_k=\textrm{arg}\max_{\omega_k\in\Omega}\textrm{BetP}\{m\}(\omega_k) \end{equation*}$

L’agent qui se base sur la transformée pignistique lors de la phase de prise de décision présente un comportement rationnel en maximisant l’utilité espérée. Alternativement, les plausibilités et les crédibilités peuvent être utilisées lorsque l’agent présente une attitude plutôt optimiste ou pessimiste.

Dans le cas des plausibilités, on dit que l’agent a une attitude optimiste dans le sens où la plausibilité d’un élément représente la valeur maximale de la masse de croyance sur cet élément qui pourrait être atteinte si des informations supplémentaires parvenaient au système de fusion (ce dernier utilisant la combinaison conjonctive pour intégrer cette nouvelle information). La distribution de probabilités sur les singletons à partir de laquelle une décision peut être prise est alors donnée $\forall\omega_k\in\Omega$ par :

(3.3.4) $\begin{equation*} \textrm{PIP}\{m\}(\omega_k)=\frac{pl(\omega_k)}{\sum_{\omega_k\in\Omega}pl(\omega_k)} \end{equation*}$

Notons que la plausibilité d’un singleton $pl(\omega_k)$ est égale à sa communalité $q(\omega_k)$ . De la même manière, un critère adapté à un agent « pessimiste » peut être obtenu en utilisant les crédibilités. La crédibilité d’un singleton $bel(\omega_k)$ est simplement égale à sa masse après normalisation de la fonction de masse de croyance $m$ . Remarquons que pour tout élément $A\in2^\Omega$ :

(3.3.5) $\begin{equation*} bel(A)\leq \textrm{BetP(A)}\leq pl(A) \end{equation*}$

et en particulier lorsque les plausibilités et les crédibilités sont calculées sur les singletons.

Pour le problème de prise de décision, nous supposons avoir une fonction de croyance $m$ sur $\Omega$ qui résume l’ensemble des informations apportées sur la valeur de la variable $y$ . La décision consiste à choisir une action $a$ parmi un ensemble fini d’actions $\mathcal{A}$ . Une fonction de perte $\lambda:\mathcal{A}\times\Omega\rightarrow\mathbb{R}$ est supposée définie de telle manière que $\lambda(a,\omega)$ représente la perte encourue si l’action $a$ est choisie lorsque $y=\omega$ . A partir de la probabilité pignistique, chaque action $a\in\mathcal{A}$ peut être associée à un risque défini comme le coût espéré relatif à $p_m$ si $a$ est choisie :

(3.3.6) $\begin{equation*} R(a)=\sum_{\omega\in\Omega}\lambda(a,\omega)p_m(\omega) \end{equation*}$

L’idée consiste ensuite à choisir l’action qui minimise ce risque, généralement appelé risque pignistique. En reconnaissance de formes, $\Omega=\{\omega_1,...,\omega_Q\}$ est l’ensemble des classes et les éléments de $\mathcal{A}$ sont généralement les actions $a_q$ qui consistent à assigner le vecteur inconnu à la classe $\omega_q$ .

Il est démontré que la minimisation du risque pignistique $R$ conduit à choisir la classe $\omega_0$ de plus grand probabilité pignistique [8]. Si une action supplémentaire de rejet $a_0$ de coût constant $\lambda_0$ est possible, alors le vecteur est rejeté si $p_m(\omega_0)<1-\lambda_0$ .

3.4 Prise de décision à partir de fonctions de croyance

Voyons à présent comment construire, en vue de la prise de décision, les fonctions de croyances sur les différentes hypothèses à partir de la précision des attributs, de la précision des classifieurs et des données en sortie de l’étage de classification.

Au niveau crédal du modèle des croyances transférables, afin d’obtenir les fonctions de croyance à partir des données d’apprentissage, deux familles de techniques sont généralement utilisées : les méthodes basées sur la vraisemblance qui utilisent l’estimation des densités et une méthode basée sur la distance dans laquelle les jeux de masses sont construits directement à partir des distances aux vecteurs d’apprentissage.

Méthodes basées sur la vraisemblance.
Les densités de probabilités conditionnellement aux classes sont supposée connues. En ayant observé , la fonction de vraisemblance est une fonction de dans définie par , pour tout . A partir de , Shafer [15] a proposé de construire une fonction de croyance sur définie par sa fonction de plausibilité comme :

(3.4.1) $\begin{eqnarray*} pl(A)=\frac{\max_{\omega_q\in A}[L(\omega_q|X)]}{\max_{q}[L(\omega_q|X)]} & \forall A\subseteq\Omega \end{eqnarray*}$

A partir de considérations axiomatiques, Appriou [1] a proposé une autre méthode basée sur la construction de $Q$ fonctions de croyances $m_q(.)$ . L’idée consiste à prendre en compte de manière séparée chaque classe et à évaluer le degré de croyance accordé à chacune d’entre elles. Dans ce cas, les éléments focaux de chacune des fonctions de croyance $m_q$ sont les singletons $\{\omega_q\}$ , les sous ensembles complémentaires $\bar{\omega_q}$ et $\Omega$ . Appriou obtient ainsi deux modèles différents :
- Modèle 1 :
  
  (3.4.2) $\begin{eqnarray*} m_q(\{\omega_q\}) = \alpha_q\frac{R.L(\omega_q|x)}{1+R.L(\omega_q|x)}\\ m_q(\overline{\omega_q}) = \alpha_q\frac{1}{1+R.L(\omega_q|x)}\\ m_q(\Omega) = 1-\alpha_q \end{eqnarray*}$
- Modèle 2 :
  
  (3.4.3) $\begin{eqnarray*} m_q(\{\omega_q\}) = 0\\ m_q(\overline{\omega_q}) = \alpha_q(1-R.L(\omega_q|x))\\ m_q(\Omega) = 1-\alpha_q(1-R.L(\omega_q|x)) \end{eqnarray*}$
Ici, $\alpha_q$ est un coefficient qui peut-être utilisé pour modéliser une information complémentaire (comme par exemple la fiabilité d’un capteur), et $R$ est une constante de normalisation qui est choisie dans $]0,(\sup_x \max_q(L(\omega_q|x)))^{-1}]$ . En pratique, les performances de ces deux modèles semblent être équivalentes. Cependant, Appriou recommande l’utilisation du modèle 2 qui a l’avantage d’être consistant avec le « théorème de Bayes généralisé » proposé par Smets dans [16]. A partir de ces $Q$ fonctions de croyance et en utilisant la règle de combinaison de Dempster, une fonction de croyance unique $m$ est obtenue par $m=\bigoplus_qm_q$ .
Méthode basée sur la distance.
La seconde famille de modèles se base sur des informations de distance. Dans cette dernière, citons comme exemple l’extension de l’algorithme des $k$ plus proches voisins qui a été introduit par T. Denœux dans [18]. Dans cette méthode, une fonction de croyance $m_i$ est directement construite en utilisant les informations apportées par les vecteurs $x^i$ situés dans le voisinage du vecteur inconnu $x$ par :

(3.4.4) $\begin{eqnarray*} m^i(\{\omega_k\})=\alpha^i\phi^i(d^i)\\ m^i(\Omega) = 1-\alpha^i\phi^i(d^i)\\ m^i(A) = 0,\forall A\in 2^\Omega \backslash \{\{\omega_k\},\Omega\} \end{eqnarray*}$

où $d^i$ est la distance euclidienne du vecteur inconnu au vecteur $x^i$ , $\alpha^i$ un paramètre associé au $i$ -ème voisin et $\phi^i(d^i)=e^{-\gamma^i(d^i)^2}$ avec $\gamma^i$ un paramètre positif (rappelons que l’opérateur $\backslash$ signifie « privé de »). La méthode des $k$ plus proches voisin permet d’obtenir $k$ fonctions de croyance à agréger par la règle de combinaison pour la prise de décision.

4 Proposition

4.1 Principe

La théorie de l’évidence présente plusieurs éléments d’intérêt dans notre quête d’une mesure de la précision associée à la décision, ainsi que dans l’intégration d’une telle mesure dans cette prise de décision. Le premier d’entre eux est certainement celui de pouvoir proposer un bornage pessimiste et optimiste de la décision, ce qui peut en première instance être rapproché de la tolérance souhaitée en association avec la décision. Le second correspond ensuite à l’introduction du facteur d’affaiblissement dans le propos. Par son entremise, il est possible d’intégrer un facteur prenant en compte la fiabilité de l’opérateur fournissant l’information. Cette fiabilité, ou confiance, est déduite d’un apprentissage effectué au préalable, c’est à dire hors ligne. Or tel qu’est construite l’approche, quelque soit la valeur établie, quelque soit l’objet à partir duquel est établie la mesure, celle ci sera considérée au même niveau d’importance que toutes celles issues de l’opérateur.

Il ne faut pas voir ici une critique de la construction du facteur d’affaiblissement qui a été introduit pour permettre la combinaison de différentes sources d’information, tels que des capteurs ou des bandes de fréquences dans des IRM. Derrière cette proposition se place l’hypothèse de linéarité de comportement de la source d’information face au bruit et/ou à l’information à acquérir. Cette hypothèse certainement valide dans le contexte où a été développée cette théorie n’est en revanche pas valide dans notre contexte plus générique.

Deux solutions s’offrent à nous pour développer notre proposition, la première serait d’intégrer un second facteur dans la formulation qui ne serait dépendant que de l’objet à mesurer au travers de l’opérateur $j$ . La seconde solution consiste à ne conserver qu’un seul facteur d’affaiblissement intégrant les deux aspects à prendre en compte :

L’apport du type d’information considéré dans la prise de décision. Ce qui correspond à une pertinence a priori, c’est à dire uniquement liée à l’opérateur et considérée à la suite de l’apprentissage avant la phase de prise de décision proprement dite (phase dite en ligne).
La qualité de la mesure, que nous appelons précision. Cette mesure de précision est directement dépendante de l’objet à mesurer vu au travers de l’opérateur, mesure effectuée pour prendre en compte les non linéarités de comportement de l’opérateur ou du capteur (i.e. cas des réponses en fonction des différent tissus dans l’imagerie médicale). Cette mesure de précision sera donc appelée mesure de précision a posteriori car établie à l’issu de la mesure.

Dans les deux cas, nous proposons de conserver l’écriture d’Appriou. La combinaison des différents éléments d’affaiblissement étant écrite sous forme multiplicative. Pour des raisons de temps nécessaire, nous n’avons pas associé dans ce travail ces deux parties liées à l’estimation de la précision totale (a priori et a posteriori). Entre autre raison à cette décision intervient notamment la problématique de l’estimation de la précision a priori, fortement dépendante de la construction de la base d’apprentissage.

Voyons à présent une partie des pistes envisagées pour cette question dans le cadre de la classification. Néanmoins, la littérature sur le sujet étant déjà importante, nous avons estimé qu’il existait déjà de nombreuses bases de réponse à cette question.

4.2 Mise en œuvre

Les fonctions de croyances par classe/classifieur/attribut sont combinées (Dempster) afin de construire une fonction de croyance par classe. La prise de décision est ensuite faite selon l’équation 3.3.3. Le mécanisme de décision, est schématisé par la figure 4.2.1. Cette figure représente l’enchaînement des processus ainsi que les échanges entre eux. Nous avons représenté ici chacune des variables du formalisme, son origine et sa destination. La source du flux illustrant l’individu à analyser ( $x^*$ ) n’est pas représentée car nous ne traitons pas de cette partie. $x^*$ peut être un objet injecté directement dans le processus, mais il peut être issu de traitements postérieurs.

DFD_chaine — Figure 4.2.1 – Diagramme des flots de données de la chaîne de traitements

L’exploitation de l’expression d’Appriou, et notre version modifiée de l’expression d’Appriou exploite des étiquettes discrètes basées sur la fonction de vraisemblance $L(\omega_q|x)$ liant un individu $x$ à son appartenance à la classe $\omega_q$ .

Afin d’obtenir ces fonctions et selon le schéma de la figure 4.2.2 ces étiquettes sont dans notre cas issues d’un étage de classification liant l’individu à la classe $\omega_q$ . Classiquement dans ce cadre, la fonction de vraisemblance $L(\omega_q|x)$ est alors liée à la distance $C_i(\omega_q|x)$ de l’individu $x$ à la classe $\omega_q$ selon le classifieur $i$ (suivant le classifieur, la distance peut être remplacée par un degré d’appartenance ou une probabilité). Cependant, la capacité d’associer un individu à une étiquette par un classifieur est dépendante du jeu d’attributs utilisé. De la même façon, chaque classifieur propose un partitionnement différent de l’espace des attributs en fonction du modèle de classe utilisé ou des métriques mises en œuvre. Notre écriture reliera donc la fonction de vraisemblance $L(\omega_q|x)$ à la distance $C_i(\omega_q|A_j(x))$ , où $A_j(x)$ représente le vecteur d’attributs fourni par l’opérateur $j$ (moments de Zernike à l’ordre 15 par exemple ou histogramme couleur sur 32 bins obtenu par fuzzy C-means etc.) et $C_i$ faisant référence au classifieur $i$ .

A diagram of a process Description automatically generated — Figure 4.2.2 – Chaîne de traitements intégrant la précision des attributs

Le choix de cette écriture nous permet dés lors de combiner plusieurs étiquettes issues de classifieurs différents et/ou d’attributs différents. Selon le protocole choisi, les différents classifieurs seront mis en compétition directement ou une étape de sélection dynamique du meilleur d’entre eux sera opérée avant cette étape de fusion. Dans ce dernier cas, la compétition fusionne les étiquettes issues de différents attributs vus au travers du meilleur classifieur pour chacun d’entre eux. L’expression à laquelle nous aboutissons est directement déduite de l’équation 3.3.3 :

(4.2.1) $\begin{eqnarray*} \left\{ \begin{array}{ll} m_{ijq}(\{\omega_q\})&=0\\ m_{ijq}(\overline{\omega_q})&=\alpha_{jq}(1-R_{ijq}.C_i(\omega_q|A_j(x)))\\ m_{ijq}(\Omega)&=1-m_{ijq}(\overline{\omega_q})\\ \end{array} \right.\\ \nonumber\forall {i}\in[1,n_c], \forall {j}\in[1,n_a], \forall {q}\in[1,n_q] \end{eqnarray*}$

Appriou intègre $R$ , un paramètre de normalisation de la formule établit pour que la masse de croyance $m_{ijq}(\overline{\omega_q})$ soit comprise entre 0 et 1. $R$ est donc une valeur comprise entre $0$ et la valeur maximale qui peut être estimée pour $C_i(\omega_q|A_i(x))$ . Cette valeur de $R$ est unique pour le classifieur $i$ et correspond à la plus grande distance identifiée ou possible entre un individu et les classes définies pour ce classifieur, d’où :

(4.2.2) $\begin{eqnarray*} \nonumber\mbox{pour que }0\leq 1-\frac{x}{y}\leq 1\mbox{ il faut }y\geq x\\ \nonumber\mbox{d'où }y=\sup_x(\max_q(C_i(\omega_q|A_j(x))))\\ 0<R\leq\frac{1}{\sup_x(\max_q(C_i(\omega_q|A_j(x))))} \end{eqnarray*}$

La masse de croyance que nous venons d’établir est $m_{ijq}(\{\omega_q\})$ , c’est à dire la masse de croyance associée au fait que la classe $q$ soit attribuée à l’individu $x$ par le classifieur $i$ pour le vecteur d’attributs $j$ . Or, ce qui nous intéresse c’est la décision d’affectation finale de la classe $q$ à l’individu $x$ et par voie de conséquence la masse de croyance en la classe $q$ , $m_q(\{\omega_q\})$ , et les masses associée $m_q(\overline{\omega_q})$ et $m_q(\Omega)$ :

(4.2.3) $\begin{eqnarray*} \left\{ \begin{array}{l} m_q(\{\omega_q\})\\ m_q(\overline{\omega_q})\\ m_q(\Omega) \end{array} \right.\\ \nonumber\forall q\in[1,n] \end{eqnarray*}$

A partir du modèle de combinaison de Dempster, nous formalisons cette prise de décision à partir des $q$ décisions intermédiaires sur un ensemble de $n$ étiquettes pour un jeu unique d’attributs :

(4.2.4) $\begin{eqnarray*} \left\{ \begin{array}{ll} m(\{\omega_k\})&=\bigoplus_{q=1}^{n_q}m_{iq}(\{\omega_k\})\\ m(\overline{\omega_k})&=\bigoplus_{q=1}^{n_q}m_{iq}(\overline{\omega_k}) \end{array} \right.\\ \nonumber\forall q\in[1,n], \forall i\in[1,n_c] \end{eqnarray*}$

et :

(4.2.5) $\begin{equation*} m(\Omega)=1-\sum_{i=1}^{n}(m(\{\omega_i\})+m(\overline{\omega_i}))\\ \end{equation*}$

De façon plus générale, en présence de plusieurs jeux d’attributs issus d’opérateurs différents (ou paramètres différents), la règle de combinaison de Dempster nous permet d’aboutir à la formulation générale :

(4.2.6) $\begin{equation*} \left\{ \begin{array}{ll} m(\{\omega_k\})&=\bigoplus_{q=1}^{n_q}\bigoplus_{i=1}^{n_c}\bigoplus_{j=1}^{n_a}m_{ijq}(\{\omega_k\})\\ m(\overline{\omega_k})&=\bigoplus_{q=1}^{n_q}\bigoplus_{i=1}^{n_c}\bigoplus_{j=1}^{n_a}m_{ijq}(\overline{\omega_k})\\ \end{array} \right. \end{equation*}$

Le diagramme de flots de données de la figure 4.2.1 illustre le fonctionnement de cette écriture.

Bibliographie

[1] A. Appriou. Probabilités et incertitudes en fusion de données multi-senseurs. Revue Scientifique et Technique de la Défense, 11 :27–40, 1991.
[2] D. Arrivault. Apport des graphes dans la reconnaissance non-contrainte de caractères manuscrits anciens. PhD thesis, Université de Poitiers, 2002.
[3] I. Bloch. Fusion d’informations numériques : panorama méthodologique. In Journées Nationales de la Recherche en Robotique, 2005.[7]
[4] R. Caruana and A. Niculescu-Mizil. An empirical comparison of supervised learning algorithms. In ICML ’06 : Proceedings of the 23rd international conference on Machine learning, pages 161–168, New York, NY, USA, 2006. ACM.
[5] T. M. Cover and P. E. Hart. Nearest neighbor pattern classification. IEEE Trans. on Information Theory, 13(1) :21–27, 1967.
[6] A. P. Dempster. Upper and lower probabilities induced by multiple valued mappings. Annals of Mathematical Statistics, 38 :325–339, 1967.
[7] A. P. Dempster. A generalization of bayesian inference. Journal of the Royal Statistical Society, 30 :205–247, 1968.
[8] T. Denœux. Analysis of evidence-theoretic decision rules for pattern classification. Pattern Recognition, 30(7) :1095–1107, 1997.
[9] J. Kholas and P. A. Monney. Lecture Notes in Economics and Mathematical Systems, volume 425, chapter A mathematical theory of hints : An approach to the Dempster-Shafer theory of evidence. Springer-Verlag, 1995.
[10] G. J. Klir and M. J. Wierman. Uncertainty-based information. Elements of generalized information theory, 2nd edition. Studies in fuzzyness and soft computing. Physica-Verlag, 1999.
[11] E. Lefevre, O. Colot, and P. Vannoorenberghe. Belief function combination and conflict management. Information Fusion, 3 :149–162, 2002.
[12] D. Mercier, B. Quost, and T. Denoœux. Refined modeling of sensor reliability in the belief function framework using contextual discounting. Information Fusion, 2007.
[13] E. Ramasso. Reconnaissance de séquences d’états par le Modèle des Croyances Transférables – Application à l’analyse de vidéos d’athlétisme. PhD thesis, Université Joseph Fourier de Grenoble, 2007.
[14] I. Rish. An empirical study of the naive bayes classifier. In IJCAI-01 workshop on « Empirical Methods in AI », 2001.
[15] G. Shafer. A Mathematical Theory of Evidence. Princeton University Press, 1976.
[16] P. Smets. Beliefs functions : The disjunctive rule of combination and the generalized bayesian theorem. Int. Jour. of Approximate Reasoning, 9 :1–35, 1993.
[17] P. Smets. The nature of the unnormalized beliefs encountered in the transferable belief model. In Proceedings of the 8th Annual Conference on Uncertainty in Artificial Intelligence, pages 292–297, 1992.
[18] P. Smets. Advances in the Dempster-Shafer Theory of Evidence – What is Dempster-Shafer’s model ? Wiley, 1994.
[19] P. Smets. Decision making in the tbm : The necessity of the pignistic transformation. Int. Jour. of Approximate Reasoning, 38 :133–147, 2005.
[20] P. Smets and R. Kennes. The transferable belief model. Artificial Intelligence, 66(2) :191–234, 1994.
[21] B. Yaghlane, P. Smets, and K. Mellouli. Belief function independence : I. the marginal case. Int. Jour. of Approximate Reasoning, 29 :47–70, 2001.
[22] B. Yaghlane, P. Smets, and K. Mellouli. Belief function independence : II. the conditionnal case. Int. Jour. of Approximate Reasoning, 31(1) :31–75, 2002.
[23] B. Yaghlane, P. Smets, and K. Mellouli. Independence concept for belief functions. In Physica-Verlag, editor, Technologies for constructing intelligent systems : Tools, 2002.[93]

$^1$ Proposition de règlement du parlement européen et du conseil établissant des règles harmonisées concernant l’intelligence artificielle (législation sur l’intelligence artificielle) et modifiant certains actes législatifs de l’union

$^2$ ISO/IEC 42001