Réseaux bayésiens
Les réseaux bayésiens sont le fruit de nombreuses recherches effectuées dans les années 80 par Pearl [Pea86]. Ils constituent l’un des formalismes les plus complets et les plus cohérents pour la représentation, l’acquisition et l’utilisation de la connaissance.
Ils représentent un modèle graphique spécifique où la structure graphique est un graphe acyclique direct (DAG). En effet, cette structure traduit efficacement les relations d’indépendances entre les variables permettant une compréhension et un accès direct à la structure. C’est ainsi qu’une correspondance entre la structure graphique et la structure probabiliste associée apparaît, facilitant le traitement et la résolution de certains problèmes théoriques.
Dans la modélisation probabiliste, les graphes permettent d’une part de fournir un moyen convenable d’exprimer les hypothèses, d’autre part de faciliter la représentation de la probabilité jointe et de réaliser des inférences à partir d’observations.
Méthodes de propagation probabiliste
Le processus de propagation se réduit à un processus de marginalisation de la distribution de probabilité jointe. Cependant le problème ne réside pas au niveau du calcul mais plutôt dans son efficacité. La méthode de calcul devient de plus en plus inefficace au fur et à mesure que le nombre de variables augmente. En effet, si nous disposons de n variables binaires, le calcul de la distribution de probabilité marginale nécessitera un temps de l’ordre de O(2n), ce qui donne un aspect de non-faisabilité à cette méthode.
La solution jugée efficace et pertinente jusqu’à présent est celle qui permet d’exploiter la structure d’indépendance des variables du modèle probabiliste considéré. Ainsi, le calcul de la distribution de probabilité jointe globale se réduit à une suite de calculs de probabilités locales simple à effectuer.
Nous décrivons dans la section suivante différents algorithmes de propagation dans les réseaux bayésiens [Pea88],[Dl93],[Lau96],[MWJ99]. Ces algorithmes d’inférence peuvent être classés en deux catégories principales :
Algorithmes d’inférence exacte : l’algorithme fondamental de propagation exacte, introduit par [KP83], est celui des messages locaux. Il consiste en une actualisation, à tout moment, des probabilités marginales, par transmission de messages entre variables voisines dans le graphe d’indépendance. Cet algorithme ne fonctionne de manière exacte que lorsque le réseau possède une structure d’arbre.
Par ailleurs, il existe des adaptations de cette méthode qui permettent d’utiliser les messages locaux même lorsque nous ne sommes pas en présence d’une structure arborescente. Dans ce cas, nous citons l’algorithme Loop CutSet Conditioning qui a été introduit par [Pea86]. Dans cette méthode, les liens du réseau sont modifiés en instanciant un certain sous ensemble de variables appelé l’ensemble de coupe (Loop CutSet). Dans le réseau résultant, l’inférence est effectuée en utilisant l’algorithme des messages locaux.
Cependant, dans le cas de réseaux à multiples connexions, c’est à dire en présence de boucles, il est préférable d’utiliser les méthodes approchées qui dérivent de cet algorithme à savoir loopy belief propagation voir [MWJ99].
Il existe aussi divers algorithmes de propagation qui opèrent sur les graphes indirects, parmi lesquels nous citons [Lau96]. Le principe de cet algorithme consiste à transformer le graphe initial en un arbre de jonction où les variables du graphe sont représentées par des clusters d’où l’appellation de l’algorithme clustering algorithm. Les messages sont transmis entre les clusters permettant le calcul des distributions de probabilités marginales. Cet algorithme s’applique pour toute structure de DAG contrairement à la méthode des messages locaux.
Algorithmes approchés : Dans les modèles probabilistes denses (nombre de variables très grand), l’inférence exacte est souvent inefficace et parfois impossible, dans le sens où le temps de calcul augmente d’une manière exponentielle par rapport à la taille du problème. Dans ce cas, les techniques d’inférence approchées proposent des solutions alternatives afin de remédier à ce problème. Parmi ces techniques, nous citons sampling methods (Monte Carlo) [CC90], dont les applications sont variées à savoir la synthèse d’image, la robotique, etc. Les méthodes variationnelles, basées sur un ensemble de techniques d’optimisation, permettent de transformer le problème d’inférence initial en un problème d’optimisation réalisable.
Inférence dans les réseaux uni-connexion
Dans cette section, nous présentons un algorithme de propagation de l’évidence dans les réseaux bayésiens de structure arborescente polyarbre voir [PS91]. Dans cet algorithme, l’arrivée d’une nouvelle information (evidence) est considérée comme une perturbation qui se propage en parallèle à travers différents processeurs dans le réseau.
Cette propagation est réalisée par la transmission de messages locaux entre les variables les plus proches. La communication locale entre les variables est basée sur deux types de messages, appelés λ-message et ρ-message circulant respectivement des nœuds parents aux nœuds enfants et vice versa.
Comme nous l’avons déja défini dans un polyarbre deux nœuds sont liés par un chemin unique, l’avantage d’une telle structure est que tout nœud A ∈ V peut diviser le graphe initial G en deux sous-graphes disconnectés :
GU : Constitue l’ensemble des nœuds accessibles à partir des antécédents directs (parents) U du nœud A,
GY : Constitue l’ensemble des nœuds accessibles à partir des descendants directs (enfants) Y du nœud A. C’est à dire le sous-arbre de racine A.
La propagation de l’évidence est alors effectuée en combinant les informations issues des différents sous-graphes par l’intermédiaire de flux de messages circulant d’un sous graphe à un autre.
Inférence dans les réseaux multi-connexions
L’algorithme présenté précédemment ne s’applique qu’aux réseaux uni-connexion (ou polyarbres). En effet, il a été démontré dans [Pea88], que cet algorithme ne donne pas de résultats satisfaisants pour les réseaux multi-connexions. En revanche, une méthode plus générale a été établie afin de résoudre le problème de l’inférence exacte dans les réseaux bayésiens, connue sous le nom de propagation probabiliste dans les arbres de jonction. Elle a été développée par [LS88] et améliorée par [Jen96], comme elle est le noyau de certains logiciels de propagation tel que HUGIN.
Dans cette méthode, la structure de graphe du réseau bayésien n’est pas utilisée directement mais par contre une structure secondaire est employée. Celle-ci est bien adaptée aux calculs, que le réseau bayéien d’origine. Le principe de la méthode de l’arbre de jonction consiste à élaborer une représentation graphique, qui dérive du réseau bayésien initial, appelée arbre de jonction et notée par J T [Jen96].
Toutefois, les deux méthodes de calcul (celle de Pearl et celle jensen) ont été unifiées en adaptant l’arbre de jonction pour l’algorithme d’inférence dans les polyarbres.
Table des matières
Introduction Générale
I Principes des Réseaux Causaux
1 Réseaux Probabilistes
1.1 Introduction
1.2 Fondements théoriques des probabilités
1.2.1 Loi de probabilité
1.2.2 Probabilité conditionnelle et indépendance
1.2.3 Formule de Bayes
1.3 Notions de base sur les graphes
1.3.1 Propriétés des graphes orientés
1.3.2 Types de graphes orientés
1.4 Indépendance conditionnelle dans les réseaux causaux
1.4.1 Circulation de l’information dans les DAGs
1.4.2 Critère de d-séparation
1.5 Réseaux bayésiens
1.5.1 Définition d’un réseau bayésien
1.5.2 Règle de chaînage probabiliste
1.5.3 Spécification d’un réseau bayésien
1.6 Principe de l’inférence probabiliste
1.6.1 Notion de l’évidence (ou de l’observation)
1.6.2 Méthodes de propagation probabiliste
1.7 Inférence dans les réseaux uni-connexion
1.7.1 Partitionnement de l’évidence
1.7.2 Equations fondamentales
1.7.3 Algorithme d’inférence
1.8 Inférence dans les réseaux multi-connexions
1.8.1 Génération de l’arbre de jonction
1.8.2 Processus de propagation
1.9 Conclusion
2 Réseaux possibilistes
2.1 Introduction
2.2 Principe de la théorie des possibilités
2.2.1 Distribution de possibilité
2.2.2 Mesure de possibilité et Mesure de nécessité
2.2.3 Conditionnement possibiliste
2.3 Définition d’un réseau possibiliste
2.3.1 Règles de chaînage
2.4 Indépendance dans les réseaux possibilistes
2.4.1 Indépendance qualitative
2.4.2 Indépendance causale possibiliste
2.5 Inférence dans les réseaux possibilistes
2.5.1 Propagation basée sur le produit
2.5.2 Propagation basée sur le minimum
2.6 Conclusion
II Adaptation possibiliste pour la fusion d’informations incertaines
3 Fusion en théorie des possibilités
3.1 Introduction
3.2 Principe de la logique possibiliste
3.3 Caractéristiques des opérateurs de fusion
3.4 Mode de fusion conjonctive
3.5 Normalisation vue par la fusion conjonctive
3.5.1 Description graphique de la fusion conjonctive
3.5.2 Description graphique de l’opération de normalisation
3.6 Mode de fusion disjonctive
3.7 Mode de fusion avec priorités inégales
3.7.1 Fusion adaptative
3.7.2 Fusion avec priorité
3.8 Fusion de bases de connaissances
3.8.1 Fusion syntaxique
3.8.2 Fusion sémantique
3.9 Conclusion
4 Nouvelle approche pour la fusion possibiliste
4.1 Introduction
4.2 Concepts de base de la théorie des possibilités
4.2.1 Distributions de possibilités et mesures de possibilités
4.2.2 Réseaux quantitatifs possibilistes
4.3 Fusion conjonctive basée sur le produit
4.4 Passage d’une base possibiliste à un réseau possibiliste
4.4.1 Représentation logique d’un graphe
4.4.2 Représentation graphique d’une base
4.5 Fusion de réseaux possibilistes de structures identiques
4.6 Fusion de réseaux U-acycliques
4.6.1 Ajouts de nœuds
4.6.2 Ajout d’arcs
4.7 Calcul de la fusion U-acyclique
4.7.1 Procédure de fusion
4.7.2 Fiabilité et modes de combinaison
4.7.3 Exemple d’application en robotique
4.8 Conclusion
5 Fusion cyclique de réseaux possibilistes
5.1 Introduction
5.2 Fusion préliminaire
5.3 Processus de décomposition
5.4 Procédure de fusion
5.5 Conclusion
6 Normalisation dans les réseaux possibilistes
6.1 Introduction
6.2 Principe de la normalisation quantitative
6.3 De la sous-normalisation locale à la sous-normalisation globale
6.3.1 Méthode d’élimination de variables
6.4 Restauration de la normalisation
6.4.1 Normalisation de variables racines
6.4.2 Normalisation de variables à un seul parent
6.4.3 Normalisation de variables à plusieurs parents
6.4.4 Procédure de normalisation
6.5 Conclusion
7 Mise en Oeuvre et Evaluations
7.1 Introduction
7.2 Etude expérimentale
7.2.1 Paramètres d’évaluations
7.2.2 Résultats d’évaluations des algorithmes de fusion
7.2.3 Résultats d’évaluations de l’algorithme de normalisation
7.3 Outil graphique de fusion possibiliste
7.3.1 Structure du réseau
7.3.2 Quantification du réseau
7.3.3 Processus de fusion
7.3.4 Processus de normalisation
7.3.5 Processus d’inférence
7.4 Conclusion
Conclusion
A Procédures implémentées
A.1 Structures de données
A.2 Principaux programmes
A.2.1 Structure d’un réseau possibiliste
A.2.2 Procédures de fusion de graphes acycliques
A.3 Procédures de fusion de graphes cycliques
A.4 Procédures de restauration de la normalisation
Bibliographie
