Prendre une décision à l’aide des fonctions de croyances

de | 2017-05-11

Aujourd’hui je vais vous parler d’un de mes travaux de recherche sur la prise de décision dans le cadre de la reconnaissance de gestes par vision 3D. Que va-t-on manger ce soir ? Qui a tué Pamela Rose ? Quel est l’âge du capitaine ? Autant de questions auxquels on peut essayer de répondre avec un joli cadre mathématique, la théorie des fonctions de croyances. Dans ce billet je vais essayer de vulgariser au maximum mais certains passages nécessitent des connaissances en traitement d’image. Ils ne sont cependant pas nécessaire pour comprendre ce dont je vais parler et vont servir d’exemples.

Introduction à la théorie des fonctions de croyances

Cette partie est inspirée des documents en sources qui sont cités plus bas.

Pour introduire la théorie des fonctions de croyances ou théorie de Dempster-Shafer prenons un exemple pratique. L’objectif de ce formalisme est de pouvoir répondre à une question. Prenons un cas concret, l’inspecteur Bullit est sur une nouvelle affaire, une sordide histoire de meurtre. Il cherche a répondre à la question :

Mais qui a tué Pamela Rose ?

L’inspecteur Bullit a identifié 3 suspects, Alice, Bob et Charles. On a donc 3 hypothèses élémentaires : Alice, ou Bob, ou Charles a tué Pamela Rose, que l’on notera respectivement A, B et C. Ce sont les éléments focaux et forment le cadre de discernement \(\Omega = \{A,B,C\} \).

Enfin Bullit dispose de deux informateurs que l’on appelle des experts ou sources d’informations.

Bien modéliser le problème

Évidemment si les deux sources concordent alors le bon suspect est facilement a identifié. Malheureusement pour Bullit la réalité est souvent plus complexe.

Comment modéliser l’imperfection de l’information ?

Prenons un exemple, la source 1 estime qu’il y a autant de chances pour chacune des hypothèse et la source 2 estime qu’elle ne sait pas qui est le coupable. En théorie de probabilité classique, Bullit décrirai ses probabilités de culpabilité comme cela :

\[ p_1(\{A\}) = p_1(\{B\}) = p_1(\{C\}) = \frac{1}{3} \]

\[ p_2(\{A\}) = p_2(\{B\}) = p_2(\{C\}) = \frac{1}{3} \]

Les deux avis sont différents mais sont modélisés de la même manière. Heureusement Bullit connait la théorie des fonctions de croyances et il possède des outils pour décrire plus finement la situation. Il va pouvoir décrire l’équiprobabilité annoncée par la source 1 et l’ignorance de la source 2.

\[ m_1(\{A\}) = m_1(\{B\}) = m_1(\{C\}) = \frac{1}{3} \]

\[ m_2(\{A, B, C \}) = 1 \]

Bullit vient de décrire les fonctions de masse de croyance, associés à chacune des sources. Une fonction de masse de croyance est l’ensemble des parts de croyance que l’on accorde a chacune des hypothèses possible.

Ou de façon plus formelle, il s’agit d’une application \(m : 2^\Omega \rightarrow [0,1] \) telle que :

\[ \sum_{E \subseteq \Omega } m(E) = 1 \]

Avec \(m(E)\) la part de croyance qui soutient l’hypothèse \(E\). Dans notre cas les fonctions de masse de croyance peuvent s’écrire ainsi :

Hypothèse {A} {B} {C} {A, B} {A, C} {B, C} {A, B, C}
m1 0 1/3 1/3 1/3 0 0 0 0
m2 0 0 0 0 0 0 0 1

On peut lire cette notation ainsi :

  • \(m_1(∅)\) la masse de croyance attribuée par la source 1 à l’hypothèse nulle, c’est la contradiction.
  • \(m_1(\{B\})\) la masse de croyance attribuée par la source 1 à l’hypothèse « B est vrai ».
  • \(m_1(\{A, C\})\) la masse de croyance attribuée par la source 1 à l’hypothèse « A ou C est vrai ».
  • \(m_1(\{A, B, C\}) = m_1(\Omega) \) la masse de croyance attribuée par la source 1 à l’ignorance.

Un autre exemple, si les sources donnent des informations différentes :

Les deux sources d’information de Bullit.

Hypothèse {A} {B} {C} {A, B} {A, C} {B, C} {A, B, C}
m1 0 1 0 0 0 0 0 0
m2 0 0 0 0 0 0 1 0

Manipuler les sources et prendre une décision

Maintenant on sait décrire des informations de manière pratique mais comment prendre une décision ? On sépare généralement deux étapes, la manipulation des fonctions de masse de croyance et la prise de décision.

Premièrement Bullit n’a pas autant confiance dans toutes ses sources, la source 1 n’est pas très fiable. L’inspecteur décide d’appliquer ce qu’on appelle l’opération d’affaiblissement de la source, c’est à dire qu’on va donner du crédit à une source en fonction de sa fiabilité \(1-\alpha\) où \(\alpha\) est le coefficient d’amortissement.

\[^\alpha m(E) = (1-\alpha)m(E), \forall E \subset \Omega  \]
\[^\alpha m(\Omega) = (1-\alpha)m(\Omega) +  \alpha \]

Bullit va maintenant fusionner les 2 sources pour ne former qu’une seule fonction de masse de croyance à l’aide d’une combinaison disjonctive :

\[ m_1 \cup m_2 (E) = m_{1\cup 2}(E) = \sum_{E_1 \cup E_2 = E} m_1(E_1)m_2(E_2), \forall E \subseteq \Omega\]

Il possède maintenant une unique fonction de masse de croyance qui contient les informations combinées des deux sources.  Pour prendre une décision, l’inspecteur va choisir une stratégie « optimiste » et cherche quelle est hypothèse A, B ou C qui maximise la plausibilité, c’est à dire qui a le plus d’éléments dans la fonction de masse de croyance qui pourrait la supporter.

\[ pl(E) = \sum_{F \cap E \neq \emptyset} m(F), \forall E \subseteq \Omega \]

C’était un gros bloc mais Bullit a enfin tous les outils dont il a besoin pour résoudre son enquête 😉

Application à la reconnaissance de gestes

On peut appliquer la méthode de décision utilisée par Bullit dans d’autres circonstances que la résolution d’une enquête. Dans une partie de mes travaux de thèse [lien] j’ai appliqué cette approche pour reconnaitre des gestes dans des vidéos 3D.

Les vidéos sur lesquelles j’ai travaillées sont comme des vidéos classiques mais au lieu d’enregistrer une information de couleur sur chaque pixel on obtient sa distance par rapport à la caméra.

Dans cette étude j’ai sélectionner 8 algorithmes de reconnaissance de gestes qui sont mes sources d’informations. Au lieu de prédire le coupable d’un crime, ces sources prédise l’action d’une vidéo. Pour rentrer un peu plus dans les détails, les algorithmes de reconnaissance de gestes sont en réalité 4 variations de l’algorithme de HON4D [Oreifej et al., CVPR 2016] et 4 variations de l’algorithme d’Actionlet [Wang et al., CVPR 2012]. Ces algorithmes ont été sélectionnés dans l’état de l’art car ils proposent des descripteurs de natures différentes. Le HON4D est un descripteur global se basant sur les cartes de profondeur alors que les Actionlet sont des descripteurs locaux se basant sur les zones d’intérêt autour de certains joints du squelette. Les variations sur ces algorithmes sont l’utilisation de 4 classifieurs différents : arbre de décision, random forest, classifieur bayésien naïf et SVM.

Les sources reconnaissent l’action à partir de la vidéo

Les fonctions de masse de croyances sont construites en se basant sur la sortie du classifieur qui vote pour l’hypothèse associée. Ce vote est pondéré par à l’aide d’un critère se basant sur la variation intra-classe de l’action reconnue et sur la distance (dans le jeu d’apprentissage) du descripteur de la vidéo au centre de la classe dans l’espace des descripteurs. Une opération d’amortissement est aussi effectué en fonction des performances sur le jeu d’apprentissage.

Pour prendre une décision j’ai utiliser comparer plusieurs stratégies de combinaison de l’information. Le vote majoritaire, le vote pondéré selon plusieurs critères et l’approche par fonction de croyance ont été comparés. Sur l’ensemble des test, l’approche par fonctions de croyances est globalement la meilleure stratégie mais cela n’est pas vraiment significatif. Cette approche est cependant robuste à la présence de mauvaises sources d’informations, relativement aux autres sources.

Le principal apport de ces travaux réside surtout dans la proposition d’utiliser conflit comme un critère de rejet. Plusieurs définitions du conflit ont été étudiées. Cela revient à dire que si une décision n’est pas assez crédible car les sources sont « trop en désaccord » par rapport à un seuil, alors la décision finale, c’est à dire l’action retournée, n’est pas pertinente. On préfère alors ne pas prendre de décision, ne pas reconnaitre le geste, plutôt de prendre un risque trop important de se trompé.

Influence du taux de rejet sur la précision du système. Tout droits réservés – All right reserved (Alexandre Perez, 2016, AUSY Expertise et Recherche, ETIS CNRS UMR 8051)

 

Sources

Dans ce billet je suis passé rapidement sur certains points, voir je n’en ai pas parlé. Je mets donc les sources pour aller plus loin.

2 réflexions au sujet de « Prendre une décision à l’aide des fonctions de croyances »

  1. Ping : Ma soutenance de thèse ! – Alexandre's blog

  2. Ping : Un moteur de recherche pour modèle 3D – Alexandre's blog

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée.