Apprentissage de structure de réseaux bayésiens à partir ... · Apprentissage de structure de...

Apprentissage de structurede réseaux bayésiens à partir

de réseaux markoviens

Christophe Gonzales et Nicolas Jouve

{Christophe.Gonzales, Nicolas.Jouve}@lip6.fr

LIP6 – Université Paris 6

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Introduction

Apprentissage de structure : étant donné un échantillon d’unedistribution P, trouver un graphe représentant P « au mieux »

Deux approches :

Contraintes : tests d’indépendance conditionnelle (e.g. χ2)Optimisation : exploration heuristique de l’espace desmodèles, dotés d’une mesure de qualité (e.g. BIC)

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Introduction

Apprentissage de structure : étant donné un échantillon d’unedistribution P, trouver un graphe représentant P « au mieux »

Deux approches :

Contraintes : tests d’indépendance conditionnelle (e.g. χ2)Optimisation : exploration heuristique de l’espace desmodèles, dotés d’une mesure de qualité (e.g. BIC)

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Introduction

Approche optimisation : quel espace utiliser ?

RB : structures équivalentes forment des plateaux dans lafonction scoreClasses d’équivalence (graphes partiellement orientés) :

espace plus petit et mieux adapté à l’explorationgarantie d’optimalité (algo Greedy Equivalent Search)

RM : contrepartie non orientée des RB

exponentiellement plus petitvoisinage plus simple

Motivation : peut-on tirer profit de l’espace des RM ?

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Introduction

Approche optimisation : quel espace utiliser ?

RB : structures équivalentes forment des plateaux dans lafonction scoreClasses d’équivalence (graphes partiellement orientés) :

espace plus petit et mieux adapté à l’explorationgarantie d’optimalité (algo Greedy Equivalent Search)

RM : contrepartie non orientée des RB

exponentiellement plus petitvoisinage plus simple

Motivation : peut-on tirer profit de l’espace des RM ?

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Introduction

Approche optimisation : quel espace utiliser ?

RB : structures équivalentes forment des plateaux dans lafonction scoreClasses d’équivalence (graphes partiellement orientés) :

espace plus petit et mieux adapté à l’explorationgarantie d’optimalité (algo Greedy Equivalent Search)

RM : contrepartie non orientée des RB

exponentiellement plus petitvoisinage plus simple

Motivation : peut-on tirer profit de l’espace des RM ?

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Introduction

Approche optimisation : quel espace utiliser ?

RB : structures équivalentes forment des plateaux dans lafonction scoreClasses d’équivalence (graphes partiellement orientés) :

espace plus petit et mieux adapté à l’explorationgarantie d’optimalité (algo Greedy Equivalent Search)

RM : contrepartie non orientée des RB

exponentiellement plus petitvoisinage plus simple

Motivation : peut-on tirer profit de l’espace des RM ?

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Plan de l’exposéRéseaux bayésiens et markoviensNotre méthodeApprentissage du RMOrientationRaffinementConclusions et perspectives

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Réseaux markoviens et bayésiens

Réseau markovien bayésienGraphe non orienté orienté sans circuits

Critère

Séparation :X ⊥s Y | Z

si toute chaîne entre X et Y

possède un nœud dans Z

d-séparation :X ⊥ds Y | Zsi ∀ chaîne ch entre X et Y ∃un nœud S de ch t.q.

- si S est convergent sur ch,

ni S ni aucun de ses descendants n’ap-

partiennent à Z,

- sinon, S appartient à Z.

Factoris.si P > 0, P(V) =

QC∈C ψ(C),

où C est l’ens. des cliques du graphe.P(V) =

Qni=1 P(Xi |Parents(Xi))

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Réseaux markoviens et bayésiens

Réseau markovien bayésienGraphe non orienté orienté sans circuits

Critère

Séparation :X ⊥s Y | Z

si toute chaîne entre X et Y

possède un nœud dans Z

d-séparation :X ⊥ds Y | Zsi ∀ chaîne ch entre X et Y ∃un nœud S de ch t.q.

- si S est convergent sur ch,

ni S ni aucun de ses descendants n’ap-

partiennent à Z,

- sinon, S appartient à Z.

Factoris.si P > 0, P(V) =

QC∈C ψ(C),

où C est l’ens. des cliques du graphe.P(V) =

Qni=1 P(Xi |Parents(Xi))

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Réseaux markoviens et bayésiens

Réseau markovien bayésienGraphe non orienté orienté sans circuits

Critère

Séparation :X ⊥s Y | Z

si toute chaîne entre X et Y

possède un nœud dans Z

d-séparation :X ⊥ds Y | Zsi ∀ chaîne ch entre X et Y ∃un nœud S de ch t.q.

- si S est convergent sur ch,

ni S ni aucun de ses descendants n’ap-

partiennent à Z,

- sinon, S appartient à Z.

Factoris.si P > 0, P(V) =

QC∈C ψ(C),

où C est l’ens. des cliques du graphe.P(V) =

Qni=1 P(Xi |Parents(Xi))

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Réseaux markoviens et bayésiens

Réseau markovien bayésienGraphe non orienté orienté sans circuits

Critère

Séparation :X ⊥s Y | Z

si toute chaîne entre X et Y

possède un nœud dans Z

d-séparation :X ⊥ds Y | Zsi ∀ chaîne ch entre X et Y ∃un nœud S de ch t.q.

- si S est convergent sur ch,

ni S ni aucun de ses descendants n’ap-

partiennent à Z,

- sinon, S appartient à Z.

Factoris.si P > 0, P(V) =

QC∈C ψ(C),

où C est l’ens. des cliques du graphe.P(V) =

Qni=1 P(Xi |Parents(Xi))

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Optimalité

Ppté de Markov Globale : X ⊥ Y | Z =⇒ X⊥⊥PY | ZOptimalité : G contenant P est optimale s’il n’existe pas G′contenant P tq (i) G « contient » G′ et (ii) G et G′ ne sontpas équivalentesP DAG-isomorphe =⇒ ∃B∗ RB optimal, unique auxéquivalents prèsP DAG-isomorphe =⇒ P > 0 =⇒ ∃!G∗ RM optimal, graphemoral de B∗

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Optimalité

Ppté de Markov Globale : X ⊥ Y | Z =⇒ X⊥⊥PY | ZOptimalité : G contenant P est optimale s’il n’existe pas G′contenant P tq (i) G « contient » G′ et (ii) G et G′ ne sontpas équivalentesP DAG-isomorphe =⇒ ∃B∗ RB optimal, unique auxéquivalents prèsP DAG-isomorphe =⇒ P > 0 =⇒ ∃!G∗ RM optimal, graphemoral de B∗

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

De Markov à Bayes : tout est dans la V-structure

L’information liée à l’orientation réside dans les nœudsconvergents, et plus précisément dans les V-structuresPasser d’un modèle à l’autre :

RB = RM ssi le graphe est triangulé (NB : DAG sans VS esttriangulé)RB → RM : moralisationRM → RB : démoralisation...

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

De Markov à Bayes : tout est dans la V-structure

L’information liée à l’orientation réside dans les nœudsconvergents, et plus précisément dans les V-structuresPasser d’un modèle à l’autre :

RB = RM ssi le graphe est triangulé (NB : DAG sans VS esttriangulé)RB → RM : moralisationRM → RB : démoralisation...

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

De Markov à Bayes : tout est dans la V-structure

L’information liée à l’orientation réside dans les nœudsconvergents, et plus précisément dans les V-structuresPasser d’un modèle à l’autre :

RB = RM ssi le graphe est triangulé (NB : DAG sans VS esttriangulé)RB → RM : moralisationRM → RB : démoralisation...

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

De Markov à Bayes : tout est dans la V-structure

L’information liée à l’orientation réside dans les nœudsconvergents, et plus précisément dans les V-structuresPasser d’un modèle à l’autre :

RB = RM ssi le graphe est triangulé (NB : DAG sans VS esttriangulé)RB → RM : moralisationRM → RB : démoralisation...

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Plan de l’exposéRéseaux bayésiens et markoviensNotre méthodeApprentissage du RMOrientationRaffinementConclusions et perspectives

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Notre méthode

Hypothèses : P est DAG-isomorphe et les données sont ennombre suffisant

construire le RM optimal G∗

l’orienter en un RB B0

raffiner B0 dans l’espace des CE jusqu’à obtenir B∗

Approche exacte (comme GES) malgré la NP-difficulté duproblème mais...

le pire cas ne semble pas fréquenton obtient des réseaux aux propriétés intéressantes entemps polynomialla phase de raffinement est anytime

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Notre méthode

Hypothèses : P est DAG-isomorphe et les données sont ennombre suffisant

construire le RM optimal G∗

l’orienter en un RB B0

raffiner B0 dans l’espace des CE jusqu’à obtenir B∗

Approche exacte (comme GES) malgré la NP-difficulté duproblème mais...

le pire cas ne semble pas fréquenton obtient des réseaux aux propriétés intéressantes entemps polynomialla phase de raffinement est anytime

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Plan de l’exposéRéseaux bayésiens et markoviensNotre méthodeApprentissage du RMOrientationRaffinementConclusions et perspectives

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Exploration de l’espace des RM

Deux approches :

Optimisation : impossible dans ce contexte car l’estimationdu MV est très coûteuse dans le cas général⇒ Contraintes, mais les tests IC sont non-significatifs sil’ensemble conditionnant est trop grand (pour une quantitéde données raisonnable)

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Exploration de l’espace des RM

Deux approches :

Optimisation : impossible dans ce contexte car l’estimationdu MV est très coûteuse dans le cas général⇒ Contraintes, mais les tests IC sont non-significatifs sil’ensemble conditionnant est trop grand (pour une quantitéde données raisonnable)

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Apprentissage de G∗

1 G graphe vide2 Phase d’ajouts :

TQ c’est possible,

Choisir (X , Y ) 6∈ G tq X 6 � Y | SepG(X , Y )L’ajouter

3 Phase de retraits :∀(X , Y ) ∈ G tq X⊥⊥Y | SepG(X , Y ), ôter (X , Y )

↪→ On montre qu’on obtient G∗, en temps polynomial

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Apprentissage de G∗

1 G graphe vide2 Phase d’ajouts :

TQ c’est possible,

Choisir (X , Y ) 6∈ G tq X 6 � Y | SepG(X , Y )L’ajouter

3 Phase de retraits :∀(X , Y ) ∈ G tq X⊥⊥Y | SepG(X , Y ), ôter (X , Y )

↪→ On montre qu’on obtient G∗, en temps polynomial

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Comment éviter les tests non-significatifs ?

Construction incrémentale plutôt qu’agrégation decouvertures de MarkovCalculs de séparateurs (presque) minimaux partriangulation du graphe courant et collecte-diffusion dansl’arbre de jonctionChoix heuristique de l’arête à ajouter : dépendance la plusgrande, mesurée par l’écart normalisé au seuil du χ2

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Comment éviter les tests non-significatifs ?

Construction incrémentale plutôt qu’agrégation decouvertures de MarkovCalculs de séparateurs (presque) minimaux partriangulation du graphe courant et collecte-diffusion dansl’arbre de jonctionChoix heuristique de l’arête à ajouter : dépendance la plusgrande, mesurée par l’écart normalisé au seuil du χ2

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Comment éviter les tests non-significatifs ?

Construction incrémentale plutôt qu’agrégation decouvertures de MarkovCalculs de séparateurs (presque) minimaux partriangulation du graphe courant et collecte-diffusion dansl’arbre de jonctionChoix heuristique de l’arête à ajouter : dépendance la plusgrande, mesurée par l’écart normalisé au seuil du χ2

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Plan de l’exposéRéseaux bayésiens et markoviensNotre méthodeApprentissage du RMOrientationRaffinementConclusions et perspectives

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Orientation

Boucle sur les nœuds :Choisir X n’appartenant qu’à une unique cliqueOrienter les arêtes adjacentes vers luiTenter d’ôter des arêtes de moralisation entre ses voisins

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Orientation

C

H

K

R

L

J

F C

H

K

R

L

J

C

H

K L

J

C

H

K

J

C

H

K

H

K K

C

H

K

R

L

J

F C

H

K

R

L

J

F C

H

K

R

L

J

F C

H

K

R

L

J

F C

H

K

R

L

J

F

H

K

R

L

J

FC

H

K

R

L

J

F C

G∗ G1 G2 G3 G4 G5 G6

B∗ B1 B2 B3 B4 B5 B6 = B

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Propriétés

A chaque pas, il existe bien un nœud n’appartenant qu’àune unique clique si l’algo est appliqué à G∗

Sinon, il faut trianguler localementOn obtient un RB B0 contenant P, de graphe moral G∗, entemps polynomialOn a révélé des VS de B∗ mais en général pas toutes

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Propriétés

A chaque pas, il existe bien un nœud n’appartenant qu’àune unique clique si l’algo est appliqué à G∗

Sinon, il faut trianguler localementOn obtient un RB B0 contenant P, de graphe moral G∗, entemps polynomialOn a révélé des VS de B∗ mais en général pas toutes

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Propriétés

A chaque pas, il existe bien un nœud n’appartenant qu’àune unique clique si l’algo est appliqué à G∗

Sinon, il faut trianguler localementOn obtient un RB B0 contenant P, de graphe moral G∗, entemps polynomialOn a révélé des VS de B∗ mais en général pas toutes

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Plan de l’exposéRéseaux bayésiens et markoviensNotre méthodeApprentissage du RMOrientationRaffinementConclusions et perspectives

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Raffinement

Greedy Equivalent Search comprend deux phases(exponentielles) :

Phase d’ajouts : construction d’un RB contenant PPhase de retraits : raffinement d’un RB contenant Pjusqu’à B∗

=⇒ on peut appliquer la phase 2 de GES à B0

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Raffinement

Greedy Equivalent Search comprend deux phases(exponentielles) :

Phase d’ajouts : construction d’un RB contenant PPhase de retraits : raffinement d’un RB contenant Pjusqu’à B∗

=⇒ on peut appliquer la phase 2 de GES à B0

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Plan de l’exposéRéseaux bayésiens et markoviensNotre méthodeApprentissage du RMOrientationRaffinementConclusions et perspectives

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Conclusions

on conserve la propriété d’optimalité de GESon remplace sa première phase exponentielle par unephase polynomiale

plus rapide !on obtient de bons réseaux (optimaux pour l’inférence) entemps polynomial

la phase de raffinement (exponentielle) est anytime

↪→ Principe : exploiter d’abord et intégralement l’informationaccessible polynomialement, à savoir l’aspect non orienté dumodèle

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Conclusions

on conserve la propriété d’optimalité de GESon remplace sa première phase exponentielle par unephase polynomiale

plus rapide !on obtient de bons réseaux (optimaux pour l’inférence) entemps polynomial

la phase de raffinement (exponentielle) est anytime

↪→ Principe : exploiter d’abord et intégralement l’informationaccessible polynomialement, à savoir l’aspect non orienté dumodèle

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Conclusions

on conserve la propriété d’optimalité de GESon remplace sa première phase exponentielle par unephase polynomiale

plus rapide !on obtient de bons réseaux (optimaux pour l’inférence) entemps polynomial

la phase de raffinement (exponentielle) est anytime

↪→ Principe : exploiter d’abord et intégralement l’informationaccessible polynomialement, à savoir l’aspect non orienté dumodèle

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Conclusions

on conserve la propriété d’optimalité de GESon remplace sa première phase exponentielle par unephase polynomiale

plus rapide !on obtient de bons réseaux (optimaux pour l’inférence) entemps polynomial

la phase de raffinement (exponentielle) est anytime

↪→ Principe : exploiter d’abord et intégralement l’informationaccessible polynomialement, à savoir l’aspect non orienté dumodèle

Introduction RB et RM Méthode Apprentissage du RM Orientation Raffinement Conclusions

Perspectives

Poursuivre les expérimentationsExploiter les propriétés de B0 pour optimiser la phase 2Etudier plus précisément la robustesse de la méthode àses deux hypohtèses