Critère de d-séparation
La séparation dans les graphes orientés est plus complexe que dans les graphes non orientés. En effet, il ne suffit pas de savoir si au moins un nœud de tout chemin entre X et Y appartient à Z, il faut aussi que ce nœud vérifie des conditions supplémentaires, apportées par les orientations des arcs. Ainsi, les types de connexions existantes permettent de déterminer l’ensemble des nœuds concernés par la mise à jour lors d’une quelconque observation. En d’autres termes, ils représentent les indépendances conditionnelles à travers la structure graphique du DAG, c’est ce qu’on appelle le critère de d-séparation. Ce critère est utilisé pour répondre aux requêtes de la forme : « la variable A et la variable B sont-elles indépendantes étant donnée la variable C ».
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.
Spécification d’un réseau bayésien
La construction d’un réseau bayésien modélisant un domaine d’application nécessite trois phases distinctes :
Phase symbolique : elle reflète les relations d’influence pouvant exister entre les variables, à travers une modélisation graphique du problème donné.
Phase probabiliste : elle spécifie le modèle graphique par la représentation d’une distribution jointe sur l’ensemble des variables. En effet, cette représentation détermine les distributions de probabilités locales (a priori et conditionnelles) d’une variable connaissant uniquement les variables ayant une influence directe sur elle.
Phase numérique : elle consiste en l’évaluation numérique des distributions de probabilités conditionnelles. Autrement dit, c’est la spécification de l’ensemble des distributions de probabilités d’une variable, pour chacune de ses valeurs possibles, connaissant les valeurs de ses parents. Ces probabilités sont souvent acquises par un expert du domaine modélisé, ou apprises à partir d’une base d’exemples.
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 algorithme. 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 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 Œuvre 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
