Publié par
Il y a 2 années · 11 minutes · Data

Une Introduction aux Modèles Graphiques avec Figaro

Les modèles graphiques sont un mélange de théorie des probabilités et de théorie des graphes. Ensemble, ces deux disciplines forment un framework qui permet de représenter une multitude de problèmes, tels les systèmes de diagnostics médicaux, les problèmes de reconnaissance du langage, ceux de tracking d’objets ou encore de manière plus générale les systèmes d’aide à la décision. Nous allons voir dans cette série d’articles quelques concepts de base ainsi que la manière de les appliquer concrètement à l’aide de Figaro, une bibliothèque Scala qui permet de simplifier la spécification de tels modèles et ainsi laisser libre court à l’imagination du modeleur.

Une description succincte

Selon Wikipédia :

Un modèle graphique est un graphe orienté ou non orienté, c’est-à-dire un ensemble, les « sommets », et des liens entre les sommets, les « arêtes ». Chaque sommet représente une variable aléatoire et chaque arête représente une dépendance de ces variables1.

Deux exemples importants de modèles graphiques sont les réseaux bayésiens et les champs aléatoires de Markov1 .

Dans le cadre de ce premier article, nous utiliserons un exemple de réseau bayésien, pour faire connaissance avec la bibliothèque Figaro. Nous en profiterons pour expliquer quelques notions au fil de l’eau, l’idée étant de vous faire coder un exemple concret, une sorte de HelloWorld de l’Intelligence Artificielle, afin d’apprendre en s’amusant.

Learning By Doing

Nous allons traiter le problème de l’Alarme, un grand classique en Intelligence Artificielle.
Le problème est le suivant :

Je suis résidant sur la côte ouest des Etats-Unis, où les tremblements de terre et les cambriolages peuvent se produire : il s’agit de deux phénomènes qui peuvent déclencher l’alarme de mon domicile.
Je suis au travail quand je reçois un appel de mon voisin John pour me prévenir qu’il a entendu mon alarme sonner.

Quelle est la probabilité d’un cambriolage ?

Je cours donc à ma voiture en pensant qu’il s’agit peut être d’un cambriolage.
En allumant la radio j’entends aux infos qu’il y a eu un tremblement de terre près de chez moi.

Quelle est la probabilité que ce soit toujours un cambriolage ?

Figaro

Figaro est un langage de programmation probabiliste qui aide dans le développement de modèles probabilistes complexes. On peut y trouver toute une série d’algorithmes d’inférences déjà implémentés.  En outre, les modèles Figaro sont des structures de données dans le langage de programmation Scala, qui est interopérable avec Java, et peuvent être construits, manipulés et utilisés directement dans un programme Scala ou Java.

Figaro est gratuit et est publié sous une licence open-source.

Installation

Il existe plusieurs manière d’utiliser Figaro, ce peut être via un shell scala ou encore sous forme d’application.

Pour plus de détails : https://github.com/p2t2/figaro

Pour une utilisation shell

La démarche est relativement simple, il suffit simplement d’ajouter le jar Figaro au classpath de scala à son lancement. Vous pouvez télécharger la dernière version du jar à l’adresse suivante (Section Download)  ou reconstruire à partir des sources (GitHub)

Pour vous simplifier la tâche, je vous ai écrit un petit script bash qui s’occupe d’aller chercher la version du jar indiqué et de vous créer un alias pour lancer un shell scala avec le bon classpath.

Une fois le fichier précédent téléchargé, il suffit de se mettre dans le même répertoire et d’exécuter les commandes suivantes :

chmod +x figaro-setup.sh
./figaro-setup.sh --dir '.' --version '3.3.0.0-2.11'
source ~/.bashrc

Si vous avez choisi de créer l’alias vous pourrez ainsi lancer un shell scala avec les bonnes dépendances, comme suit :

figaro-shell

Pour créer son application

Vous trouverez l’exemple de l’Alarme implémenté sous forme d’une petite application sur le GitHub de l’article.
Il s’agit d’un exemple assez simple, mais nous verrons dans un prochain article qu’il est possible d’utiliser des concepts objets afin de représenter des modèles plus complexes.

Passons à la pratique

Nous souhaitons comprendre/étudier un phénomène, celui du problème de l’Alarme.

Nous devons donc avoir une idée des variables en jeu et de leurs interactions. Nous pouvons donc adopter une approche type Business-Driven ou Expert-Driven, en d’autre mots nous n’avons pas connaissance du domaine d’étude et nous allons devoir collaborer avec un « expert » du domaine (il est à noter que la littérature peut jouer le rôle d’expert et que parfois le bon sens et l’expérience permet tout simplement d’aboutir à une première version du modèle, qui pourra être raffiné avec des connaissances plus spécifiques par la suite).

Dans notre cas, nous pouvons déduire les relations entre les variables par nous même (la structure du graphe).
Mais quelles sont ces variables ?

La question « Quelle est la probabilité d’un cambriolage sachant que John a appelé et que les informations ont parlé d’un tremblement de terre ? » nous permet d’identifier nos protagonistes.
En effet nous aurons besoin de variables qui représentent :

  • Le fait que John ait appelé ou non (John)
  • Le fait que l’alarme ait sonné ou non (Alarm)
  • Le fait qu’il y ait eu un tremblement de terre ou non (Earthquake)
  • Le fait qu’il y ait eu un cambriolage ou non (Burglary)
  • Le fait que les informations aient parlé d’un tremblement de terre ou non (News)

Nous avons donc nos cinq variables qui peuvent chacune prendre deux valeurs (true ou false). On parlera de variables binaires, qui est un cas particulier de variables dites discrètes (qui prennent un nombre fini de valeurs possibles).

La question ci-dessus peut ainsi s’écrire en terme probabiliste comme suit : P(Burglary=true | John=true, News=true)  (se prononce « la probabilité que Burglary=true sachant que John=true et que News=true »). Il s’agit d’une probabilité conditionnelle.

Nous avons à présent identifié les nœuds de notre graphe, reste à trouver les relations entre chacun d’eux.

Nous savons que John appelle s’il entend l’alarme, il existe donc une relation d’implication Alarm => John.
Par ailleurs l’alarme se déclenche s’il y a un tremblement de terre ou un cambriolage donc Burglary => Alarm et Earthquake => Alarm.
Qui plus est, les informations parleront d’un tremblement de terre s’il a effectivement eu lieu, donc Earthquake => News

Donc si on résume, nous avons le graphe suivant :


Nous avons parlé de relation d’implication, en réalité il serait plus juste de parler de relation de dépendance. En effet, John dépend de Alarm, mais de quelle manière exactement ?

Ici, nous entrons dans la spécification du réseau bayésien. En effet dans un réseau bayésien, les nœuds sont des variables aléatoires et les arêtes les lois de probabilité caractérisant les liaisons entres ces variables.

Par exemple, sachant que l’alarme a sonné, on peut se dire que John appellera 7 fois sur 10, soit avec une probabilité de 0.7. À l’inverse, si l’alarme n’a pas sonné, il se peut qu’il appelle en croyant l’avoir entendu, mais avec une probabilité très faible, disons 0.01. Dans la pratique ces valeurs peuvent être déterminées à l’aide d’experts ou via des données.

Si on prend la variable Burglary, elle peut prendre deux modalités true ou false avec une certaine probabilité.
En probabilité, on appelle cela une variable de Bernoulli, qui prend la valeur 1 avec probabilité p et 0 avec probabilité 1-p (où p appartient à l’intervalle [0, 1] )

On a ainsi P(Burglary=true) = p
L’idée est alors de déterminer p.

Dans la pratique, si on adopte le paradigme bayésien, on mettrait une loi de probabilité sur p, dite loi a priori. Cette loi représente notre croyance avant de voir les données.
Dans le cas du tremblement de terre, nous pourrions simplement n’en avoir aucune idée et mettre une loi uniforme sur [0,1]. La loi uniforme dans sa version discrète correspond au fait que tout élément de mon ensemble à la même probabilité (1/6 pour chaque face, dans le cas d’un dé équilibré). La loi Uniforme sur [0,1] est la version continue de celle-là et correspond au fait que tout intervalle de même longueur inclus dans le support de la loi (ici [0,1]) a la même probabilité.
On parlerait alors de loi non-informative. Ou on pourrait aller voir des experts afin d’éliciter une loi qui représente leur croyance du phénomène. Par la suite, à l’aide de données sismiques, nous pourrions mettre à jour (bayes-rule) notre croyance (prior) et ainsi obtenir une nouvelle loi de probabilité (posterior).

Pour l’exercice nous supposerons connues ces différentes valeurs, nous avons donc à notre disposition les différentes lois a priori et les lois conditionnelles (Conditional Probability Distribution)

Lois a priori

Lois a priori

CPD

CPD

Comment doit-on lire ces tableaux ?

Prenons le dernier (Alarm) et décortiquons une ligne pour mieux comprendre.
Prenons la dernière ligne

Modèles Graphiques avec Figaro

Cela revient à dire que la probabilité que l’alarme sonne alors qu’il n’y a pas eu de cambriolage mais un tremblement de terre est de 0.1 (P(Alarm=true | Burglary=false, Earthquake=true) = 0.1)

Nous avons à présent toutes les cartes en mains pour passer à la pratique.

Un peu de Code

Vous trouverez l’ensemble du code sur le GitHub de l’article (sous forme d’application).

Pour le coté interactif nous utiliserons ici le shell scala (soit l’alias figaro-shell définit plus haut)

On lance donc le shell :

figaro-shell 

Quelques imports :

import com.cra.figaro.language._
import com.cra.figaro.library.compound._
import com.cra.figaro.algorithm.factored._

En Figaro, la notion de variable de Bernoulli est représentée par l’objet Flip.
Si on se réfère à la loi de Burglary (ci-dessus) il s’agit d’une loi de Bernoulli de paramètre p=0.1.
Soit en Figaro :

val burglary = Flip(0.01)

De même on aura :

val earthquake = Flip(0.0001)

Pour les distributions conditionnelles de probabilité Figaro met à notre disposition l’objet CPD.
On aura donc les définitions suivantes pour News, Alarm et John :

val news = CPD(earthquake,
  false -> Constant(false),
  true -> Flip(0.8))

val alarm = CPD(burglary, earthquake,
  (false, false) -> Flip(0.001),
  (false, true) -> Flip(0.1),
  (true, false) -> Flip(0.9),
  (true, true) -> Flip(0.99))

val john = CPD(alarm,
  false -> Flip(0.01),
  true -> Flip(0.7))

Nous venons de spécifier notre modèle, nous pouvons donc à présent l’utiliser pour poser des questions.

Par exemple, la première question que nous nous posions était :

Quel est la probabilité d’un cambriolage sachant que John a appelé ?

Pour se faire il faut spécifier au modèle que nous avons observé que John a appelé :

john.observe(true)

À présent, pour répondre à notre question, il nous faut l’aide d’un algorithme d’inférence, qui va se charger de calculer la probabilité demandée.
Nous utiliserons ici l’algorithme VariableElimination qui est un algorithme exact (pour des variables discrètes).

val probBurglaryGivenJohn = VariableElimination.probability(burglary, true)
println(s"Probability of burglary given John's call: ${probBurglaryGivenJohn}")

Pour répondre à notre deuxième question :

Quel est la probabilité d’un cambriolage sachant que John a appelé et que les informations ont parlé d’un tremblement de terre ?

 

Il suffit simplement de spécifier au modèle que l’on a aussi observé news=true :

news.observe(true)


Et de poser à nouveau notre question :

val probBurglaryGivenJohnNews = VariableElimination.probability(burglary, true)
println(s"Probability of burglary given John's call and Earthquake News: ${probBurglaryGivenJohnNews}")

Conclusion

Vous avez vu au travers de cet article quelques notions de base des modèles graphiques et comment les implémenter en Figaro. Nous nous sommes contentés de traiter le cas de variables discrètes.

Nous verrons dans de prochains articles le cas des variables continues, et comment profiter de la programmation orientée objet pour pouvoir traiter facilement (de manière plus lisible) des modèles plus complexes. Nous verrons également comment représenter des modèles dynamiques et essayerons de l’appliquer à un cas réel. Nous aborderons aussi dans un article dédié à cet effet les différents algorithmes d’inférence à notre disposition et quelques recommandations quant à leur utilisation. Nous consacrerons également un numéro aux systèmes d’aide à la décision.

Quelques Livres

  • Avi Pfeffer, « Practical Probabilistic Programming », Manning 2015

La publication aura lieu en décembre 2015, une MEAP est disponible sur leur site, pour l’avoir lu le livre est très bien construit et accompagne parfaitement dans la prise en main du langage et des notions. La partie théorique est un peu légère et je recommenderais plus un des livres suivants pour un approfondissement :

  • Daphne Koller and Nir Friedman, « Probabilistic graphical models: principles and techniques », MIT Press 2009
  • Uffe B. Kjærulff and Anders L. Madsen, « Bayesian Networks and Influence Diagrams », Springer 2008
  • J. Pearl. « Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. » Morgan Kaufmann. 1988.
  • James O. Berger, « Statistical Decision Theory and Bayesian Analysis », Springer 1985

Il en existe évidement une multitude d’autre, mais dont je n’ai pas encore pris assez connaissance pour me permettre de les recommander.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *