Apprentissage de la structure de réseaux bayésiens

Jimmy Vandel

Directeurs de thèse : Brigitte Mangin & Simon de Givry

Apprentissage de la structure de réseaux bayésiens.Application aux données de génétique-génomique.

Motivation 1

Motivation biologique➢ Mesure pour un ensemble d'individus, l'activité de différents gènes

(par exemple le niveau d'expression)

Motivation

Motivation biologique➢ Mesure pour un ensemble d'individus, l'activité de différents gènes

(par exemple le niveau d'expression)

Régulation ?

Motivation

Motivation biologique

➢ Mesure pour un ensemble d'individus, l'activité de différents gènes(par exemple le niveau d'expression)

Objectif

Motivation

➢ Apprendre la structure d'un réseau de régulation de gènes (RRG)

3Motivation

➢ Les réseaux bayésiens discrets, une solution ?

Objectif ➢ Apprendre la structure d'un réseau de régulation de gènes (RRG)

3Motivation

• Modélisation de dépendances complexes (non-linéaires)

• Estimation aisée des paramètres pour des données complètes

• Modèle décomposable localement

• Prise en compte de la causalité entre certaines variables

3Motivation

• Causalité partielle due aux équivalents de Markov

• Données d'expression continues → discrétisation nécessaire

• Ne peut représenter des circuits → approches ensemblistes

• Complexité pour apprendre la structure

• Modélisation de dépendances complexes (non-linéaires)

• Estimation aisée des paramètres pour des données complètes

• Modèle décomposable localement

• Prise en compte de la causalité entre certaines variables

Plan de l'exposé :

1 – Apprentissage de la structure d'un réseau bayésien➢ Présentation des réseaux bayésiens

➢ État de l'art

➢ Nos propositions de nouveaux opérateurs locaux

2 – Application à la génétique-génomique➢ Introduction aux réseaux de régulation de gènes

➢ État de l'art

➢ Notre modélisation des données de génétique-génomique

➢ Application aux données d'Arabidopsis thaliana

Plan de l'exposé :

➢ État de l'art

Présentation des réseaux bayésiens (RB) 5

Les réseaux bayésiens

Secousse Effraction

Alarme

Appel à un voisin

Message radio

➢ Modèles graphiques probabilistes

• Graphe Dirigé Acyclique (DAG)

• Probabilités conditionnelles d'un ensemble de variables aléatoires Xp

Présentation des réseaux bayésiens (RB) 5

Les réseaux bayésiens

PG X i/Paij=i

➢ Modèles graphiques probabilistes

➢ Pour chaque variable on a

où : parents de

Secousse (S) Effraction (E)

Oui Oui 0.90 0.10

Oui Non 0.20 0.80

Non Oui 0.90 0.10

Non Non 0.01 0.99

P Alarme / S , E P ! Alarme / S , E

Secousse Effraction

Alarme

Appel à un voisin

Message radio

• Probabilités conditionnelles d'un ensemble de variables aléatoires

• Graphe Dirigé Acyclique (DAG)

PG X =∏i=1

pPG X i /Pa i➢ Distribution de probabilité jointe

État de l'art 6

Apprentissage de la structure

1 - Recherche des indépendances

2 - Méthodes à base de score

➢ Rechercher les indépendances conditionnelles à l'aide d'un test statistique• Test du chi-2• Rapport de vraisemblance• Information mutuelle

➢ Maximiser un score qui calcule la vraisemblance des données• Score BIC• Score BDe• Score fNML

Scores équivalents, pénalisés et décomposables

➢ Algorithmes de recherche locale

→ problème d'optimisation NP-dur (Chickering et al., 02)

→ nombre exponentiel de tests possibles→ sensibilité à la puissance du test, risque de propagation des erreurs

État de l'art 7

Recherches locales comparées

➢ Opérateurs élémentaires : - ajout d'un arc- suppression d'un arc- inversion d'un arc

➢ Voisinage d'un graphe : l'ensemble des graphes atteignables à partir de par l'application d'opérateurs élémentaires

État de l'art 7

➢ Stratégie de déplacement dans le voisinage

→ Concept algorithmique simple→ Peu de paramètres→ Bonnes performances en pratique

• Approches gloutonnes

État de l'art 7

→ GS, notre contribution SGS→ LAGD (Holland et al., 08)

→ GES (Chickering et al., 02)

➢ Stratégie de déplacement dans le voisinage

• Espace des DAG

• Espace des équivalents de Markov

→ Concept algorithmique simple→ Peu de paramètres→ Bonnes performances en pratique

➢ Espace de recherche

• Approches gloutonnes

État de l'art 8

Espace de recherche

Ensemble des graphes dirigés

État de l'art 8

Espace de recherche

État de l'art 8

Espace de recherche

État de l'art 8

Espace de recherche

État de l'art 8

Espace de recherche

Scores locauxScore global

État de l'art 9

Greedy Search (GS)

G1 G2 G 3

3 opérateurs classiques• Ajout d'un arc• Suppression d'un arc• Inversion d'un arc

État de l'art 9

G1 G 2 G 3

G1 G2 G 3

G1 G 2 G 3

G1 G2 G 3 G1 G2 G 3

G1 G2 G 3

Greedy Search (GS)Taille du voisinage : O p2

État de l'art

G1 G 2 G 3

G1 G2 G 3

G1 G 2 G 3

G1 G2 G 3 G1 G2 G 3

G1 G2 G 3

G1⊥G2

G1⊥G 3

G 2⊥G3

État de l'art

G1 G 2 G 3

G1 G2 G 3

G1 G 2 G 3

G1 G2 G 3 G1 G2 G 3

G1 G2 G 3

G1⊥G2

G1⊥G 3

G 2⊥G3

État de l'art

G1 G2 G 3

G1 G2 G 3G1 G2 G 3

État de l'art

G1 G2 G 3

G1 G2 G 3G1 G2 G 3

État de l'art

G1 G2 G 3

Nos propositions 10

Opérateur SWAP

→ échapper aux solutions de maximum local

Graphe courant

G1 G 2

G 3 G 3

Graphe optimal17 20

Nos propositions

Opérateur SWAP

G1 G 2

SuppressionG 1,G3 Ajout G2,G 3

Graphe courant

G1 G 2

G 3 G 3

Graphe optimal17 20

Nos propositions

Opérateur SWAP

G1 G 2

Graphe courant

G1 G 2

G 3 G 3

Graphe optimal17 207

Nos propositions

Opérateur SWAP

G1 G 2

Ajout G2,G 3 |G 1 SuppressionG 1,G3 |G 2

G1 G 2

Graphe courant

G1 G 2

G 3 G 3

Graphe optimal17 207

Nos propositions

Opérateur SWAP

SwapG 1,G 3,G 2

Graphe courant

G1 G 2

Graphe optimal

Taille du voisinage : Okp2avec le nombre maximum de parentsk

Nos propositions

Opérateur Itératif

SwapG 2,G 3,G 7?

G 2 G 3

Graphe courant

Nos propositions 11

Circuit {G3,G 4,G 6,G7}

Objectif : supprimer les circuits

G 2 G 3

Graphe courant

SwapG 2,G 3,G 7?

Nos propositions 11

Étape 1. Supprimer l'arc qui minimise le score local

G 2 G 3

Graphe courant

Circuit {G3,G 4,G 6,G7}SwapG 2,G 3,G 7?

Nos propositions 11

Amélioration du score ? Oui

G 2 G 3

Graphe courant

Nos propositions 11

Amélioration du score ?

Oui → OK !Non → Retour à l'étape1

Oui → Aucun circuit ?

G 2 G 3

Graphe courant

Nos propositions 11

Non → Continuer l'étape 2

Étape 2. Swapper cet arc

G 2 G 3

Graphe courant

Nos propositions 11

Étape 2. Swapper cet arc Amélioration du score ?

Oui → OK !Non → Retour à l'étape 1

G 2 G 3

Graphe courant

Nos propositions 11

Graphe courant

G 2 G 3

Non → Game Over !

Nos propositions 11

Graphe courant

G 2 G 3

Non → Game Over !

Nombre borné d'opérations :O kp avec le nombre maximum de parentsk

Nos propositions

Stochastic Greedy Search

G1 G2 G 3

➢ Greedy Search (GS)

Nos propositions 12

G1 G2 G 3

Nos propositions 12

G1 G2 G 3

G1 G 2 G 3

Nos propositions 12

G1 G2 G 3

???G1 G2 G 3

G1 G 2 G 3

➢ Stochastic Greedy Search (SGS)= GS + orientation aléatoire des arcs inversibles

→ Parcours d'équivalents de Markov différents à chaque répétition (r)

r=1r=2

Comparatifs 13

Comparatifs

➢ Données générées à partir de distributions de probabilité : 100 jeux de données (500 → 5 000 exemples)

➢ SGS (+SWAP+opérateurs itératifs) comparé à : - LAGD

➢ Nombre limité de parents : 5

➢ Pré-sélection de parents potentiels pour le réseau Pigs avec SGS Add Parent ,Cible 0

➢ 4 réseaux benchmarks

Alarm Insurance Hailfinder Pigs

Nb. de variables 37 27 56 441

Nb. d'arcs 46 52 66 592

Degré entrant 4 3 4 2

Comparatifs 14

Comparatifs : Scores atteints

➢ Comparaison des meilleurs scores BDeu atteints en moyenne sur les 100 jeux de données

Test de Wilcoxon 5%

500 5 000 500 5 000 500 5 000 500 5 000

SGS vs GES + + + + + + + -

SGS vs LAGD + + + + ~ + n/a n/a

LAGD vs GES + ~ + + + + n/a n/a

➢ SGS et LAGD : meilleur score atteint sur 10 répétitions (r=10)

Comparatifs 15

Comparatifs : Distances d'édition

500 5 000 500 5 000 500 5 000 500 5 000

SGS 11* 8 24* 10* 41 29* 32 41

LAGD 15 10 24* 16 47 39 n/a n/a

GES 11* 6* 25 15 39* 33 9* 0*

* meilleur résultat

➢ Comparaison des structures non-orientées via les distances d'édition moyennes sur les 100 jeux de données

Comparatifs 15

Comparatifs : Distances d'édition

500 5 000 500 5 000 500 5 000 500 5 000

SGS 11 9* 8 4* 24 24* 10 9* 41 40 29 26* 32 1* 41 2

LAGD 15 10 24* 16 47 39 n/a n/a

GES 11 6 25 15 39* 33 9 0*

* meilleur résultat

➢ Correction des v-structures couvertesG1 G 2

G1 G 2

➢ Comparaison des structures non-orientées via les distances d'édition moyennes sur les 100 jeux de données

Conclusions 16

Conclusions

➢ Nous avons proposé deux nouveaux opérateurs locaux pour l'apprentissage de structure de RB.

• Amélioration des scores atteints à l'aide de l'algorithme SGS• Les distances d'édition peuvent être améliorées à l'aide de

post-traitements

➔ New Local Move Operators for Learning the Structure of Bayesian Networks.ECAI'12 workshop, AIGM, Montpellier, 2012.

➔ New Local Move Operators for Bayesian Network Structure Learning.Workshop on Probabilistic Graphical Models, Spain, 2012.

Plan de l'exposé :

➢ État de l'art

Introduction aux réseaux de régulation 18

Régulation et polymorphisme

Introduction aux réseaux de régulation

➢ Mutations de l'ADN : en région codante → impacte la régulation

en région promotrice → impacte l'expression➢ Mutations de l'ADN : en région codante → impacte la régulation

en région promotrice → impacte l'expression➢ Données génétiques : un marqueur par gène (cas idéal)

➢ Mutations de l'ADN : en région codante → impacte la régulation

État de l'art

Apprentissage de RRG – Logiciels disponibles

Données d'expression seulesDonnées de génétique-génomique

➢ Modèles Graphiques Gaussiens (GMM)

➢ Réseaux bayésiens

➢ Corrélations partielles

➢ Forêts aléatoires

• ARACNE (Margolin et al., 06)• CLR (Faith et al., 07)• ParCorA (de la Fuente et al., 04)

• GENIE3 (Huynh-Thu et al., 10)

• GGMselect (Giraud et al., 09)• GeneNet (Schäfer et al., 05)• Paquet R Lars (régressions Lasso) (Meinshausen et al., 06) (Vignes et al., 11)• Paquet C glpk (sélecteur de Dantzig) (Candes et al., 07) (Vignes et al., 11)• SIMoNe (Chiquet et al., 09)

• Banjo (Hartemink, 05) (Vignes et al., 11) (Vandel et al., à paraître)• SCT (Chipman et al., 11)

Notre modélisation 20

Modélisation

Données d'expression E i={1,2 ,3 }E1 E 2 E3

Notre modélisation 20

Modélisation

Données d'expressionE1 E i={1,2 ,3 }

Données génétiques M i={ 0,1}

M 1 M 3

Notre modélisation

Modélisation

Données d'expression

Données génétiques M 2M 1 M 3

E1 E 2 E3 E i={1,2 ,3 }

M i={ 0,1}

→ Restrictions biologiques• Impose les arcs Mi → Mi+1• Interdit les arcs E → M

Notre modélisation

Modélisation

Données génétiques

E1 E 2 E3 E i={1,2 ,3 }

M i={ 0,1}

→ Effet cis : mutation en région promotrice du gène i (exemple : M1 et M3)• Impose l'arc Mi → Ei

M 2M 1 M 3

Notre modélisation

Modélisation

E1 E 2 E3 E i={1,2 ,3 }

M i={ 0,1}

M 2M 1 M 3

→ Effet trans : mutation dans la région codante du gène i (exemple : M2)• Interdit l'arc Mi → Ei

Notre modélisation

Modélisation

M 2M 1 M 3

E1 E 2 E3 Données d'expression

E i={1,2 ,3 }

M i={ 0,1}

Notre modélisation

Modélisation

M 2M 1 M 3

E i={1,2 ,3 }

M i={ 0,1}

➢ Discrétisation adaptative des données d'expression pour une interprétation visuelle

Notre modélisation

Modélisation

M 2M 1

E i={1,2 ,3 }

M i={ 0,1}

➢ Discrétisation adaptative des données d'expression pour une interprétation visuelle

Situation réellenb. de gènes nb. de marqueurs≠

Comparatifs

Génération des données

➢ Équation Différentielle Ordinaire (EDO)

dt= V i ∗∏ Z j∗

I jK ij

∗∏ Z k 1Ak

A kK ak

−k i E i E i

(Liu et al., 08)

➢ Données génétiques : populations générées par rétro-croisement avec CARTHAGENE

(Schiex et al., 01)

Comparatifs 21

Génération des données

50 réseaux Web50 (Mendes et al., 03) 15 réseaux DREAM (Pinna et al., 11)

1000 gènes100 → 999 individus

50 gènes50 → 500 individus

➢ Équation Différentielle Ordinaire (EDO)

dt= V i ∗∏ Z j∗

I jK ij

∗∏ Z k 1Ak

A kK ak

−k i E i E i

➢ Données génétiques : populations générées par rétro-croisement avec CARTHAGENE (Schiex et al., 01)

(Liu et al., 08)

Comparatifs 22

Réseaux Web50

➢ Réseaux bayésiens : GS (BDeu / BIC / fNML ), SCT➢ Modèle linéaire : Régressions Lasso , GGMselect , GeneNet , SIMoNe ➢ Corrélation de paires : CLR , ARACNE , ParCorA

Précision :VP

Sensibilité :VP

Précision

50 individus

Moyennes sur les 50 réseaux Web50 non-orientés

Précision

500 individus

Comparatifs 23

Réseaux DREAM

Courbes Précision-Sensibilité

➢ Réseaux bayésiens (GS score BDeu)➢ Régressions Lasso➢ Sélecteur de Dantzig

Réseau 6300 individus Connectivité~2

Sensibilité

Fréquences d'apparition pondérées des arcs sur 20 exécutions

G 725 G321 1G 910 G18 0.98

G 221 G119 0.95

G 901 G544 0.92

G748 G92 0.89G 221 G 226 0.88

Réseaux orientés

Arabidopsis thaliana 24

Arabidopsis thaliana

➢ Données expérimentales (Simon et al., 08)

• Population RIL 158 individus (Cvi/Col)

• Puces CATMA 34660 sondes (22089 gènes)

• Marqueurs SNP 89

➢ Pré-traitement des données d'expressions• complétion des manquants à l'aide de sondes prédictrices• sélection de 4176 sondes expliquées par le polymorphisme (eQTL)

• création de pseudos-marqueurs ( 590 marqueurs au total )

• sélection de 4176 sondes expliquées par le polymorphisme (eQTL)

➢ Pré-traitement des données d'expressions• complétion des manquants à l'aide de sondes prédictrices

➢ Pré-traitement des génotypes• complétion des manquants avec le paquet R « qtl »

• création de pseudos-marqueurs ( 590 marqueurs au total )

• sélection de 4176 sondes expliquées par le polymorphisme (eQTL)

➢ Pré-traitement des données d'expressions• complétion des manquants à l'aide de sondes prédictrices

➢ Pré-traitement des génotypes• complétion des manquants avec le paquet R « qtl »

nb. de gènes nb. de marqueurs≠

Arabidopsis thaliana➢ Réseau bayésien appris

• 4766 variables• 6137 arcs (284 Mi → Ej / 5853 Ei → Ej)

➢ Comparaison avec une analyse eQTL ** recherche pour chaque gène, les polymorphismes expliquant son expression

→ ~48% des eQTL detectés en trans sont expliqués par un chemin dans notre RB

➢ Comparaison avec une analyse eQTL ** recherche pour chaque gène, les polymorphismes expliquant son expression

→ LHCB6 & ACP4 impliqués dans le phénomène de photosynthèse chez A. thaliana

→ ~48% des eQTL detectés en trans sont expliqués par un chemin dans notre RB

Conclusions 26

Conclusions

➢ Nous avons proposé une modélisation par RB dans le cadre des données de génétique-génomique.

➢ Nous avons reconstruit un premier RRG pour Arabidopsis thaliana à partir de données réelles.

• Résultats cohérents avec une analyse eQTL• Validation avec la littérature de certaines régulations apprises

• Approche compétitive sur des réseaux de petite taille (Web50) etpour des réseaux plus larges (DREAM)

➔ Inférence de réseaux de régulation de gènes au travers de scores étendus dans les réseaux bayésiens. Revue d'Intelligence Artificielle, à paraître.

➔ Gene Regulatory Network Reconstruction Using Bayesian Networks, the Dantzig Selector, the Lasso and Their Meta-Analysis. PLoS ONE, 2011.

Conclusions générales 27

Conclusions générales

➢ Les réseaux bayésiens représentent une approche performante pour l'apprentissage de RRG

• Modélisation d'effets non-linéaires

➢ Amélioration de l'apprentissage des RB à l'aide de voisinages étendus

• Représentation de la causalité induite par les données de génétique-génomique

• Évaluation globale du réseau

• Proposition d'opérateurs locaux : SWAP et extension itérative

➢ Questions en suspens• Approximations dues : - à l'absence de circuit

- à la discrétisation - au caractère glouton de notre approche

• Post-traitement de la structure apprise

Perspectives 28

Perspectives à court terme

• Enrichir notre comparatif d'autres approches : Optimal Reinsertion

• Tester les opérateurs avec des heuristiques plus évoluées : Tabu

• Comparer les réseaux appris au réseau optimal

• Diffuser l'algorithme SGS sur des logiciels existants (Cytoscape)

➢ Application aux données de génétique-génomique

➢ Apprentissage de réseaux bayésiens

• Évaluer les méthodes de discrétisation

• Poursuivre l'étude du RRG d'Arabidopsis thaliana

Perspectives 29

Perspectives à plus long terme

• Enrichir le modèle de nouveaux types de données

• Restreindre intelligemment l'espace de recherche

• Continuer d'améliorer la distance d'édition à l'aide de post-traitements

➢ Apprentissage de réseaux bayésiens

➢ Application aux données de génétique-génomique

Références

Présentation des réseaux bayésiens (RB) i

Équivalence de Markov

Secousse Effraction

Alarme

Appel à un voisin

Message radio

Secousse Effraction

Alarme

Appel à un voisin

Message radio=

➢ Deux instances d'une même classe d'équivalence représentée par un cpDAG(completed partially Directed Acyclic Graph)

➢ Impact du nombre d'exécutions r ➢ Moyennes sur 30 jeux de données du réseau Alarm (500 exemples)

➢ SGS initialisé avec le graphe vide et le graphe aléatoire (2 parents max)

Comparatifs ii

Comparatifs : Nombre de répétitions

Comparatifs iii

Réseaux DREAM

Réseau 11999 individus connectivité~2

➢ Nombre d'arcs en commun parmi les 1000 premiers classés par les 3 approches

VPVPFP

Apprentissage de la structure de réseaux bayésiens

Documents

Réseaux Bayésiens - Inria · 2008. 2. 4. · Plan Le tutoriel proposé est inspiré des formations réseaux bayésiens effectuées pour le réseau RISC du RISC en 2005 et 2006,

Apprentissage de la structure des réseaux bayésiens : état

Réseaux Bayésiens - Deptinfo

Panorama des problématiques de traitement de l’informationiut-c.univ-lille.fr/fileadmin/user_upload/... · apprentissage automatique apprentissage supervisé apprentissage non

Réseaux Bayésiens pour l’aide à la décision

Evaluation apprentissage

Mise en œuvre des réseaux bayésiens

Apprentissage Automatique (5/10): Apprentissage non supervisé

Introduction aux Réseaux Bayésiens

apprentissage organisationnel.doc

Cours 4: Réseaux Bayésiens - Cours informatiqueCours 4: Réseaux Bayésiens Université de Blida Département d’informatique Master 2- GSI Mme Fareh 2015/2016 1

Apprentissage Automatique (4/7): Apprentissage non supervisé

Méthodes de construction de réseaux bayésiens

Mélanges bayésiens de modèles d'extrêmes multivariés,

Vers des Réseaux Bayésiens pour la Classification des

Apprentissage en entreprise. C.A.P APPRENTISSAGE

Diagnostic et pronostic de défaillances par réseaux bayésiens

Indexation de structures de documents par réseaux bayésiens · Indexation de structures de documents par réseaux bayésiens Mohamed Ali Mahjoub, - Khlifia Jayech Institut

Behja, Hicham & Senach, Bernard - Tutoriel Réseaux Bayésiens (EGC, 2008)

IFT 615 Intelligence Artificielle Jean-François Landry Département dinformatique Université de Sherbrooke Réseaux bayésiens jflandry/ift615