Réseaux bayésiens: les formules logiques perdent du poids

Publié par Redbran le 30/08/2016 à 12:00
Source: CNRS-INS2I
...
Restez toujours informé: suivez-nous sur Google Actualités (icone ☆)

ECAI est la conférence européenne de référence sur l'intelligence artificielle. L'opportunité de découvrir quelques aspects de ce vaste domaine de recherche. Dans ce premier focus, nous découvrons une avancée en compilation de réseaux bayésiens, des représentations informatiques aux multiples applications. Cette amélioration se traduit par une transformation du réseau (Un réseau informatique est un ensemble d'équipements reliés entre eux pour échanger des...) bayésien en une formule logique (La logique (du grec logikê, dérivé de logos (λόγος),...) pondérée.

Suscitant une littérature scientifique abondante depuis plus de quarante ans, les réseaux bayésiens constituent un des succès importants de l'intelligence artificielle (L'intelligence artificielle ou informatique cognitive est la « recherche de moyens...), avec des applications dans de multiples domaines, tels que la biologie (La biologie, appelée couramment la « bio », est la science du vivant....), la bioinformatique, la médecine (La médecine (du latin medicus, « qui guérit ») est la science et la...), le traitement d'images, les réseaux sociaux et l'analyse financière (Couramment, l'analyse financière est prise au sens d'analyse fondamentale d'une entreprise soit...).


Les réseaux bayésiens sont des graphes orientés, c'est-à-dire des représentations à base de points (des noeuds) et de flèches (des arcs) les reliant. La figure d'exemple ci-dessus présente un réseau bayésien. Les noeuds d'un réseau bayésien représentent des variables aléatoires. Il y en a quatre sur l'exemple (Nuageux, Arrosage, Pluie et Gazon mouillé) et ces variables prennent ici des valeurs binaires (1 ou 0). Le graphe est orienté car les arcs ont une flèche, chaque arc exprime une influence directe de la variable d'origine sur la variable qui est à l'extrémité de la flèche. Ainsi, le fait que le temps soit nuageux a une influence sur le fait que l'arrosage automatique (L'automatique fait partie des sciences de l'ingénieur. Cette discipline traite de la...) se déclenche ou pas. Sur l'exemple, Arrosage et Pluie sont les "parents" de Gazon mouillé.

La force des réseaux bayésiens est qu'ils permettent de représenter des distributions de probabilité de façon concise, c'est-à-dire sans avoir besoin (Les besoins se situent au niveau de l'interaction entre l'individu et l'environnement. Il est...) de préciser explicitement la probabilité de chaque événement. Pour cela, chaque noeud est associé à une distribution de probabilité (donnée ici par une table) qui indique comment la probabilité qu'une variable prenne une certaine valeur dépend des valeurs prises par ses variables parents. Dans notre exemple, la table de probabilité conditionnelle (La notion de probabilité conditionnelle permet de tenir compte dans une prévision d'une...) associée à la variable Arrosage indique que la probabilité que l'arrosage se mette en route (A=1) quand le temps est nuageux (N=1) vaut 0,1.

Parmi les opérations fondamentales à réaliser à partir d'un réseau bayésien figurent le calcul de la probabilité d'un événement donné et le calcul d'une explication la plus probable: étant donné un événement, trouver une affectation de valeurs aux variables restantes, ayant une probabilité maximale. Sur l'exemple précédent, on pourrait vouloir calculer la probabilité que le gazon soit mouillé et que l'arrosage automatique ne se soit pas mis en route. Ayant observé que le temps n'est pas nuageux et que le gazon est mouillé, on pourrait aussi vouloir calculer la probabilité de l'explication la plus probable (L'arrosage s'est-il mis en route ? A-t-il plu ?). Toutefois, ces opérations sont, en général, difficiles à calculer.

Afin de pallier cette complexité calculatoire, une approche consiste à "compiler" l'information contenue dans le réseau bayésien en un circuit arithmétique (L'arithmétique est une branche des mathématiques qui comprend la partie de la...). Pour cela, le réseau bayésien est d'abord traduit en une formule logique pondérée, les poids permettant de représenter les distributions conditionnelles du réseau. Cette formule logique est ensuite compilée en un circuit arithmétique, représentation compacte d'une expression arithmétique liant des nombres et des variables, et utilisant les opérations d'addition (L'addition est une opération élémentaire, permettant notamment de décrire la...) et de multiplication (La multiplication est l'une des quatre opérations de l'arithmétique élémentaire...). La structure d'un circuit arithmétique permet ainsi de traiter beaucoup plus rapidement les opérations précédentes.

La contribution de l'article "An Improved CNF Encoding Scheme for Probabilistic Inference" d'Anicet Bart[1], Frédéric Koriche [2], Jean-Marie Lagniez [2] et Pierre Marquis [2], est une nouvelle méthode de transformation (prouvée correcte) d'un réseau bayésien en une formule logique, dans laquelle les variables (et leurs négations) ont des poids. En considérant (entre autres choses) un poids par table de façon implicite, les formules obtenues portent sur des nombres de variables plus petits et sont plus concises que celles obtenues en utilisant les méthodes de transformation qui existaient jusqu'ici. Expérimentalement, elles conduisent à des circuits arithmétiques dont les tailles sont souvent bien plus petites.

Notes:
[1] Laboratoire d'Informatique de Nantes Atlantique (LINA - CNRS/Université de Nantes/École des Mines de Nantes)
[2] Centre de Recherche en Informatique de Lens (CRIL - CNRS/Université de l'Artois)
Page générée en 0.185 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
A propos - Informations légales | Partenaire: HD-Numérique
Version anglaise | Version allemande | Version espagnole | Version portugaise