A.delaplace.thesis

UNIVERSIT FRANOIS RABELAISTOURS

cole Doctorale : Sant, Scienceset Technologies

Anne Universitaire : 2006-2007

THSE POUR OBTENIR LE GRADE DE

DOCTEUR DE LUNIVERSIT DE TOURS

Discipline : Informatique

prsente et soutenue publiquement

par :

Alain DELAPLACE

le 12 dcembre 2007

Approche volutionnaire de lapprentissage de structure pourles rseaux baysiens

Directeur de thse : Professeur Hubert C

Co-encadrement : Thierry B

JURY :

T BROUARD Examinateur Matre de Confrences lUniversit de ToursH CARDOT Directeur de thse Professeur des universits lUniversit de ToursP LERAY Rapporteur Professeur des universits lUniversit de NantesJ LOPEZ KRAHE Examinateur Professeur des universits lUniversit Paris 8M SEBAG Rapporteur Directeur de Recherches lUniversit Paris-Sud

"Theres no such thing as a free lunch.""Specialization is for insects."

Robert A. Heinlein

Remerciements

Je tiens remercier en premier lieu, pour la place quils ont eu dans ces annes de travail,Hubert Cardot et Thierry Brouard. Je les remercie de la libert de choix et de recherche quilsmont laiss tout en sachant me guider une fois mes choix dcids. Je tiens aussi par ailleurs mexcuser auprs deux pour les relectures, nombreuses, et certainement pas toujours agrablestant donn mon amour des grandes phrases.

Je tiens aussi remercier mes rapporteurs. Philippe Leray, pour avoir su, que ce soit di-rectement ou indirectement, me conseiller et mavoir fait dcouvrir le domaine des rseauxbaysiens. Je ne pense pas tre le seul dans ce cas tant donn la popularit grandissante desrseaux baysiens dans nos provinces. Merci, de mme, Michle Sebag pour ses remarquesconcernant les diffrents points de mon travail autour des mthodes volutionnaires et avoirsu partager son exprience. Le travail final en a t grandement amlior.

Mes parents, bien sr. Cest vident, bien sr, mais cest vous que je dois den tre l. Entreles encouragements, le toit et les repas chauds ainsi que les coups de pieds souvent mrits,vous avez t l du dbut la fin et il faudrait tre le dernier des ingrats pour ne pas en rendrecompte. Du dbut la fin, chaque galre, chaque moment difficile, vous tiez l. De l penser que vous me portez la poisse... Ma famille, en gnral, et ma tante Nadia pour mavoirtoujours laiss une gamelle chauffer deux heures dumatin, quand les barres du distributeurne suffisaient plus.

Maintenant, la partie dsopilante. La section des remerciements aura constitu pour moiune des parties les plus problmatiques rdiger. Qui doit y figurer ? Dans quel ordre etsurtout, aurais-je oubli quelquun ? Dois-je dcevoir mon public qui sattend une avalanchede gags et de calembours en une fusion miraculeuse dun almanach Vermot et dune section deremerciements traditionnelle, du genre tirer des larmes un parpaing ?

Usuellement constitue dun dfil de sobriquets ridicules voquant une vie sociale depuislongtemps moribonde et de rfrences appuyes dinterminables nuits de travail, illustrant lapathtique mais virile nostalgie digne dune chambre militaire des heures fiches en lair surdes sujets striles, la page des remerciements est traditionnellement un manuscrit de thse ceque les ds en mousse sont une voiture.

Quand des annes censes tre les plus intenses dune existence ne semblent avoir connucomme sommets que de tristes soires tartiflettes passes devant une empoignade tlvise desombres nanderthaliens en short avec des gens dont on ignore pour la plupart les prnoms,on se fait rapidement une ide de la qualit de vie allant de pair avec les tudes longues.

Mais puisquil faut en passer par l, allons-y.

6

mes amis, Mathieu, Guillaume, Clment, Christophe, Ludo... Merci pour avoir supportmon sale caractre et mon cynisme meurtrier. Mes dpressions nauraient pas t les mmessans vous. Plus srieusement, il est du domaine public que jai un caractre de cochon mais jesais que les amis, ce sont les gens encore l aprs que lon se soit comport comme un crtin.

Les compagnons de galre du labo : Stphane, le trio Julien O., Julien M. et Ludo P.(lesgrands musiciens sont ceux aux carrires les plus courtes, je vous souhaite de rester petits),Sbastien D.(lve le pied et dors un peu, ce point-l a relve du masochisme), Rashid (celui-qui-ne dors-jamais, ou rarement), Lamia (pour les nuits de rdaction et pour tre toi-mme, toutsimplement), Geoffrey, les Mathieus, Cdric, David, Arnaud, et les dizaines dautres doctorantspasss ou prsents. Merci en particulier Sbastien Aupetit pour son aide sur le domaine desalgorithmes volutionnaires. Je naime pas expdier ainsi de ce que je ne saurais considrercomme une "tche" mais il me faudrait trop de pages pour vous remercier chacun et chacune la hauteur du/des service(s) rendu(s). Et Raoni me ferait un procs, en plus.

Les doctorants "extrieurs" (bah !) : Olivier Franois pour son travail sur la BNT et les rseauxbaysiens mais aussi les conseils et tout le reste, Sabine Barrat pour mavoir montr que montravail pouvait effectivement servir dautres personnes, Nicolas Marti pour... euh, pour lesMartineries, Cheng-Ma pour mavoir aid dcouvrir une culture qui me fascine toujours, etl aussi beaucoup dautres.

Les personnes travaillant au laboratoire dinformatique de luniversit de Tours, bien sr.Merci tous ceux qui auront pris le temps, parfois, de passer mon bureau juste pour medemander comment a allait. Ce nest pas grand-chose mais, au final, a compte. Merci biensr aux membres de mon quipe, lquipe RFAI mais aussi tous ceux des autres quipes pourmavoir donn le coup de main quand jen avait besoin et ce, parfois, avant mme que je necommence ma thse. Un norme et franc merci Jean-Charles Billaut, Ameur Soukhal, VincentTkindt, Christophe Lent, Mohand Slimane et en gnral tous ceux qui ont pris le temps.Et je noublie pas les IATOS sans lesquels on nirait pas bien loin. Un merci spcial Colette,qui sarrange toujours pour que les trains partent lheure et que tous les papiers soient biensigns.

Et merci, bien sr, Christian Proust pour avoir permis que tout cela soit possible.

Ah oui, merci aussi Georges, Brad et Angelina pour cette dlicieuse soire au Georges V.

Et un grand, un immense merci tous ceux qui ny ont pas cru (ils se reconnatront). Voussuprendre aura t une belle motivation pour aller au bout.

Enfin, je concluerai en prcisant que la liste des personnes que je remercie ne saurait treexhaustive ; pirouette lgante qui mvitera de me morfondre, une fois que ce travail seraimprim et dment reli, lorsque jeme rendrai compte que jaurai oubli quelquundimportant.

Table des matires

1 Introduction 15

1.1 Problmatique et objectifs de notre travail . . . . . . . . . . . . . . . . . . . . . . . 17

1.2 Guide de lecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

I tat de lart 21

2 Rseaux baysiens 23

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.2 Dfinition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.3 Proprits des rseaux baysiens . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.3.1 Condition locale de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.3.2 d-sparation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.3.3 Cartes dindpendance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.3.4 Factorisation de la probabilit jointe . . . . . . . . . . . . . . . . . . . . . . 30

2.4 Causalit dans les rseaux baysiens . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.5 Rseaux baysiens densits de probabilits continues . . . . . . . . . . . . . . . 32

2.6 Infrence probabiliste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.7 Exemples dapplication de rseaux baysiens . . . . . . . . . . . . . . . . . . . . . 33

2.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3 Apprentissage des paramtres 37

3.1 Gnralits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

8

TABLE DES MATIRES

3.2 Base de donnes complte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.2.1 Approche frquentiste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.2.2 Approche baysienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3.2.3 Diffrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.3 Base de donnes incomplte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.3.1 Approche frquentiste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.3.2 Approche baysienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4 Apprentissage de structures 45

4.1 Gnralits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4.1.1 Cadre thorique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.1.2 Cadre pratique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.2 Mthodes procdant par tests statistiques . . . . . . . . . . . . . . . . . . . . . . . 48

4.2.1 Algorithmes PC et IC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.2.2 Algorithme BNPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.2.3 Commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.3 Fonctions dvaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.4 Algorithmes employant un score . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4.4.1 Recherche de larbre de recouvrement de poids maximal . . . . . . . . . . 59

4.4.2 Algorithme K2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

4.4.3 Algorithme Greedy Search . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

4.4.4 Recherche gloutonne sur lespace des graphes essentiels . . . . . . . . . . 61

4.4.5 Commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

4.4.6 Mthodes hybrides . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

4.5 Lapprentissage de la structure par des mthodes stochastiques . . . . . . . . . . 66

4.5.1 Mthodes de Monte Carlo par chanes de Markov . . . . . . . . . . . . . . 67

4.5.2 Mthodes volutionnaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

4.6 Problmatiques particulires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

4.6.1 Cas des variables continues . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

9 / 229

TABLE DES MATIRES

4.6.2 Cas des bases de donnes incompltes : lalgorithme SEM . . . . . . . . . 70

4.6.3 Cas des variables latentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

5 Algorithmes gntiques 77

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

5.2 Les algorithmes gntiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

5.2.1 Les composantes dun algorithme gntique . . . . . . . . . . . . . . . . . 80

5.2.2 Oprateurs phnotypiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

5.2.3 Oprateurs gnotypiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

5.2.4 Applications des problmes continus . . . . . . . . . . . . . . . . . . . . 84

5.3 tude thorique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

5.3.1 Le thorme des schmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

5.3.2 Critiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

5.4 Dveloppements autour des algorithmes gntiques . . . . . . . . . . . . . . . . . 88

5.4.1 Adaptativit des paramtres . . . . . . . . . . . . . . . . . . . . . . . . . . 88

5.4.2 Algorithmes estimation de densits . . . . . . . . . . . . . . . . . . . . . 91

5.4.3 Techniques de niching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

5.4.4 Algorithmes gntiques parallles . . . . . . . . . . . . . . . . . . . . . . . 97

5.5 Applications lapprentissage de structures . . . . . . . . . . . . . . . . . . . . . . 98

5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

II Apprentissage de la structure dun rseau baysien par un algorithme volu-tionnaire 103

6 Apprentissage avec rpartition dans lespace des solutions 105

6.1 Algorithme gntique simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

6.1.1 Dfinition dun individu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

6.1.2 Mesure de la qualit dun individu . . . . . . . . . . . . . . . . . . . . . . . 106

6.1.3 Initialisation des individus . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

6.1.4 Stratgies et paramtres de slection . . . . . . . . . . . . . . . . . . . . . . 107

10 / 229

TABLE DES MATIRES

6.1.5 Oprateurs gntiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

6.2 Choix dune stratgie adapte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

6.2.1 Distances entre deux structures de rseaux baysiens . . . . . . . . . . . . 114

6.2.2 Choix dune mthode doptimisation . . . . . . . . . . . . . . . . . . . . . 116

6.2.3 Niching squentiel appliqu lapprentissage de structures . . . . . . . . . 117

6.2.4 Exprimentations et rsultats . . . . . . . . . . . . . . . . . . . . . . . . . . 120

6.3 Combinaison avec une approche spatiale . . . . . . . . . . . . . . . . . . . . . . . 120

6.3.1 Rpartition spatiale de la population . . . . . . . . . . . . . . . . . . . . . . 121

6.3.2 Exprimentations et rsultats . . . . . . . . . . . . . . . . . . . . . . . . . . 123

7 Stratgie dadaptation de la mutation 125

7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

7.2 Notre mthode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

7.3 Exprimentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

8 Exprimentations 135

8.1 Objectifs et mthodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

8.1.1 Mthodes dapprentissage employes . . . . . . . . . . . . . . . . . . . . . 136

8.1.2 Les rseaux appris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

8.1.3 Mesures utilises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

8.1.4 Protocoles exprimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

8.2 Apprentissage de la structure ASIA . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

8.3 Apprentissage de la structure Insurance . . . . . . . . . . . . . . . . . . . . . . . . 147

8.4 Apprentissage de la structure ALARM . . . . . . . . . . . . . . . . . . . . . . . . . 150

8.5 Rsultats complmentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

8.5.1 Commentaires gnraux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

8.5.2 Performances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

8.6 Comportement des algorithmes volutionnaires . . . . . . . . . . . . . . . . . . . 164

8.6.1 volution des individus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

8.6.2 Performances temporelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

11 / 229

TABLE DES MATIRES

8.6.3 Nombre ditrations avant la solution . . . . . . . . . . . . . . . . . . . . . 169

8.6.4 Taux dindividus rpars . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

8.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

III Rseaux baysiens : une application la reconnaissance de formes 173

9 La segmentation de liris dans une image 175

9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

9.2 Rseaux baysiens pour la classification . . . . . . . . . . . . . . . . . . . . . . . . 175

9.2.1 Rseaux baysiens nafs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

9.2.2 Structures arborescentes augmentes . . . . . . . . . . . . . . . . . . . . . 176

9.2.3 Multi-nets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

9.3 Problmatique aborde . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

9.4 Travaux antrieurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

9.4.1 Mthode de J. Daugman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

9.4.2 Mthode de Wildes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

9.5 Notre mthode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

9.5.1 Caractristiques employes . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

9.5.2 La base Ubiris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

9.6 Les modles employs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180

9.7 Implmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

9.7.1 Rsultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

9.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184

IV Conclusions et perspectives 187

10 Conclusion 189

11 Perspectives 191

Bibliographie 193

12 / 229

TABLE DES MATIRES

A Probabilits et statistiques 207

A.1 Probabilits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

A.1.1 Probabilits conditionnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . 208

A.1.2 Indpendances conditionnelles : dfinitions et mesures . . . . . . . . . . . 209

A.2 Formules et notions lis lindpendance conditionnelle . . . . . . . . . . . . . . 210

A.2.1 Entropie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

A.2.2 Rapport de vraisemblance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212

A.2.3 Test de Mann-Whitney . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213

A.3 Mesures de divergence entre deux distributions de probabilits . . . . . . . . . . 213

A.3.1 Divergence de Kullback-Leibler . . . . . . . . . . . . . . . . . . . . . . . . 213

A.3.2 Divergence de Jensen-Shannon . . . . . . . . . . . . . . . . . . . . . . . . . 214

B Analyse de texture 215

B.1 Fondement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

B.1.1 Matrices de cooccurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

B.1.2 Caractristiques dHaralick . . . . . . . . . . . . . . . . . . . . . . . . . . . 216

C Rsultats exprimentaux 219

C.1 Stratgie de pnalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219

C.2 Stratgie dadaptation de la mutation . . . . . . . . . . . . . . . . . . . . . . . . . 220

C.3 Algorithme distribu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221

13 / 229

Chapitre 1

Introduction

La recherche sest depuis longtemps penche sur la restitution ou du moins la simulationdu fonctionnement de lesprit humain. Lune des tentatives les plus reconnues est celle visant pouvoir simuler le processus dapprentissage de ltre humain de manire automatique travers un systme thorique. Ce systme devant alors tre apte apprendre par lexprienceet, par voie de consquence, samliorer dans lexcution de la tche qui lui a t confie.Lobjectif que nous venons dnoncer est le principe gnral de la discipline que lon nommemachine learning. Sous cette dnomination se retrouve effectivement un ensemble de mthodeset de modles dont lobjectif est de pouvoir extraire et intgrer une connaissance par la voie delapprentissage automatique.

Ltendue du champ dapplication des modles graphiques est aussi vaste que la taxonomiesy rapportant. Si les modles dirigs sapprtent lassistance au diagnostic et linfrence,dautres modles (semi-dirigs ou non dirigs) ont t dvelopps mesure du temps et desbesoins afin de pouvoir, par exemple, sappliquer la segmentation dimages, au filtrage designal, etc.

Lintrt dunmodle et de lapprentissage en gnral est dobtenir un systme certes capablede se perfectionner travers sa propre exprience mais aussi apte sadapter des situationsdiffrentes. Pour prendre un exemple simple, lexprience que lon peut avoir en travaillant danslinformatique peut servir, loccasion, dpanner un appareil lectronique. Cette adaptation de nouvelles situations partir de lacquis est aussi une des caractristiques de lhumain.Les objectifs ont volu. Par-del la simple mulation de la cognition humaine, les modles etmthodes du machine learning ont aujourdhui russi rassembler en leur sein des systmesdont les objectifs peuvent tre aussi divers que :

extraire une connaissance trop complexe pour pouvoir tre dcrite par un expert ; aider lexpert en lui apportant une connaissance simplifie ou non du domaine ; inversement, pouvoir intgrer une connaissance experte un domaine ; tre capable, par un apprentissage incrmental, de restituer le mcanisme sous-jacent lobjet modlis ;

offrir un formalisme universel afin de faciliter la transmission de la connaissance acquise ; ...Le domaine du machine learning a considrablement volu depuis le milieu du XXe sicle,

aussi bien travers les modles, depuis les champs de Markov cachs jusquaux machines

15

CHAPITRE 1. INTRODUCTION

vecteurs de support, qu travers ses nombreuses applications allant de lapplication indus-trielle et commerciale jusquaux applications militaires, laide la vie courante sous formelectronique ou encore le diagnostic mdical.

Conus pour pouvoir prendre en charge les problmes comportant la notion dincertitude,les rseaux baysiens apportent la fois une interface intuitive sous la forme dun grapheorient et un ensemble de mthodes permettant dexploiter au mieux la connaissance extraitequils modlisent. Par consquents, les rseaux baysiens se sont peu peu imposs parmiles diffrents modles probabilistes existants. Si les rseaux baysiens ont t connus princi-palement grce aux travaux de Judea Pearl [Pearl, 1988] et Michael Jordan [Jordan, 1998], lespremires bauches de ces modles remontent au dbut du XXe sicle avec les travaux de S.Wright [Wright, 1921].

De toutes les problmatiques gravitant autour des rseaux baysiens, la dtermination dumodle mme est la plus cruciale et la plus tudie. Si la dtermination complte dun rseaubaysien ou de tout modle en gnral par un expert parat tre la solution la plus simple, ilen est hlas autrement. Dune part, une telle dtermination est coteuse en temps et enmoyens.Il est rare de pouvoir promptement dterminer un modle fiable dun domaine constitu denombreuses variables. Dautre part, le modle obtenu par apprentissage constitue lui-mme,dans certains cas, la solution recherche. On peut ainsi souhaiter dterminer les interactionsentre diffrents allles dun gne et donc, partir dune base dexemples, chercher le modlerefltant au mieux ces relations. Dans ce cas, la rponse (le modle) est partie intgrante duproblme et un expert ne pourrait rpondre au besoin.

Diverses mthodologies ont t dveloppes dans le but de permettre un apprentissageautomatique des constituants dun rseau baysien : mthodes dterminant des relations pro-babilistes partir de tests dindpendance statistique, mthodes lisant le meilleur modle partir dun ensemble de candidats ou encore recherche de la meilleure classe dquivalence.

En loccurrence, un type populaire dheuristique dapprentissage pouvant se prter un telexercice est lensemble des mthodes dites volutionnaires et plus particulirement les algo-rithmes gntiques. Issus, dans leur forme actuelle, des travaux de J. H.Holland [Holland, 1975]dans les annes soixante-dix, les algorithmes gntiques partagent avec les rseaux baysiensun facteur dattrait non ngligeable en ce que leur fonctionnement est intuitif et aisment as-similable. Inspirs des thories de Darwin et de lide de slection naturelle, leur principe deslection bas sur la qualit dun individu en fait un typedheuristique visant uneperformanceindividuelle tout en tant capables, la diffrence dheuristiques exactes, de faire une synthsedes rsultats. Un comportement tout fait comparable aux objectifs du machine learning. Lesalgorithmes gntiques font de plus, depuis un certain nombre dannes, lobjet de plusieurstudes visant les sortir du carcan formaliste les restreignant jusqualors un simple schmadexploration stochastique/exploitation. Ces tudes mettent surtout en relief limportance dela reprsentation des solutions ou la possibilit dautomatiser les paramtres de recherche delalgorithme.

Nous proposons ici dtudier le comportement et les performances dun tel algorithme gn-tique lors de lapprentissage de la structure dun rseau baysien. Nous mettrons en videnceles qualits et les dfauts respectifs des diffrents outils et mthodes dvelopps et employs.Comme cela est souvent le cas dans la littrature, nous nous sommes fixs pour objectif deparvenir retrouver une structure connue partir de bases dexemples pralablement chan-

16 / 229


tillonns. Nous avons aussi observ le comportement et les performances de rseaux baysiensappliqus la classification dans le cadre spcifique de la reconnaissance de formes.

1.1 Problmatique et objectifs de notre travail

la lecture de la littrature, il savre que les travaux effectus sur lemploi de mthodesvolutionnaires pour lapprentissage de la structure des rseaux baysiens se sont, pour laplupart, limits lapplication dun algorithme gntique sous sa forme canonique sur un es-pace pralablement restreint ou bien lespace des structures laide doprateurs eux-mmesrestreints. Lobjectif de notre travail est de dterminer, travers plusieurs approches, si lesdveloppements ultrieurs des processus volutionnaires sont mme dapporter un rel b-nfice une telle approche du problme. Une premire approche, consistant en une mthodede niching squentiel adapte, exploite les proprits de lespace des graphes reprsentantsdes classes dquivalence des structures [Delaplace et al., 2007a, Delaplace et al., 2007b]. Unevolution de cette mthode, conjuguant laspect temporel des mthodes squentielles unerecherche rpartie dans lespace des solutions, applique le mme principe une populationrpartie en lots. Enfin, une autre mthode, amliorant et prcisant les premiers principes demutation dynamique appliqus notre problme et exposs dans [Delaplace et al., 2006], mo-dlise une distribution de probabilits pour les diffrentes oprations de mutation applicablesaux structures volues ; distribution rvalue en fonction des rsultats observs au cours desphases successives de mutation.

1.2 Guide de lecture

Dans un premier temps, travers ltat de lart, nous aborderons le thme des rseauxbaysiens. Nous prsenterons les caractristiques de cette modlisation avant de voir quellessont les principales mthodes dapprentissage des paramtres avant daborder les mthodesexistantes dapprentissage des paramtres dun rseau baysien partir dune base de cas.

Dans une deuxime partie, nous prsenterons les diffrentes stratgies dveloppes dans lecadre de nos travaux. Nous introduirons une adaptation des techniques de niching squentielles lapprentissage de structure ainsi quune extension de cette mthode par une distribution desindividus dans lespace. Dans le chapitre suivant, une mthode permettant une adaptation deloprateur de mutation en fonction des rsultats prcdemment obtenus sera prsente. Lesexprimentations et rsultats obtenus laide de ces mthodes ainsi quun comparatif avec lesprincipalesmthodes de recherche de structure par valuation existantes seront prsentes dansle chapitre 8. Enfin, nous prsenterons une application des rseaux baysiens la reconnaissancede formes et plus particulirement la segmentation de liris sur des photographies dilhumain.

Nous terminerons ce document par une discussion autour des rsultats de nos mthodes endtaillant les conclusions que nous avons pu tirer de nos recherches et exprimentations.

En fin de document, outre la bibliographie regroupant les diffrentes rfrences, le lecteurpourra trouver une annexe contenant les principaux rappels quant certaines notions em-

17 / 229


ployes dans nos travaux. Parmi celles-ci se trouvent quelques notions de probabilits, unedescription de certaines techniques de caractrisation de textures employes dans le chapitreddi la classification ainsi que les rsultats de tests que nous avons effectus dans le cadredu paramtrage de nos algorithmes.

18 / 229

Notations

Notations gnralesB Rseau baysien, B = (G,).Xi Indiffremment, variable alatoire ou sommet associ dans un graphe.ri Dimension de la variable Xi.xki k

e instanciation de la variable alatoire Xi, k 1 . . . ri.Vi Liste des ri instanciations de Xi dans D.vik ke lment de Vi.U Ensemble de n variables alatoires {X1,X2, . . .Xn}.D Base de cas issus du domaineU, constitue de N cas. Ensemble des paramtres dun rseau baysien B.i Ensemble des paramtres de la variable Xi.i jk Paramtres de la variable Xi lorsque i = i j et Xi = xki .D(l)i Valeur prise par la variable Xi dans le l

e cas de la base D.i Ensemble des sommets parents du sommet Xi dans un graphe orient

G.i j je instanciation de i.qi Nombre dinstanciations distinctes de i, qi =

rh, h : Xh i.

Ni jk Nombre de cas, dans la base D, o Xi = xki alors que i = i j.Gi G j Relation dquivalence au sens de Markov entre les structures Gi et G j

Notations probabilistesP Mesure de probabilits(. y .) Relation dindpendance marginale.(. y .|.) Relation dindpendance conditionnelle.

Notations graphiquesG Graphe orient sans circuit constitu de n sommets {X1,X2, . . . ,Xn}.V Ensemble des n sommets {X1,X2, . . . ,Xn} dun graphe G.E Ensemble des arcs dun graphe orient G.AdjG(X) Ensemble des sommets de G directement relis au sommet X.X Y Les sommets X et Y sont relis par une arte.X Y Les sommets X et Y sont relis par un arc allant de X vers Y.(. d .|.) Relation de d-sparation dans un graphe G.SepSetG(X,Y) Ensemble de sommets d-sparant les sommets X et Y dans le graphe G

19

Abrviations

Les abrviations employes :

Notation DfinitionGOSC Graphe Orient Sans Circuit.GPOSC Graphe Partiellement Orient Sans Circuit.GE Graphe Essentiel.PAG Partial Directed Acyclic Graph : graphe sans circuit partiellement orient.PAG Partial Ancestral Graph : Graphe complet partiellement ancestral.EDA Estimation of Distribution Algorithm : algorithme estimation de densit.EP Evolution Programming : programmation volutionnaire.ES Evolution Strategies : stratgies dvolution.GP Genetic Programming : programmation gntique.

20

Premire partie

tat de lart

21

Chapitre 2

Rseaux baysiens

travers ce chapitre, nous allons prsenter ce que sont les rseaux baysiens, leur utilitet quelles sont les proprits fondamentales qui en font une modlisation particulirementavantageuse. Le sujet tant trs tendu, nous ne saurions le traiter exhaustivement. Nouspouvons nanmoins recommander plusieurs ouvrages au lecteur souhaitant approfondir lesujet. Bien entendu, louvrage de rfrence demeure celui de J. Pearl [Pearl, 1988] qui est lorigine du formalisme tel que nous le connaissons aujourdhui. [Charniak, 1991] ou le livrede P. Nam et al [Nam et al., 2004] fournissent tous deux une trs bonne introduction au sujet.Enfin dautres ouvrages reconnus traitent des rseaux baysiens ou des modles graphiques engnral : [Lauritzen, 1998, Jordan, 2004, Pearl, 2000].

2.1 Introduction

Dans le cadre de la thorie des probabilits, il est frquent de chercher modliser une dis-tribution de probabilits jointe P sur un domaine de variables alatoiresU = {X1,X2, . . .Xn}. Laconnaissance de cette distribution de probabilits permet de calculer la probabilit de chaquecombinaison dinstances distinctes des variables deU. Ceci permettant, tant donn la connais-sance des valeurs de certaines variables, de pouvoir calculer la probabilit de diffrents vne-ments dont les valeurs sont inconnues.

Les rseaux baysiens font partie dune branche spcifique de la famille des modles gra-phiques probabilistes et se prsentent sous la forme dun graphe orient sans circuit (ou GOSC)symbolisant les diffrentes dpendances existant entre les variables reprsentes.

Un rseau baysien est dfini par les lments suivants : un graphe orient sans circuit dont les sommets reprsentent des variables alatoires dundomaine ;

les arcs du graphe indiquent des dpendances conditionnelles entre les sommets ; des probabilits conditionnelles permettent de quantifier les dpendances.

23

CHAPITRE 2. RSEAUX BAYSIENS

Un exemple de rseau baysien est donn dans la figure 2.1. Il sagit dun rseau dcrivantles relations conditionnelles existant entre :

la survenue ventuelle dun sisme ; la diffusion dun flash radio annonant un sisme ; le cambriolage dun difice ; le dclenchement de lalarme de cet difice, suite un sisme ou un cambriolage ; le fait que le central de la compagnie de scurit appelle les lieux, ou non suivant ltat delalarme.

chaque sommet du graphe est associe une table de probabilits permettant de dterminerla probabilit avec laquelle la variable associe peut prendre une valeur particulire tant donncelles prises par ses parents (sils existent).

Figure 2.1 Exemple de rseau baysien.

Nous remarquons immdiatement certaines indpendances conditionnelles : tre cambriolou non ne dpend pas de la survenue dun tremblement de terre (cela pourrait tre sujet dbatmais nous admettons cette indpendance par souci de simplicit).

Un des principaux avantages du formalisme des rseaux baysiens est de permettre unelecture facilite des indpendances conditionnelles au sein de la distribution de probabilitsmodlise. La dtermination de ces indpendances permet par la suite la simplification des cal-culs, souvent fastidieux, ncessaires au calcul de la probabilit dune instanciation du domaine(i.e. la probabilit jointe de ce dernier).

24 / 229


2.2 Dfinition

Un modle graphique probabiliste permet de reprsenter un ensemble de relations condi-tionnelles au sein dun domaineU = {X1,X2, . . .Xn} de variables alatoires ayant chacune leurpropre domaine de dfinition.

Une valeur dintrt est la distribution de probabilits jointe spcifiant la probabilit dap-parition des diffrentes combinaisons de valeurs de variables du domaine. Cette distribution,une fois connue, permet destimer la probabilit des valeurs dune ou plusieurs variables enconnaissant les valeurs prises par les autres variables du domaine.

Dfinition 1 Un rseau baysienB est dfini la fois qualitativement et quantitativement par un couple(G,) :

G est un GOSC dont les sommets correspondent aux variables (X1,X2, . . .Xn) de lensemble U.Les arcs orients de G reprsentant des dpendances directes entre ces variables.

est lensemble des paramtres du rseau. contient les paramtres i, j,k = P(Xi = xki |i = i j),i 1 . . . n pour chaque valeur xki pouvant tre prise par Xi et chaque configuration i j de i,ensemble des sommets parents de Xi dans G.

Il est noter que ladjectif baysien peut savrer trompeur. Dun point de vue baysien,les probabilits doccurrence dun vnement, conditionnellement ou non un autre, sontquantifies de manire subjective en dfinissant un a priori sur leur distribution. Une approchefrquentiste, quand elle, repose sur lobservation de sries dexpriences (pour plus de dtails,se rfrer au chapitre 3). Sil est videmment possible demployer indiffremment les rseauxbaysiens dans lun ou lautre de ces cadres, le terme baysien est employ dans la dnomi-nation du modle afin de souligner la prpondrance des axiomes relatifs aux probabilitsconditionnelles dans la dfinition et lusage de ces modles.

2.3 Proprits des rseaux baysiens

Lemploi des rseaux baysiens permet dassocier la thorie des probabilits la thorie desgraphes. Il convient ds lors de pouvoir lier les proprits graphiques de la structure G dunrseau baysien B avec les proprits de la distribution de probabilits modlise. Lensembledes (in)dpendances conditionnelles du domaine peut tre dtermin graphiquement partirdun ensemble daxiomes [Pearl, 1997] et dhypothses.

La lecture des indpendances conditionnelles sur un graphe est intimement lie la notionde sparation.

La sparation est un critre permettant de statuer si deux sous ensembles de sommetsdisjoints dungraphe sont ounon spars lunde lautre tant donnun troisime sous ensembledisjoint.

La sparation est dfinie diffremment selon le type de graphe auquel on sintresse (orientou non-orient notamment). Ici, nous nous limitons la dfinition de la sparation dans le cadredes graphes orients.

25 / 229


2.3.1 Condition locale de Markov

Dfinition 2 tant donn un rseau baysien B = {G,}, toute variable Xi de B est indpendante delensemble Nd(Xi)/i, form de lensemble de ses non-descendants dans G privs de ses parents, tantdonn ces derniers, i.e. :

Xi G,Xi y {Nd(Xi)/i}|i

Un descendant dune variable Xi dans un graphe G est dfini comme tant un sommetatteignable depuis Xi par un chemin orient.

Reprenons lexemple de la figure 2.1. La condition locale de Markov applique ici permet,entre autres, daffirmer que Appel Central est indpendant de Flash Radio (qui nest ni un parent,ni un descendant) connaissant Sisme (qui est un parent).

La condition locale de Markov permet donc de dtecter un ensemble minimal dindpen-dances probabilistes entre les sommets et leurs non-descendants, impliquant entre autres quedeux sommets non adjacents Xi et X j de G sont conditionnellement indpendants tant donnun troisime sous-ensemble, contenu dansU/{Xi,X j}.

Cest lapplication de la condition locale de Markov qui nous permet dcrire la probabilitjointe des variables du domaine sous une forme factorise :

P(X1,X2, . . .Xn) =ni=1

P(Xi|i) (2.1)

2.3.2 d-sparation

Si, dans un GOSC, les relations entre les paires de variables sont binaires (relies ou non), ladtermination dune indpendance conditionnelle implique gnralement trois sous ensemblesde variables.

La d-sparation est un critre permettant de dterminer les indpendances conditionnellesmodlises par unGOSC. Simplement, il sagit dedterminer si un sous-ensembleXdevariablesdu domaine est conditionnellement indpendant dun sous-ensemble Y tant donn un sous-ensemble Z.

Sil parat vident que nous faisons alors la corrlation entre la connexit et la dpendanceconditionnelle, la direction des arcs impliqus entre aussi en jeu (le d de d-sparation provenantde directional) car nous dfinissons la notion de chemin connecteur (et inversement, de che-min bloquant). Nous allons introduire progressivement, en les illustrant, les diverses notionsncessaires la dfinition de la d-sparation.

Nous emploierons par la suite le terme de convergence pour dsigner une configurationparticulire au sein du graphe.

Dfinition 3 (V-structure) Dans un graphe G, on appelle convergence (ou V-structure), tout triplet{X1,X2,X3} de sommets tel que

26 / 229


Dfinition 4 (Chemin) Dans un graphe G, un chemin entre deux sommets A et B de G dsigne unesrie darcs conscutifs reliant A B, quelle que soit leur orientation.

Dfinition 5 (Chemin bloquant) Dans un graphe G, un chemin entre deux sommets A et B de G estdit bloquant sil comporte au moins une convergence de la forme X1 X2 X3 telle que X2 ne soit pasinstancie.

La dernire prcision, concernant linstanciation au sein des convergences, sera explique plusloin dans cette section.

Notre dfinition de la d-sparation repose sur celle de sa contrapose : la d-connexion.

Sparation inconditionnelle

Soient deux variablesX1 etX2.X1 etX2 sont d-connectes sil existe un chemin non-bloquantentre X1 et X2.

Figure 2.2 Illustration de la sparation inconditionnelle.

Dans la figure 2.2, les sommets X1 et X3 sont d-connects de mme que les sommets X4et X6. En revanche, on distingue une convergence (non instancie) sur le sommet X3. Celle-ciimplique, entre autres, que les sommets X1 et X6 ne sont pas d-connects (et par consquent,sont d-spars).

Blocage conditionnel

Considrons un sous ensemble Z de variables alatoires dun domaine U. Si les valeursprises par ces variables sont connues, la distribution de probabilits, conditionnellement cesous-ensemble, est modifie qualitativement. Il convient alors de dfinir la d-connexion parrapport un ensemble de conditions pouvant bloquer cette connexion.

Deux sommets X1 et X2 sont d-connects conditionnellement un sous-ensemble Z desommets si il existe un chemin sans convergence reliant X1 et X2 et ne passant par aucune desvariables de Z.

Figure 2.3 Illustration dun blocage conditionnel.

27 / 229


En considrant, dans la figure 2.3 que les sommets griss appartiennent au sous-ensembleZ : X1 et X6 sont toujours d-spars mais, de plus, X1 et X3 sont d-spars par Z (en raison deX2) ainsi que X4 et X6.

Conditionnement sur les convergences

Si on observe un vnement ayant deux causes distinctes et originellement indpendantes,ces causes deviennent dpendantes. Un exemple intuitif permettant de comprendre ce principeest celui du lancer de deux pices. Les variables X1 et X2 reprsentent chacune le rsultat dulancer dune des deux pices et la variable alatoireX3 vaut 1 si les deux lancers ont eu le mmersultat et 0 sinon. Il est alors vident que la connaissance de X3 cre une dpendance entre X1et X2.

Ce rsultat, aussi connu sous le nomdeparadoxedeBerkson, impliqueunenrichissementdesdeux points prcdents et plus exactement dans le cas des sommets situs sur des convergences(deux causes communes) et leurs descendants.

Si un sommet convergent se trouvant sur le chemin appartient lensemble conditionnantZ ou un de ses descendants dans Z, il nest plus un facteur bloquant de d-connexion.

Figure 2.4 Illustrationded-connexions etd-sparations avec conditionnement sur les variables.

Sur la figure 2.4, X1 et X3 sont d-spars par X2 Z de mme que X1 et X7. Mais X3 et X6sont d-connects puisque X4 a son unique descendant dans Z.

Dfinition 6 (Chemins bloqus, actifs) Soit G = {V,E}, un graphe orient sans circuit. Soit A, Bet C trois sous ensembles disjoints de V. Soit un chemin reliant un sommet de A un sommet de B.Le chemin est dit bloqu par lensemble C si une des deux conditions suivantes est remplie :

Le chemin converge en un sommet Xi et ni Xi ni aucun de ses descendants ne sont dans C Le chemin passe par un sommet Xi C en lequel il ny a pas de convergence

Si aucune de ces conditions nest remplie, on dit alors que le chemin est actif.

Cette dfinition permet alors de dfinir prcisment le critre de d-sparation :

Dfinition 7 (d-sparation) Soit G = {V,E}, un graphe orient sans circuit. Soit A, B et C trois sousensembles disjoints deV. A et B sont d-spars par C dans G (not (A G B|C)) si et seulement si tousles chemins reliant un sommet de A un sommet de B sont bloqus par C.

Par la suite, nous emploierons la notation A G B pour indiquer que A et B sont d-sparsdans G.

28 / 229


2.3.3 Cartes dindpendance

Les rgles de la d-sparation que nous venons de voir nous ont permis de dterminer unensemble de relations ternaires non-explicites faisant intervenir des sous ensembles disjointsde sommets.

Une fois les relations de sparation au sein du graphe G dtectes, nous allons chercher qualifier G par rapport la distribution de probabilits P du domaine que nous caractrisonspar lensemble des relations dindpendances conditionnelles quelle implique.

Dfinition 8 (Carte dindpendance) Soit P une distribution de probabilits sur un ensemble de va-riables alatoiresU ;G, unGOSC compos surU etX,Y,Z U, et (. yP .|.)une relation dindpendanceconditionnelle vrifie par P.

G est une carte dindpendance (ou I-map) de P sil vrifie :

X G Y|Z X yP Y|Z

G est une carte de dpendance (ou D-map) de P sil vrifie :

X yP Y|Z X G Y|Z

G est une carte parfaite (ou P-map) de P sil vrifie :

X G Y|Z X yP Y|Z

A noter que dans le cas dune I-map, nous admettons la possibilit quil existe des ind-pendances conditionnelles de P qui ne sont pas reprsentes dans G. Un graphe entirementconnect est alors une I-map de toutes les lois de probabilits surU.

Cette notion peut tre illustre trs simplement par lexemple suivant : considrons la dis-tribution de probabilits P dfinie sur deux variables X et Y et dcrite dans la figure 2.5. Lesvariables X et Y sont indpendantes selon la distribution P.

Figure 2.5 Distribution de probabilits P dfinie sur deux variables X et Y.

Cependant, les graphes G1 et G2 de la figure 2.6 sont tous les deux des I-maps des distri-butions de probabilits associes : X et Y sont bien indpendantes selon G1 et lensemble desindpendances conditionnelles reprsentes par G2 est lensemble vide, ce qui respecte bien ladfinition dun I-map.

Par dfinition [Verma et Pearl, 1990], un rseau baysien est toujours une I-map de la distri-bution quil reprsente. Linconvnient de cette dfinition est quunGOSC entirement connectest lui aussi une I-map de la distribution encode (puisquil nencode aucune indpendance).

29 / 229


Figure 2.6 Exemple de cartes dindpendances.

Dfinition 9 (Carte dindpendances minimale) G est une carte dindpendances minimale de ladistribution de probabilits P si aucun graphe partiel G de G nest une carte dindpendances de P.

Concrtement, cette dfinition signifie quaucun arc de G ne peut tre retir sans violer laproprit des cartes dindpendances.

Thorme 1 Un graphe G est une I-map de la distribution de probabilits P si et seulement si P peut sefactoriser selon G :

P(X1,X2, . . .Xn) =ni=1

P(Xi|i),Xi U

2.3.4 Factorisation de la probabilit jointe

Les diffrentes proprits prcdemment nonces ont pour finalit de permettre lexploi-tation de linterface graphique du rseau baysien afin de simplifier le calcul de la probabilitjointe.

Figure 2.7 Exemple de rseau baysien.

Soit le rseau baysien de la figure 2.7. Ce rseau est constitu de 6 variables binaires ; lecalcul de la probabilit jointe de ces 6 variables requerrait 26 1 = 63 paramtres indpendants.

30 / 229


Nous nous sommes restreints ici un exemple simple, il va de soi que dans le cadre dunemodlisation plus raliste, la fois le nombre de variables et les cardinalits de celles-ci seraientbeaucoup plus leves.

Lquation du thorme 1, applique au rseau de la figure 2.7 nous donne alors la dcom-position suivante :

P(X1,X2, . . . ,X6) = P(X1) P(X2|X1) P(X3|X1) P(X4|X2) P(X5|X2,X3) P(X6|X3)

Ici, le calcul de la probabilit jointe ne ncessite plus que le calcul de 1 + 2 + 2 + 2 + 4 + 2 = 13entres indpendantes. Lconomie en calculs devient bien sr dautant plus impressionnanteque le nombre de variables du rseau concern est grand (et le graphe parcimonieux).

2.4 Causalit dans les rseaux baysiens

Jusqu prsent, nous avons dfini et employ les rseaux baysiens conjointement au termede causalit en raison de limportance de lorientation de la structure du modle dans sonutilisation pratique. Or, il est important de pouvoir distinguer un modle statistique et unmodle causal.

Les rseaux baysiens peuvent tre de deux types : causaux ou non-causaux. Un rseaubaysien causal modlise expressment un ensemble de relations de type cause effet : chaquesommet non-racine du graphe est la consquence directe de ses parents dans le graphe. Unrseau non causal, en revanche, modlise des relations de dpendance probabilistes entre lesvariables : un arc allant dun sommet X vers un sommet Y nimplique pas une relation decausalit.

Jusquici nous avons tabli une dfinition formelle des rseaux baysiens sans nous intresserexplicitement auxmthodesdapprentissagede cesderniers.Or, nousverronspar la suite que lesmthodes dapprentissage usuelles, employant une base dapprentissage constitue dexemplesdinstances du domaine, ne permettent dapprendre la structure dun rseau baysien qu saclasse dquivalence au sens de Markov prs (cf. section 4.4.4) ; dans le cas o le graphe estcausalement suffisant (cf. section 4.1.1), seuls les arcs orients au sein du graphe partiellementorient servant de reprsentant la classe dquivalence du graphe reprsentent des causalitseffectivement dtermines par linformation contenue dans la base dapprentissage.

La dtermination des diffrents liens de causalit dans un graphe non-causal peut alors sefaire de deuxmanires. Soit par lintervention dun expert qui incombe la tche de reprsenterles diffrents liens (et donc orientation des arcs dans la structure), soit par lobservation desconsquences quont des interventions locales en certaines variables sur le domaine modlis.

Lintrt principal de la causalit entre dans le cadre de linfrence causale qui a pour objectifde pouvoir mesurer leffet dune intervention sur une ou plusieurs variables sur la probabilitdun ensemble dautres variables. Linfrence causale et la notion de causalit en gnral sonttoujours sujets discussion aujourdhui, tant sur le plan mathmatique que sur le plan philoso-phique. Le lecteur pourra nanmoins se reporter la lecture de [Spirtes et al., 1999, Pearl, 2000,Meganck et al., 2006a,Meganck et al., 2006b,Murphy, 2003] pour plus de dtails sur les rseauxbaysiens causaux ainsi que sur leur apprentissage.

31 / 229


Dans le cadre de nos travaux, nous nous restreignons lapprentissage des structures partirde bases dapprentissage statiques et donc lapprentissage de rseaux baysiens non causaux.

2.5 Rseaux baysiens densits de probabilits continues

Les rseaux baysiens, tels que prsents dans ce travail de thse, comportent des va-riables prenant leurs valeurs dans des espaces discrets. Bien quil soit rpandu de travaillersur de tels modles, essentiellement pour des raisons pratiques, il est tout fait possibledemployer des rseaux baysiens dans le cas o les variables modlises sont continues.Ainsi, [Lauritzen et Wermuth, 1989] ont propos des rseaux baysiens dont les variables pr-sentent une densit de probabilits correspondant une distribution gaussienne. Dautresmodlisations permettent de gnraliser la densit modlise en lapproximant par un m-lange de gaussiennes [Lerner et al., 2001] ou encore des densits exponentielles tronques[Cobb et Shenoy, 2006].

2.6 Infrence probabiliste

Les rseaux baysiens permettent la dcomposition de la probabilit jointe des variablesdu domaine quils modlisent. Cette dernire proprit permet de pouvoir dduire la valeurprise par une ou plusieurs variables du domaine partir de lobservation dautres variables[Heckerman et al., 1995b].

Commenons par dfinir (O,H), une partition de lensemble des variables X. H reprsentelespace des hypothses. Une hypothse h reprsente une certaine instanciation des variablesdeH.O reprsente, comparativement, les instanciations des variables deO, valeurs connues aumoment de linfrence.

Linfrence probabiliste revient couramment calculer lun des deux termes suivants :

Probabilits marginalesP(o) =

hH

P(o, h)

Probabilits a priori maximalesPmax(o) = maxhP(o, h)

Il se peut que lon cherche aussi, pour une instance de h, la valeur de sa probabilit condi-tionnelle selon o :

P(h|o) = P(o, h)hH P(o, h)

Pour rsumer, linfrence probabiliste revient calculer, tant donn le modle et un en-semble dobservations (on parle, dans la littrature anglo-saxonne, de "preuve" ou evidence), laprobabilit pour une instanciation suppose des variables demeurant ou bien quelle instancia-tion de celles-ci est la plus probable.

32 / 229


Les mthodes dinfrence peuvent se rpartir en deux groupes : les mthodes exactes et lesmthodes approches.

Parmi lesmthodes exactes, lalgorithmedumessage passing (passagedemessages) [Pearl, 1988] restreint aux graphes formant un arbre ou encore du junction tree (arbre de jonction)[Jensen et al., 1990] figurent parmi les plus usits. Ces algorithmes sont expliqus en dtaildans [Pearl, 1997] et [Huang et Darwiche, 1996]. Dautres possibilits sont llimination de va-riables [Dechter, 1997] ou les mthodes symboliques permettant de limiter les calculs dans lescas les plus complexes [Li et DAmbrosio, 1994].

Les mthodes exactes cherchent limiter la quantit de calculs ncessaires en traitant lesvariables de manire locale ; en les regroupant en cliques, par exemple. Nanmoins, cette sim-plification rencontre vite ses limites dans le cas de rseaux trop complexes pour tre traits dela sorte. On peut alors dcider de continuer traiter le problme de manire exacte mais enne travaillant que sur une partie du rseau. Parmi les mthodes approches, les plus connuessont celles bases sur le principe de Monte Carlo Markov Chain ou MCMC [MacKay, 1998]. Lesmthodes dchantillonage deGibbs ou deMetropolis-Hastings [Lauritzen, 1998] peuvent ainsitre appliques aux rseaux baysiens. Lapproximation peut aussi soprer en se limitant unsous ensemble de variables [Draper et Hanks, 1994] ou bien en valuant les sommations im-pliques durant une infrence de type exact [DAmbrosio, 1993]. On peut, de mme, limiterle rseau sur lequel a lieu linfrence en ignorant les dpendances les plus faibles en son sein[Kjrulff, 1994].

Enfin, lesmthodes dites variationnelles cherchent, quant elles, dterminer lemaximumdevraisemblance en approximant la probabilit a posteriori [Jaakkola et Jordan, 1999, Beal, 2003].

Linfrence, exacte ou approche, a t montre comme tant un problme NP-difficile[Cooper, 1987, Dagum et Luby, 1993] et le sujet est prsent plus en dtail dans le livre deF. Jensen [Jensen, 1996]. De mme, louvrage de M. Jordan [Jordan, 1998] regroupe une sriede tutoriaux et darticles sur les rseaux baysiens mais aussi sur les modles graphiques engnral.

2.7 Exemples dapplication de rseaux baysiens

Les applications des rseaux baysiens sattachent essentiellement la prdiction, au diag-nostic et lassistance la dcision :

Filtrage du pourriel concept initialis par [Sahami et al., 1998]. Lutilisation des rseaux bay-siens pour le filtrage du courrier indsirable sest popularise et figure parmi les applica-tions les plus russies et populaires des rseaux baysiens.

Assistance aux handicaps PAM-AID [Lacey et MacNamara, 2000] est un systmedassistanceaudplacement en intrieur destinationdes personnes mobilit rduite. Concrtement,le systme consiste en un dambulateur motoris pouvant dtecter les obstacles (murs,objets,...) lors du dplacement.

Lassistance au pilotage Cest le cas pour la NASA avec le systme VISA servant au diagnosticdes systmes de propulsion.

33 / 229


Dcisions tactiques SAIP (Semi-Automated IMINT Processing) [Fennell et Wishner, 1998] est unprogramme du DARPA (Defense Advanced Research Projects Agency) visant fournir aucommandement militaire une information tactique partir dimages haute dfinition.Des systmes tels que les rseaux baysiens interviennent dans le pr-traitement desimages afin de dterminer les priorits tactiques des lments sur le terrain.

Aide linteraction Plus rcent, le programmeGenoa II [Allanach et al., 2004], issu lui aussi dela recherche au DARPA, a pour objectif lamlioration des interactions homme-machinedans le cadre de la lutte anti-terroriste et emploie ces fins divers outils bioinformatiquesainsi que la modlisation baysienne.

valuation du risque EDF emploie les rseaux baysiens afin de prvoir les risques lis ladisponibilit des sources froides (i.e. le dbit fluvial) pour les centrales nuclaires situesle long de la Loire.

tudes de march Les rseaux baysiens, en conjonction avec des tudes expertes, peuventpermettre de mieux cerner les besoins et impratifs commerciaux dune entreprise enprcisant, par exemple, le cur de cible dune agence bancaire [Jaronski et al., 2001].

Les exemples dapplication sont trs nombreux et lon ne saurait en faire une liste exhaustive.Mais lintrt grandissant, depuis le milieu des annes quatre-vingt dix, dont ont fait preuve lesindustriels pour les modles baysiens ne fait que crotre en particulier grce la gnralisationde processus dinteraction entre lhomme et la machine pour acclrer les prises de dcision.

Parmi les avantages proposs par les rseaux baysiens, nous pouvons aussimentionner leurcapacit, en conjugaison avec les mthodes statistiques dites baysiennes (cest--dire prenanten compte un a priori sur la distribution de probabilits modlise) conjuguer la connais-sance extraite de la base de connaissance avec une connaissance pralable du domaine. Cetteconnaissance, subjective, est frquemment le produit de lavis dun expert humain sur le sujet.Cette proprit est apprciable lorsque lon sait que dans lapplication pratique, lacquisitionde donnes est non seulement coteuse en moyens et en temps mais, hlas, dbouche souventsur une base de connaissance de taille rduite.

Nous verrons de plus, dans les chapitres suivants, que lapprentissage des rseaux baysienspeut aussi seffectuer partir de bases de donnes incompltes (i.e. bases pour lesquelles lesvaleurs prises par certaines variables dudomaine sont inconnuespour certaines instances).Cettepossibilit est particulirement intressante quand le processus de fouille de donnes ne peutsystmatiquement retourner lensemble des valeurs prises par les diffrentes composantes dumodle ( cause de capteurs dfectueux, par exemple).

2.8 Conclusion

Nous avons jusquici abord les fondements thoriques ainsi que les applications des rseauxbaysiens. Dans la suite, nous nous intressons lapprentissage. Lapprentissage dun rseaubaysien peut se dcomposer en deux phases. Dans un premier temps, la structure du rseauest dtermine, soit par un expert, soit de manire automatique partir dune base de cas issusdu domaine modlis (le plus souvent). Enfin, les paramtres du rseau sont leur tourdtermins, ici aussi par un expert ou bien par le biais dun algorithme.

34 / 229


Nos travaux concernent lapprentissage de la structure, cest cet aspect de lapprentissageque nous allons le plus dvelopper. Cependant, il nous parat indispensable de prsenter lesbases essentielles de lapprentissage des paramtres sans lesquels le rseau ne saurait treentirement dtermin.

35 / 229

Chapitre 3

Apprentissage des paramtres

La dmarche usuelle, lors de llaboration automatique dun rseau baysien, consistedabord par infrer la structure du rseau partir dune base de donnes puis lappren-tissage des paramtres de ce rseau.Dans ce chapitre, nous allons nous intresser lapprentissage des paramtres.

Nous dcrivons dans cette partie les mthodes les plus employes pour cette tche.

3.1 Gnralits

Deux principaux cas de figure peuvent se prsenter : le cas o lensemble des donnes contenues dans D est observ ; celui o certaines valeurs, pour une instanciation D(l) donne, ne sont pas connues.Auparavant, plusieurs hypothses doivent tre pralablement faites afindepouvoir effectuer

les calculs ncessaires [Heckerman et Geiger, 1994].

Indpendance des chantillons : les lments de la baseD sont indpendants, identiquementdistribus ;

Indpendance des paramtres : pour toute structure G, dune part les paramtres i associsau nud Xi sont indpendants des paramtres associs aux autres nuds et dautre part,les paramtres i j associs Xi suivant une instanciation i j des parents deXi dansG sontindpendants des paramtres associs aux autres instanciations de i ;

Modularit paramtrique : si un nud prsente les mmes parents dans deux structures dis-tinctesG1 etG2, alors la densit de distribution des paramtres de Xi est la mme pour lesdeux deux modles dfinis par G1 et G2 ;

Une autre hypothse, courante, est de supposer que les paramtres de chaque nud suiventdes densits de probabilits admettant des paramtres de Dirichlet. Les diffrents paramtresi admettent alors une densit de probabilit exponentielle de Dirichlet dexposants 1, . . . , r

37

CHAPITRE 3. APPRENTISSAGE DES PARAMTRES

et leur probabilit est gale :

P(i|1, . . . , n) =(ri

i=1 i)

rii=1 (i)

r

i=1

i1 (3.1)

Ici, reprsente la fonction Gamma dEuler : (x + 1) = x(x) et (1) = 1 dans R.

Cette hypothse sur la densit de probabilits des paramtres vise simplifier les calculs desparamtres. La premire hypothse revient en effet dire que les chantillons de la base D estun chantillon dune loi multinomiale. Or, la densit de probabilit de Dirichlet est la conjuguede la loi multinomiale. Ceci permet de conserver la fois les paramtres et leurs densits dansla mme famille de fonctions.

Nous allons voir que dans les deux cas, en prsence de donnes compltes ou incompltes,nous avons le choix entre un apprentissage uniquement bas sur les informations extraites dela base dapprentissage du modle et un apprentissage permettant de mler ces informations une ventuelle connaissance a priori que nous pourrions avoir sur le domaine.

3.2 Base de donnes complte

Ici, la base dapprentissageD ne contient pas de cas o viendrait manquer une ou plusieursobservations.

Lapprentissage des paramtres dun rseau baysien peut ici se faire suivant deux ap-proches :

Lapproche statistique (ou frquentiste) Lapproche baysienne (ou subjective)

Dans les deux cas, lensemble des paramtres est estim partir de la formule de Bayes :

P(|D) = P(D|) P()P(D)

. (3.2)

Cette quation peut aussi scrire sous la forme :

Probabilit a posteriori =Vraisemblance Probabilit a priori

Vraisemblance marginale.

La probabilit a posteriori de lensemble des paramtres connaissant la base de cas D estfonction de la vraisemblance de cet ensemble par rapport D, de la probabilit a priori de (i.e.la connaissance a priori que nous pouvons avoir sur le domaine) et de la vraisemblance de D.

Pour un ensemble de cas D(l), l 1, . . .N indpendants et identiquement distribus, la vrai-semblance des donnes D tant donn les paramtres estims scrit :

P(D|) =Nl=1

p(D(l)|). (3.3)

38 / 229


Enfin, reste la valeur de la probabilit a priori P() dont le calcul constitue la principalediffrence entre lapproche statistique et lapproche baysienne, comme nous allons le voirdans la suite.

3.2.1 Approche frquentiste

Lesmthodes frquentistes utilisent ds lors diffrents estimateurs dont le but est de parvenir dterminer la meilleure approximation de la valeur des diffrents paramtres du rseau.

Un de ces estimateurs est celui du maximum de vraisemblance. Pour chaque variable Xi,la probabilit dapparition de lvnement xi est directement proportionnelle sa frquencedapparition dans la base dapprentissage.

SoitNi jk le nombre doccurrences simultanes dans la base deXi = xk eti = i j o k 1, . . . riet j 1, . . . qi.

La probabilit estime est alors note P(Xi = xk|i = i j) = MVijk =Ni jkk Ni jk

La log-vraisemblance (le logarithme de la vraisemblance) est souvent employe pour desraisons pratiques (manipulation de valeurs numriques trs faibles).

LL(|D) = logP(D|) =Nl=1

logP(Dl|)

Nous cherchons alors, pour un paramtrei jk = P(Xi = xk|i = i j), la valeur MVijk permettantde maximiser localement la vraisemblance, cest--dire en chaque Xi :

MVijk = argMaxi jk LL(i jk|D)

Avec Ni jk, le nombre doccurences simultanes dans D de Xi = xk et i = i j.

Dmonstration 1 ([Nam et al., 2004]) La vraisemblance L(D(l)|) dune instance D(l) issue de labase dapprentissage D, o D(l) = {X(l)1 ,X

(l)2 , . . .X

(l)n }, en connaissance des paramtres du rseau, scrit :

L(D(l),) = P(X(l)1 ,X(l)2 , . . .X

(l)n ) (3.4)

=

ni=1

P(X(l)i |(l)i ) (3.5)

=i

(l)i jk (3.6)

o (l)i jk indexe implicitement les valeurs spcifiques prises respectivement par Xi et i pour D(l).

Nous supposons que les exemples de la base sont indpendants et identiquement distribus, ce quinous permet dcrire la vraisemblance pour lensemble de la base D :

L(D,) =ni=1

Nl=1

(l)i jk =ni=1

qij=1

rik=1

Ni jki jk (3.7)

39 / 229


la log-vraisemblance scrivant alors :

LL(,D) =ni=1

qij=1

rik=1

Ni jklog(i jk)

La vraisemblance et la log-vraisemblance atteignent leur maximum au mme point en lequel sannuledonc la drive de LL(,D).

Nous rcrivons la log-vraisemblance :

LL(,D) =ni=1

qij=1

ri1k=1

(Ni jklog(i jk)

)+Ni, j,ri log(i, j,ri)

LL(,D) =

ni=1

qij=1

ri1k=1

(Ni jklog(i jk)

)+Ni, j,ri log

1 ri1k=1

i jk

Les drives partielles par rapport aux diffrents i jk valent

LL(,D)i jk

=Ni jki jk

Ni, j,ri1 ri1k=1 i jk

La drive de la log-vraisemblance sannule donc quand chaque i jk vrifie :

Ni jki jk

=Ni, j,ri

1 ri1k=1 i jksoit

Ni, j,1i, j,1

=Ni, j,1i, j,1

= . . . =Ni, j,1i, j,1

=

rik=1Ni jkrik=1 i jk

=

rik=1

Ni jk

Au final, nous obtenons bien

i jk =Ni jkrik=1Ni jk

, k {1, . . . , ri}

Si lapproche frquentiste parat naturelle, elle prsente nanmoins un inconvnient majeurdans le cas dune base dapprentissage de taille limite ; si une instanciation particulire desvariables du domaine peut exister, avec une probabilit faible mais non nulle, mais quelle nestpas prsente dans la base dapprentissage, alors daprs lapproche frquentiste la probabilitde cette configuration est nulle.

Or, le fait quune instanciation nait pas t observe ne signifie pas ncessairement quelleait une probabilit nulle. Afin dy circonvenir, il serait bon de pouvoir exprimer et quantifierla possibilit de la survenance dun tel vnement. Cest cet objectif que remplit lapprochebaysienne.

40 / 229


3.2.2 Approche baysienne

Le principe de cette approche revient traiter le paramtre i jk comme une variable alatoiredote dune densit de probabilit sur lintervalle [0,1].

Si les paramtres i admettent une densit de probabilit exponentielle de Dirichlet (cf.equation 3.1) et que la distribution de D suit une loi multinomiale, nous pouvons exprimer laprobabilit a posteriori des paramtres :

P() ni=1

qij=1

rik=1

(i jk)i jk1 (3.8)

Nous savons dj que : la vraisemblance L(D|) est gale (quation 3.7) :

ni=1

qij=1

rik=1

(i jk)Ni jk

dautre part :

P(|D) = P(D|) P()P(D)

Nous pouvons ds lors crire :

P(|D) ni=1

qij=1

rik=1

(i jk)Ni jk+i jk1 (3.9)

De la mmemanire que dans le cas dumaximum de vraisemblance abord dans lapprochefrquentiste, nous pouvons alors rechercher les paramtres non plus selon le maximum devraisemblance mais selon le maximum a posteriori (MAP). En effet, dans le cadre de lapprochebaysienne, le fait demployer des a priori sur les paramtres du modle par lemploi decoefficients i jk sous entend que les donnes ont dj t observes. La dtermination desparamtres ne se fait alors plus selon les occurrences des donnes (par vraisemblance) maisconditionnellement celles-ci (approche a posteriori).

MAPijk = P(Xi = xk|i = i j) =Ni jk + i jk 1k(Ni jk + i jk 1)

(3.10)

Uneautre approche consiste nonplus rechercher lemaximum a posteriorimais sonesprance(EAP) :

EAPijk = P(Xi = xk|i = i j) =Ni jk + i jkk(Ni jk + i jk)

(3.11)

La diffrence entre ces deux dernires approches consiste essentiellement dfinir si lonsouhaite procder la slection dun modle auquel cas on cherche le modle maximisantla probabilit a posteriori ou bien estimer un modle le plus informatif possible quant auxdiffrentes hypothses reprsentes au sein dune quantit de donnes limite si on dsirealors un modle prdictif .

41 / 229


3.2.3 Diffrences

Les partisans de lapproche frquentiste reprochent gnralement la philosophie bay-sienne dattribuer des estimations P(|D) diffrentes suivant des probabilits a priori P()diffrentes, introduisant par l une subjectivit forte. Lapproche frquentiste considre quelensemble des paramtres a une valeur fixe et ne suit pas une distribution de probabilit.

Les mthodes dapprentissage des paramtres que nous venons de dcrire ne sont valablesque si lensemble des valeurs de la base de donnes D est observable. Dans le cas contraire, ilest ncessaire de faire appel des mthodes permettant destimer les valeurs des observationsmanquantes. Ce sont ces mthodes que nous allons voquer dans la section suivante.

3.3 Base de donnes incomplte

Il peut arriver quau sein de la base dapprentissage du modle, certaines valeurs soientmanquantes. Cette situation peut arriver dans le cas o, par exemple, un capteur de donnesest tomb en panne ou encore lorsque le relev de valeurs savre trop coteux pour tresystmatiquement appliqu.

Les approches vues jusquici ne sont plus, alors, applicables directement ( moins de neconsidrer pour lapprentissage que les instances compltes de la base). Si la solution la plussimple consiste ignorer les instances incompltes de la base de donnes pour lapprentissage,il est plus courant demployer une mthode revenant estimer les donnes manquantes partir des donnes connues. Ce principe est fond sur celui de lalgorithme EM (ExpectationMaximisation ou Esprance Maximisation) propos dans [Dempster et al., 1977] pour tre par lasuite appliqu lapprentissage des paramtres dun rseau baysien dans [Lauritzen, 1995] et[Heckerman, 1995].

De la mme manire que pour lapprentissage partir de donnes compltes, lalgorithmeEM peut tre appliqu selon une approche frquentiste ou baysienne.

3.3.1 Approche frquentiste

Soit : DO = {D(l)O }l=1,...N, lensemble des instances de D pour lesquelles lensemble des valeursprises par les variables du domaine sont observes.

(t), lensemble des paramtres {(t)i jk} des paramtres du rseau baysien B, litration t.Lalgorithme EM commence par estimer les valeurs des donnes manquantes (esprance)

avant de les maximiser de la mme manire que dans le cas complet (maximisation).

42 / 229


Algorithme 1 Algorithme EM pour lapprentissage des paramtres dun rseau baysien1: t 0

2: (0)i jk p > 0 (alatoire)

3: Tant que |(t+1)i jk (t)i jk| Faire

4: 1e tape : Esprance

E(Ni jk) =Nl=1

P(Xi = xk|i = i j,D(l)O , (t)i jk)

5: 2e tape : Maximisation

(t)i jk =E(Ni jk)k E(Ni jk)

6: Fin Tant que

3.3.2 Approche baysienne

Dans ce cas, nous employons des a priori de Dirichlet sur les paramtres. La diffrence avecle traitement frquentiste rside dans la 2e tape de lalgorithme 1 qui devient :

(t)i jk =E(Ni jk) + i jkk E(Ni jk) + i jk

(3.12)

43 / 229

Chapitre 4

Apprentissage de structures

Cette partie constitue une introduction gnrale la problmatique de lapprentissage dela structure dun rseau baysien. Les algorithmes que nous dcrivons ici ont pour objectif detrouver le rseau encodant le mieux la distribution de probabilit implicite la base dappren-tissage qui leur est fournie en entre. Le plan gnral de ce chapitre est celui employ dans[Nam et al., 2004, Franois, 2006, Leray, 2006], Cependant, nous nous attardons volontairementsur certaines descriptions de mthodes ou demodles tout en en ngligeant dautres, selon leurrapport avec nos travaux ou avec leur comprhension.

4.1 Gnralits

La problmatique de lapprentissage de structure peut tre compare lexploration dedonnes, cest--dire lextraction dune connaissance (dans notre cas, la topologie du rseau) partir dune base de donnes [Krause, 1999]. Si le deuxime chapitre prsentait quelques usagesdes modles baysiens dtermins, nous pouvons nanmoins remarquer que dans certains cas,la dtermination mme du modle peut constituer la problmatique rsoudre. Ainsi, dansle cadre de la bio-informatique, les auteurs de [Yu et al., 2002] emploient lapprentissage dela structure dun rseau baysien pour dtecter les relations les plus videntes entre diffrentsrgulateurs gntiques afindepouvoir guider des exprimentations ultrieures. Dans ce typedeproblmatique, la connaissance a priori du domaine que peut ventuellement avoir lutilisateurne permet que la dtection dincongruits flagrantes sur la structure obtenue automatiquement.La structure nest plus alors seulement une partie de la solution au problme mais bien unesolution part entire.

Ce chapitre prsente les mthodes les plus usites dans le cadre de lapprentissage de lastructure, les hypothses sous-jacentes ainsi que les avantages et inconvnients respectifs desdiffrentes mthodes.

45

CHAPITRE 4. APPRENTISSAGE DE STRUCTURES

4.1.1 Cadre thorique

Lacquisition dune structure reprsentative de la distribution de probabilit dun domainede variables prsuppose certaines conditions (dont la condition locale deMarkov, vue en 2.3.1).Lapplication de ces conditions et hypothses permet de garantir lexistence dune telle structure(i.e. que la distribution que nous cherchons modliser peut ltre par un GOSC) mais aussi deposer les bases sur lesquelles se fondent les diffrentes mthodes.

Hypothse de fidlit

Nous avons dores et dj suppos quun rseau baysien vrifiait la condition locale deMarkov : toute variable est indpendante de ses non-descendants connaissant ses parents (dansla structure G du rseau). La condition locale de Markov conjugue la d-sparation permetde dterminer un ensemble minimal dindpendances conditionnelles dans le graphe G. Cetensemble est minimal car il peut exister des indpendances conditionnelles qui ne peuvent tredtermines par la seule lecture du graphe G.

Prenons lexemple de la figure 4.1 reprsentant un graphe G constitu de trois variables etdeux arcs ainsi que les probabilits conditionnelles associes. On peut sans peine observer que,du fait du paramtrage particulier du modle, X1 est indpendant de X2 connaissant X3. Cetteindpendance conditionnelle ne peut tre releve par la seule condition de Markov locale (etdonc la d-sparation).

Figure 4.1 Cas dindpendance conditionnelle indtectable graphiquement.

Les indpendances conditionnelles impliques par une distribution P, comme celle de lafigure 4.1, ne peuvent tre dtermines par lapplication de la condition locale deMarkov seule.

Or, il est dans notre intrt est de pouvoir assurer la corrlation entre le graphe recherchet la distribution sous-jacente aux donnes notre disposition. Pour cela, nous introduisons lanotion de fidlit.

Dfinition 10 (Hypothse de fidlit) Une structure G et une distribution de probabilit P sontdites fidles si et seulement si lapplication de la condition de Markov permet de dduire lensemble desindpendances conditionnelles existant dans P et seulement celles-ci, i.e. :

X,Y U X yP Y X G Y

46 / 229


En dautres termes, lhypothse de fidlit applique une distribution de probabilit Pdfinie sur un domaine de variablesU suppose lexistence dune carte parfaite (ou P-map, cf.dfinition 8) du modle dindpendance associ P.

Cette hypothse invalide lexistence dun modle tel que celui de la figure 4.1.

Modularit paramtrique

Cette hypothse tait dj mise dans le cadre de lapprentissage de paramtres (section 3.1),nous pouvons la rappeler ici :

Dfinition 11 (Modularit paramtrique) Soit deux GOSCG1 etG2, une variable Xi U eti(G),lensemble des sommets prdcesseurs du sommet Xi dans le GOSC G :i 1 . . . n, si i(G1) = i(G2), alors la densit de distribution des paramtres de Xi est la mme pourG1 et G2.

Suffisance causale

Aussi appele hypothse de compltude. Nous supposons quil nexiste pas, dans le domainemodlis, de variable non-observable qui soit parente de deux ou plus variables observes.Lensemble des sommets suffit donc reprsenter lensemble des relations pouvant tre extraitesdes donnes observes. Lhypothse de suffisance causale est cependant la plus mme de sevoir invalider dans le cas de la modlisation de domaines non triviaux o linformaticien nepeut garantir lobservation de lensemble des variables pertinentes au domaine.

Connaissance a priori

Certaines mthodes permettent de prendre en compte une connaissance a priori du modlerecherch, fournie alors par lutilisateur. Certaines mthodes prsentes ici permettent notam-ment lapprentissage dune structure partir de la connaissance dun ordre topologiquementcompatible avec le modle recherch.

Dfinition 12 (Ordre topologiquement compatible) Un ordre topologiquement compatible avecun GOSC G = {V,E} est un ordre partiel sur les sommets de G tel que :

X Y E,X Y

Dans la suite, nous parlerons dordre topologique correct pour dsigner un ordre topologique-ment compatible avec le modle sous-jacent aux donnes dapprentissage.

47 / 229


4.1.2 Cadre pratique

Lapprentissage de structure dun rseau baysien doit ventuellement seffectuer en tenantcompte de la nature des donnes fournies pour lapprentissage (ou simplement de la nature dudomaine modliser) :

variables continues : les variables peuvent prendre leurs valeurs dans un espace continu(cf. section 2.5),

bases de donnes incompltes : le cas des donnes incompltes a dj t voqu dans lecadre de lapprentissage des paramtres (section 3.2). Si, dans le cadre de nos travaux,nous traitons uniquement le cas des bases de donnes compltes, nous documenteronsnanmoins lapprentissage de la structure du modle dans ce cas de figure,

insuffisance causale : il se peut que certaines variables du domaine observ soient condi-tionnellement dpendantes de variables non observes. Certains algorithmes, nous leverrons, permettent alors de dtecter de telles variables.

Pour rsumer, nos travaux ainsi que les mthodes prsentes ici, sauf prcision contraire, serfrent lapprentissage de structure dans le cas o :

les variables modlises prennent leurs valeurs dans un ensemble discret, les variables de la base dapprentissage sont entirement observes, il nexiste pas de variable latente (hypothse de suffisance causale).Dans la suite de ce chapitre, nous allons nous attacher la prsentation des diffrentes

mthodes employables pour lapprentissage de la structure dun rseau baysien.

Ces mthodes peuvent tre rparties en deux principaux groupes :Approche par dcouverte de relations dindpendances : cesmthodes consistent endespro-

cdures de tests sur les indpendances conditionnelles permettant, au final, de retrouverla structure recherche.

Par exploration/valuation : ces mthodes emploient un score afin dvaluer la capacit dugraphe retranscrire les indpendances conditionnelles au sein du modle.

Cest dans lordre de cette description que nous allons dtailler le fonctionnement des prin-cipales mthodes.

4.2 Mthodes procdant par tests statistiques

Une manire de rechercher une structure adquate pour un ensemble dapprentissage est larecherche dindpendances conditionnelles : la structure du rseau est dtermine pas pas entablissant les indpendances conditionnelles existant au sein de lensemble des variables.Si certains des algorithmes de ce type dtectent des variables latentes (caches), en revanche ilsrequirent tous une base complte.

4.2.1 Algorithmes PC et IC

Leprincipe de lalgorithmePC (Peter, Clark, les prnomsdes auteurs) est lui-mmeune volu-tionde lalgorithmeSGS (Spirtes,Glamour, Scheines, tirdesnomsde ses auteurs) [Spirtes et Scheines, 1991,Spirtes et al., 1993].

48 / 229


Le fonctionnement de lalgorithme PC est le suivant : Soit un graphe G(V,E,), deuxsommets Xi et X j deV et un sous ensemble de sommets SXi,X j V/{Xi,X j}. Les sommets Xi etX j sont relis par un arc dans G sil nexiste pas SXi,X j tel que (Xi y X j|SXi,X j).

En pratique, la vrification de lexistence dune telle indpendance revient vrifier lesdiffrentes indpendances (Xi yP X j|SXi,X j) par ordre croissant (ie. selon une taille croissantede lensemble SXi,X j . partir dun graphe non orient entirement connect, la dtection din-dpendances permet alors de supprimer les artes correspondantes jusqu lobtention dusquelette du GOSC recherch. Suivent alors deux phases distinctes visant dans un premiertemps dtecter et tablir les V-structures du graphe puis orienter les artes restantes.

Lalgorithme PC tablit les hypothses suivantes : hypothse de fidlit (cf. section 4.1.1), la base dapprentissage est complte et suffisamment grande, les rsultats des tests dindpendance conditionnelle sont fiables.Il est courant demployer le test du 2 ou bien celui du G2 (cf. Annexes A).

noter que lalgorithme PC, dcrit dans lalgorithme 2, comme tous les algorithmes dap-prentissagede structure employantunebasedexemples, renvoieungrapheorient appartenant la classe dquivalence de Markov du modle recherch : les orientations des arcs, hormiscelles des V-structures dtectes, ne correspond pas forcment aux rels liens de causalit de cemodle.

Les rgles permettant ici dorienter le graphe non-orient obtenu lissue de la phase dedtection des indpendances conditionnelles peuvent tre remplaces par toute heuristiquepermettant lobtention dun GOSC partir dun tel graphe (comme, par exemple, lalgorithmede Dor et Tarsi [Dor et Tarsi, 1992]). Les deux oprations graphiques correspondant dans cettephase de lalgorithme PC lajout dun arc orient reviennent simplement orienter le graphede manire :

ne pas crer de circuit ; de ne pas crer de V-structure ;

Lordre dans lequel les variables sont alors considres peut ventuellement dboucher surdes GOSC diffrents mais nanmoins reprsentant tous les mmes ensembles dindpendancesconditionnelles (et donc quivalents, cf. section 4.4.4).

En revanche, lordre dexcution des tests dindpendance conditionnelle (i.e. lordre sui-vant lequel les diffrent sommets de lensemble conditionnant sont tests) a une influencesur le rsultat final (exception faite du cas o la base dapprentissage est de taille infinie)[Dash et Druzdzel, 1999].

En parallle lalgorithme PC, un autre algorithme, nomm IC (pour Inductive Causation) at dvelopp par lquipe de Judea Pearl [Pearl et Verma, 1991]. Cet algorithme est similaire lalgorithme PC mais part dune structure vide en reliant les couples de variables ds quunedpendance conditionnelle est dtecte (dans le sens o aucun sous-ensemble conditionnantSXY tel que (X y Y)|SXY nest identifi) et obtient donc une D-map minimale l o lalgorithmePC cherche une I-map minimale (voir section 2.3.3).

Linconvnient commun aux deux algorithmes est la multiplicit des tests dindpendanceconditionnelle mener. Lors de la recherche de la structure dunmodle complexe (nombreuses

49 / 229


Algorithme 2 Algorithme PCEntre: Un graphe connexe non orient G = {V,E},V = {X1,X2 . . . ,Xn}1:2: 1etape : Dterminer les indpendances conditionnelles3: k 0;4: G graphe compltement connect;5: SepSetG(Xi,X j) ,(i, j) 1, . . . ,n;6: Tant que Xi,X j V2 tq |Adj(Xi)/X j| k Faire7: Dtermination des indpendances conditionnelles dordre k8: (Xi,X j) V2 tq Xi X j et |Adj(Xi)/X j| k9: Pour tout ensemble de sommets SXi,X j Adj(Xi)/X j tel que |SXi,X j | = k10: Si Xi y X j|SXi,X j Alors11: SepSetG(Xi,X j) SepSetG(Xi,X j) SXi,X j et supprimer larte Xi X j dans G12: Fin Si13: k k + 1;14: Fin Tant que15:16: 2e tape : Dtection des V-structures17: Pour chaque triplet reli deV3 de la forme Xi Z X j Faire18: Si Z < SepSetG(Xi,X j) Alors19: Orienter : Xi Z X j dans G20: Fin Si21: Fin Pour22:23: 3e tape : Orientation des artes restantes24: Tant que @ darte non oriente dans G Faire25: (Xi,X j) V26: Si Xi X j et un chemin orient de Xi vers X j Alors27: orienter larte Xi X j en Xi X j28: Sinon29: Si X j < Adj(Xi),Z tel que Xi Z et Z X j Alors30: orienter larte Z X j en Z X j31: Fin Si32: Fin Si33: Fin Tant que

50 / 229


variables), les deux algorithmes procdent des tests exhaustifs sur les diffrents ensemblesconditionnels SXi,X j possibles, pour chaque couple de sommets (Xi,X j).

4.2.2 Algorithme BNPC

Lalgorithme BNPC (pour Bayes Net Power Constructor) est dcrit dans [Cheng et al., 2002]et utilise une analyse quantitative de linformation mutuelle entre les variables du domainemodlis afin de construire la structure G recherche. Les tests dindpendance conditionnellereviennent alors dterminer un seuil pour linformation mutuelle (conditionnelle ou non)entre les couples de variables concerns.

BNPC se dcompose en trois phases :

1- laboration : Un premier graphe G1 est cr par le mme procd que celui de lalgorithmeMWST (voir section 4.4.1).

2- Enrichissement : Des artes sont ajoutes G1 afin dobtenir un graphe non-orient G2 etce, par application dun nombre rduit de tests dindpendance conditionnelle.

3- Affinement : Une nouvelle srie de tests limine les ventuelles artes superflues deG2 pourobtenir un graphe final, G.

BNPC se dcline sous deux variantes (BNPC-A et BNPC-B) selon que lutilisateur fournisseou non un ordre topologiquement compatible avec la structure recherche. BNPC-A prend enentre un tel ordre peut donc orienter les artes dtectes mesure de la construction.

Dans le cas de BNPC-B, cet ordre est inconnu et lalgorithme ne procde lorientation desdiffrents arcs quau terme de son excution.

La connaissance facultative dun ordre topologique correct a pour consquence une diff-rence notable dans la manire dont les deux variantes construisent le graphe G recherch :

BNPC-A peut dtecter directement les diffrentes d-sparations du graphe chaque tapede sa construction et donc dfinir prcisment quels sont les diffrents ensembles desommets conditionnants devant tre pris en compte,

BNPC-B, en labsence dun ordre topologique correct sur le graphe G, se voit confrontau mme problme que les algorithmes PC et IC savoir la ncessit de tester un nombreexhaustif et donc exponentiel densembles de sommets conditionnants afin de pouvoirdterminer si deux sommets X et Y doivent tre ou non relis par une arte.

Pour rduire sa complexit, BNPC-B diminue considrablement le nombre des ensemblesde sommets conditionnants par lintermdiaire dune analyse quantitative des dpendancesrgnant au sein du graphe. Pour cela, les auteurs dfinissent lhypothse de la fidlitmonotone.

Dfinition 13 (Fidlit monotone) Soit ChemG(X,Y), lensemble des chemins reliant les sommets Xet Y dans un GOSC G = {V,E}. Soit ActG(X,Y|Z), lensemble des chemins de G activs par le sousensemble de sommets Z et reliant les sommets X et Y, {X,Y} < Z. Soit I(X,Y|Z) linformation mutuelleconditionnelle mesure entre les sommets X et Y conditionnellement Z. Alors G et la distribution deprobabilit P sous-jacente aux donnes dapprentissage so

Documents

A.delaplace.thesis