these
151 pages
Français
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
151 pages
Français
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

´ ´UNIVERSITE DE MARNE-LA-VALLEE`THESEpour obtenir le grade de´ ´DOCTEUR DE L’UNIVERSITE DE MARNE-LA-VALLEESp´ecialit´e : Math´ematiques Appliqu´ees et Applications des Math´ematiquespr´esent´ee et soutenue publiquement parLinda Smaille 30 Avril 2004TitreAlgorithmique pour les R´eseauxBay´esiens et leurs ExtensionsDirecteur de th`ese : Jean Pierre RaoultJury :Rapporteurs : Marc Bouissou, EDF. R et DEvelyne Flandrin, Univ. Paris 5Eric Moulines, ENSTExaminateurs : Wenceslas Fernandez de La Vega, Univ. Paris-SudKamel Mekhnacha, INRIA Rhˆone AlpesPaul Munteanu, ESIEAGeorges Oppenheim, Univ. Marne-la-Vall´eeJean Pierre Raoult, Univ. Marne-la-Vall´eeA l’esprit de mon cher p`ere.Remerciements.Je tiens particuli`erement `a exprimer ma reconnaissance `a Jean-Pierre Raoult, mon di-recteur de th`ese, pour sa disponibilit´e, son ´ecoute et ses conseils, qui m’ont ´et´e toujourspr´ecieux, sa confiance, son investissement scientifique et humain qui ont ´et´e essentiels `a lar´ealisation de ce travail.Je voudrais ´egalement exprimer toute ma gratitude aux professeurs Eric Moulines etEvelyne Flandrin qui, en leur qualit´e de rapporteurs, m’ont fait l’honneur d’examinerminutieusement ce travail.Les discussions que j’ai eues avec Georges Oppenheim et Marc Bouissou tout au longde ma th`ese ont ´et´e particuli`erement enrichissantes, je leur en suis reconnaissante et lesremercie d’avoir accept´e de faire partie du jury de ma th`ese.A Kamel Mekhnacha j’adresse ...

Informations

Publié par
Nombre de lectures 88
Langue Français

Extrait

´ ´UNIVERSITE DE MARNE-LA-VALLEE
`THESE
pour obtenir le grade de
´ ´DOCTEUR DE L’UNIVERSITE DE MARNE-LA-VALLEE
Sp´ecialit´e : Math´ematiques Appliqu´ees et Applications des Math´ematiques
pr´esent´ee et soutenue publiquement par
Linda Smail
le 30 Avril 2004
Titre
Algorithmique pour les R´eseaux
Bay´esiens et leurs Extensions
Directeur de th`ese : Jean Pierre Raoult
Jury :
Rapporteurs : Marc Bouissou, EDF. R et D
Evelyne Flandrin, Univ. Paris 5
Eric Moulines, ENST
Examinateurs : Wenceslas Fernandez de La Vega, Univ. Paris-Sud
Kamel Mekhnacha, INRIA Rhˆone Alpes
Paul Munteanu, ESIEA
Georges Oppenheim, Univ. Marne-la-Vall´ee
Jean Pierre Raoult, Univ. Marne-la-Vall´eeA l’esprit de mon cher p`ere.Remerciements.
Je tiens particuli`erement `a exprimer ma reconnaissance `a Jean-Pierre Raoult, mon di-
recteur de th`ese, pour sa disponibilit´e, son ´ecoute et ses conseils, qui m’ont ´et´e toujours
pr´ecieux, sa confiance, son investissement scientifique et humain qui ont ´et´e essentiels `a la
r´ealisation de ce travail.
Je voudrais ´egalement exprimer toute ma gratitude aux professeurs Eric Moulines et
Evelyne Flandrin qui, en leur qualit´e de rapporteurs, m’ont fait l’honneur d’examiner
minutieusement ce travail.
Les discussions que j’ai eues avec Georges Oppenheim et Marc Bouissou tout au long
de ma th`ese ont ´et´e particuli`erement enrichissantes, je leur en suis reconnaissante et les
remercie d’avoir accept´e de faire partie du jury de ma th`ese.
A Kamel Mekhnacha j’adresse des remerciements particuliers pour toutes les questions
pertinentes qu’il a su me poser et les discussions fructueuses que nous avons eues, et qui
ont particip´e `a l’enrichissement de ce travail. Sa pr´esence dans mon jury de th`ese me fait
tr`es plaisir,toutcommecelledePaulMunteanu,etaussiWenceslas FernandezdeLaVega,
que je remercie sinc`erement pour le regard attentif qu’ils ont port´e sur mon travail.
Je tiens aussi `a remercier pour son accueil toute l’´equipe du laboratoire d’Analyse et
Math´ematiques Appliqu´ees de l’universit´e de Marne-la-Vall´ee, ou` j’ai effectu´e cette th`ese.
En particulier j’exprime ma gratitude `a tous les membres du groupe de travail de fia-
bilit´e : Christiane Cocozza, Sophie Mercier et Michel Roussignol, pour leurs conseils et
encouragements.
Je remercie ´egalement Emmanuel Mazer et Kamel Mekhnacha de l’´equipe Laplace, lo-
calis´ee `a INRIA Rhˆone Alpes, pour leur accueil, les longues journ´ees de travail et les
multiples discussions qui m’ont aid´ee dans mes travaux.
Tous ceuxquiontprisdeleurtempspourunelectureattentive etm’ontapport´eleursre-
marques et judicieux conseils :Karim Mennas,Yannick Lefebvre, Wahid Boukraa, Margot
Desgrouas. A chacun, toute ma gratitude.
Un grand merci ´egalement a` Mireille Morvan, pour sa gentillesse et son aide.
Enfin,jeremercietoutemafamilleettoutparticuli`erementmam`ere,dem’avoirsoutenue
et encourag´ee, et ma sœur Nabila pour son aide dans les moments difficiles.Table des mati`eres
1 Pr´esentation des R´eseaux Bay´esiens et R´eseaux Bay´esiens de Niveau
Deux 16
1.1 R´eseaux bay´esiens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.1.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.1.2 D´efinition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.1.3 Probabilit´e d´efinie par un r´eseau bay´esien . . . . . . . . . . . . . . . 17
1.1.4 Interpr´etation en termes de variables al´eatoires et de lois condition-
nelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.1.5 Commentaire et g´en´eralisation . . . . . . . . . . . . . . . . . . . . . 22
1.1.6 Compl´ement sur l’ind´ependance conditionnelle . . . . . . . . . . . . 23
1.1.7 Exemple d’un r´eseau bay´esien . . . . . . . . . . . . . . . . . . . . . . 25
1.2 R´eseaux Bay´esiens de niveau deux . . . . . . . . . . . . . . . . . . . . . . . 28
1.2.1 Besoin d’une notion nouvelle . . . . . . . . . . . . . . . . . . . . . . 28
1.2.2 D´efinition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.2.3 Lien avec les r´eseaux bay´esiens orient´es objets. . . . . . . . . . . . . 31
2 Propri´et´es de S´eparation dans les R´eseaux Bay´esiens 36
2.1 S´eparation dans un graphe non-orient´e (I,H) . . . . . . . . . . . . . . . . . 36
2.1.1 D´efinition et th´eor`eme fondamental. . . . . . . . . . . . . . . . . . . 36
2.1.2 Partition S-conditionnelle pour un graphe non orient´e . . . . . . . . 39
2.2 D-s´eparation dans un graphe orient´e sans circuits . . . . . . . . . . . . . . . 40
2.2.1 Graphe moral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.2.2 Chaˆıne dans un graphe orient´e. . . . . . . . . . . . . . . . . . . . . . 42
2.2.3 Blocage, d-s´eparation . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.2.4 Couverture et fronti`ere de Markov . . . . . . . . . . . . . . . . . . . 47
2.2.5 Partition S-conditionnelle pour un r´eseau bay´esien . . . . . . . . . . 47
2.3 Factorisation des calculs de lois et lois conditionnelles . . . . . . . . . . . . 50
42.3.1 Factorisation du calcul de P . . . . . . . . . . . . . . . . . . . . . 50¯S/S
2.3.2 Factorisation de calcul de P . . . . . . . . . . . . . . . . . . . . . . 52S
3 Techniques de Construction d’Arbres de Jonction. Applications aux cal-
culs dans les R´eseaux Bay´esiens 56
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.1.1 Contexte et annonce du r´esultat fondamental . . . . . . . . . . . . . 57
3.1.2 Principe du calcul de familles de lois X (ou` K⊆I) . . . . . . . . . 58K
3.1.3 Calcul de lois conditionnelles . . . . . . . . . . . . . . . . . . . . . . 58
3.1.4 Application aux r´eseaux bay´esiens et r´eseaux bay´esiens de niveau 2 . 59
3.1.5 Analyse critique de la m´ethode . . . . . . . . . . . . . . . . . . . . . 59
3.1.6 Plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.2 Arbres de jonction et suites recouvrantes propres P.I.C. . . . . . . . . . . . 60
3.2.1 Rappels : Arbre, arborescence, num´erotation topologique d’un arbre 60
3.2.2 Arbres de jonction - S´eparateurs . . . . . . . . . . . . . . . . . . . . 61
3.2.3 Suite recouvrante propre P.I.C. . . . . . . . . . . . . . . . . . . . . . 63
3.2.4 Lien entre les arbres de jonction et la P.I.C. . . . . . . . . . . . . . . 63
3.3 Deux m´ethodes de construction d’un arbre de jonction . . . . . . . . . . . . 66
3.3.1 M´ethode par moralisation et triangularisation . . . . . . . . . . . . . 66
3.3.2 M´ethode parconstruction r´ecurrente d’unesuiterecouvrante propre
P.I.C. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.4 Calcul de lois de sous-familles dans le cadre de la loi d’une famille de va-
riables al´eatoires compatible avec un arbre de jonction (algorithme LS) . . . 86
3.4.1 Pr´esentation de la m´ethode . . . . . . . . . . . . . . . . . . . . . . . 86
3.4.2 Premi`ere phase, dans le cas particulier ´el´ementaire ou` k = 2 . . . . . 87
3.4.3 Pr´esentation de la premi`ere phase du calcul, de l’algorithme dans le
cas g´en´eral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.4.4 Justification de la premi`ere phase du calcul de l’algorithme . . . . . 90
3.4.5 D´eroulement de la premi`ere phase du calcul de l’algorithme . . . . . 93
3.4.6 Deuxi`eme phase du calcul . . . . . . . . . . . . . . . . . . . . . . . . 93
3.4.7 Rˆole de l’hypoth`ese de propret´e de la suite P.I.C. (C ) . . . . . 94j 1≤j≤k
3.4.8 Terminologie informatique . . . . . . . . . . . . . . . . . . . . . . . . 94
3.4.9 Etude d’un exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4 Algorithme des Restrictions Successives 99
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.2 Calcul des lois marginales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
54.2.1 Descendance proche . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.2.2 Exemple introductif a` l’algorithme . . . . . . . . . . . . . . . . . . . 101
4.2.3 Algorithme des restrictions successives version 1 . . . . . . . . . . . 103
4.2.4 Principe de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . 103
4.2.5 Justification de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . 106
4.2.6 Evaluationdenombred’op´erations´el´ementaires dansled´eroulement
de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.2.7 G´en´eralisation facile et importante . . . . . . . . . . . . . . . . . . . 107
4.3 Calcul des lois conditionnelles . . . . . . . . . . . . . . . . . . . . . . . . . . 108
4.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
4.3.2 Exemple introductif `a l’algorithme . . . . . . . . . . . . . . . . . . . 109
4.3.3 Algorithme des

  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents