Algorithmique pour les Réseaux Bayésiens et leurs extensions

Rapporteurs : Marc Bouissou, EDF. R et DEvelyne Flandrin, Univ. Paris 5Eric Moulines, ENSTExaminateurs : Wenceslas Fernandez de La Vega, Univ. Paris-Sud Kamel Mekhnacha, INRIA Rhône Alpes Paul Munteanu, ESIEA Georges Oppenheim, Univ. Marne-la-ValléeThis thesis is designed to develope a new algorithm to compute marginal and conditional probabilities in bayesian networks. In chapter 1 we present the theory of bayesian networks. We introduce a new concept, the one of bayesian network of level two, which is a new key method to introduce our computation algorithm. In chapter 2, we present a graphical property called "D-separation" which allows to determine, for any couple of random variables, and any set of conditioning, if there is, or not, conditional independence. We also present results related to the computation of probability and conditional probabilities in the bayesian networks by using the properties of d-separation. In chapter 3 we give the presentation and the justification of one of the known algorithms of computation in the bayesian networks : the LS algorithm (Lauritzen and Spiegelhalter), based on the method of junction tree. In addition, after having presented the concept of proper covering sequencewith the running intersection property, we propose an algorithm in two versions (of which one is new) which allows to build a succession of parts of a bayesian network having this property. In chapter 4, we develope the successive restrictions algorithm which we propose for the computation of probabilities (in its first version) and of conditional probabilities (in its second version).Cette thèse est consacrée à la présentation d'un algorithme nouveau et à la formalisation et l'amélioration d'algorithmes existants pour le calcul des lois marginales et conditionnelles dans les réseaux bayésiens. Le chapitre 1 présente la théorie des réseaux bayésiens. Nous introduisons une nouvelle notion, celle de réseau bayésien de niveau deux, utile pour l'introduction de notre algorithme de calcul sur les réseaux bayésiens ; nous donnons également quelques résultats fondamentaux et nous situons dans notre formalisme un exemple d'école de réseau bayésien dit «Visite en Asie» .Dans le second chapitre, nous exposons une propriété graphique appelée «d-séparation» grâce à laquelle on peut déterminer, pour tout couple de variables aléatoires ou de groupes de variables, et tout ensemble de conditionnement, s'il y a nécessairement, ou non, indépendance conditionnelle. Nous présentons également dans ce chapitre des résultats concernant le calcul de probabilités ou probabilités conditionnelles dans les réseaux bayésiens en utilisant les propriétés de la d-séparation. Ces résultats, qui concernent des écritures à notre connaissance originales de la factorisation de la loi jointe et de la loi conditionnée d'une famille de variables aléatoires du réseau bayésien (en liaison avec la notion de réseau bayésien de niveau deux) doivent trouver leur utilité pour les réseaux bayésiens de grande taille.Le troisième chapitre donne la présentation détaillée et la justification d'un des algorithmes connus de calcul dans les réseaux bayésiens : il s'agit de l'algorithme LS (Lauritzen and Spigelhalter), basé sur la méthode de l'arbre de jonction. Pour notre part, après avoir présenté la notion de suite recouvrante propre possédant la propriété d'intersection courante, nous proposons un algorithme en deux versions (dont l'une est originale) qui permet de construire une suite de parties d'un réseau bayésien possédant cette propriété. Cette présentation est accompagnée d'exemples. Dans le chapitre 4, nous donnons une présentation détaillée de l'algorithme des restrictions successives que nous proposons pour le calcul de lois (dans sa première version), et de lois conditionnelles (dans sa deuxième version). Cela est présenté après l'introduction d'une nouvelle notion : il s'agit de la descendance proche. Nous présentons également une application de l'algorithme des restrictions successives sur l'exemple «Visite en Asie» présenté en chapitre 1, et nous comparons le nombre d'opérations élémentaires effectuées avec celui qui intervient dans l'application de l'algorithme LS sur le même exemple. Le gain de calcul qui, à la faveur de cet exemple, apparaît au profit de l'algorithme des restrictions successives, sera comme toujours, d'autant plus marqué que la taille des réseaux et le nombre de valeurs prises par les variables seront plus élevés. C'est ce qui justifie l'insertion de notre algorithme au seins de « ProBT » , un logiciel d'inférence probabiliste, réalisé et diffusé par l'équipe Laplace localisée dans le laboratoire Gravir à INRIA Rhône Alpes. En annexes nous rappelons les propriétés des graphes orientés sans circuits, les notions de base sur l'indépendance conditionnelle et l'équivalence de plusieurs définitions des réseaux bayésiens