Réseaux Bayésiens: DAG, PDAG et CPDAG

C’est un petit résumé de lecture concernant le sujet de l’apprentissage de la structure de réseaux Bayésiens (RB) dans l’espace des classes d’équivalence de Markov.  Il vise aux lecteurs qui sont familiers des méthodes basées sur le score et la recherche.  Les trois mots clés envisagés sont (1) DAG (Directed Acycle Graph: graphe dirigé sans circuit), (2) PDAG (Partially Directed Acycle Graph: graphe partiellement dirigé sans circuit) et (3) CPDAG (Completed Partially Directed Acycle Graph: graphe complété partiellement dirigé sans circuit). Le but de ce résumé est de comprendre la différence entre ces termes. Le point important à retenir est le principe de la classe d’équivalence de Markov.

Comme leur nom déjà indiqué, il s’agit de la même famille de DAG. C’est un groupe de termes bien connus dans l’apprentissage de la structure de réseaux Bayésiens (RB). En général, la différence entre eux est la règle (la restriction) qui détermine l’orientation des arcs de chaque type de graphe:

1) DAG : seulement des arcs dirigés

2) PDAG: arcs non-dirigés et dirigés

3) CPDAG: arcs non-dirigés et dirigés respectant la V-structure  X -> Y <- Z

Le dernier nous intéresse. C’est le concept qui représente la classe d’équivalence de Markov. Elle consiste à définir une graphe unique (aussi connu sous le nom: graphe essentiel) qui représente tous les graphes dit “équivalents“. Deux graphes sont équivalents si seulement s’ils ont même squelette et v-structure (arcs essentiels). Les arcs essentiels sont les arcs que leurs flèches ne pourront pas être inversés.

En effet, étant donné trois variables X, Y, Z. Supposons qu’on a quatre types de relations suivantes:

(a) X -> Y -> Z         Pa(X,Y,Z) = P(X) * P(Y|X) * P(Z|Y) 

(b) X <- Y -> Z         Pb(X,Y,Z) = P(X|Y) * P(Y) * P(Z|Y) 

(c) X <- Y <- Z         Pc(X,Y,Z) = P(X|Y) * P(Y|Z) * P(Z)

(d) X -> Y <- Z         Pd(X,Y,Z) = P(Y|X,Y) * P(X) * P(Y)

D’après la définition d’une probabilité conditionnelle, on a:

 

P(X|Y) * P(Y) = P(Y|X) * P(X)
P(Z|Y) * P(Y) = P(Y|Z)  * P(Z)

donc,

Pa(X,Y,Z) = P(X) * P(Y|X) * P(Z|Y) 

= P(X|Y) * P(Y) * P(Z|Y) = Pb(X,Y,Z)

= P(X|Y) * P(Y|Z)  * P(Z) = Pc(X,Y,Z)

alors (a), (b), (c) sont équivalents. Pourtant, avec Pd(X,Y,Z), c’est P(Y|X,Y) qui ne peut pas se simplifier. Donc, (d) n’est pas équivalent par rapport aux trois autres.

 

Voilà, quelques explications pour mieux comprendre la différence entre DAG, PDAG et CPDAG.

 

Pour conclure, la motivation de la définition de CPDAG et le principe de la classe d’équivalence de Markov est:

(1) la réduction de l’espace de structures possibles:  En effet, il y a plusieurs structures qui représentent les mêmes relations d’indépendance conditionnelle. La classe d’équivalence permet d’optimiser la recherche en évitant des redondances de structure équivalentes. Par contre, puisque le taux de nombre de DAG et de nombre de CPDAG est 0.267, donc l’amélioration en terme d’efficacité de l’algorithme apprentissage de la structure est petite.

(2) la possibilité d’obtenir un optima global de la recherche de meilleures structures:  En effet, il y a plusieurs structures qui ont même score. La classe d’équivalence de ces structures pourrait éventuellement permettre de trouver plus facilement la meilleure structure.

Pourtant, il y a également de désavantages de la classe d’équivalence de Markov :

(1) il faudrait plus d’opérations pour vérifier si la structure représente la classe d’équivalence.

(3) il est possible d’avoir besoin d’une mesure d’évaluation plus compliquée si on ne peut pas utiliser le score équivalent.

(2) l’espace de CPDAG pourrait produire un autre optima local qu’il n’y a pas dans l’espace de DAG.

 

Ce résumé s’arrête ici. Le prochain sera l’algorithme pour la recherche dans l’espace CPDAG.

 

Je vous souhaite bon vent pour la suite et à très bientôt!

Tutu

 

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s