La lecture à portée de main
159
pages
Documents
2011
Écrit par
Christel Vrain
Publié par
profil-feym-2012
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
159
pages
Ebook
2011
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Publié par
Publié le
01 novembre 2011
Nombre de lectures
102
Poids de l'ouvrage
3 Mo
Publié par
Publié le
01 novembre 2011
Nombre de lectures
102
Poids de l'ouvrage
3 Mo
UNIVERSITÉ D’ORLÉANS
ÉCOLE DOCTORALE SCIENCES ET TECHNOLOGIES
Laboratoire d’Informatique Fondamentale d’Orléans
THÈSE
présentée par :
Quang-Thang DINH
soutenue le : 28 novembre 2011
pour obtenir le grade de : Docteur de l’Université d’Orléans
Discipline/ Spécialité : Informatique
Apprentissage Statistique Relationnel :
Apprentissage de Structures
de Réseaux de Markov Logiques
THÈSE dirigée par :
Christel Vrain Professeur, Université d’Orléans
Matthieu Exbrayat Maître de Conférences, Université d’Orléans
RAPPORTEURS :
Céline Rouveirol Professeur, Université Paris 13, France
Lorenza Saitta Université Piémont Oriental, Italie
JURY :
Matthieu Exbrayat Maître de Conférences, Université d’Orléans
Patrick Gallinari Professeur, Université Pierre et Marie Curie
Philippe Leray Université de Nantes, Président du jury
Céline Rouveirol Professeur, Université Paris 13
Lorenza Saitta Université Piémont Oriental
Christel Vrain Professeur, Université d’OrléansContents
1 Introduction 7
1.1 Dissertation Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Statistical Relational Learning 11
2.1 Probabilistic Graphical Models . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.1 Bayesian Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.2 Markov Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 First-Order Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Inductive Logic Programming . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 Statistical Relational Learning. . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.1 Probabilistic Relational Models . . . . . . . . . . . . . . . . . . . . 18
2.4.2 Bayesian Logic Programs . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.3 Relational Markov Networks . . . . . . . . . . . . . . . . . . . . . . 21
2.4.4 Markov Logic Networks . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Markov Logic Networks and Alchemy 25
3.1 Markov Logic Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.1 Weight Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.2 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.1.3 Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2 Alchemy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.1 Input files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2.2 Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2.3 Weight Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.4 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4 Learning MLN Structure Based on Propositionalization 41
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.2 The HGSM and HDSM Algorithms . . . . . . . . . . . . . . . . . . . . . . 43
4.2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2.2 Propositionalization Method . . . . . . . . . . . . . . . . . . . . . . 45
4.2.3 Structure of HGSM . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2.4 Evaluating . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.2.5 Structure of HDSM . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.2.6 Evaluating HDSM . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.3 The DMSP Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.3.2 Propositionalization Method . . . . . . . . . . . . . . . . . . . . . . 69
4.3.3 Structure of DMSP . . . . . . . . . . . . . . . . . . . . . . . . . . . 75ii Contents
4.3.4 Evaluating DMSP . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.4 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5 Learning MLN Structure Based on Graph of Predicates 83
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.2 The GSLP Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2.1 Graph of Predicates in GSLP . . . . . . . . . . . . . . . . . . . . . 85
5.2.2 Structure of GSLP . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.2.3 Experiments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.3 The Modified-GSLP Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 96
5.3.1 Graph of Predicates in M-GSLP . . . . . . . . . . . . . . . . . . . 98
5.3.2 Structure of M-GSLP . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3.3 Experiments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.3.4 Complexity of the M-GSLP Algorithm . . . . . . . . . . . . . . . . 104
5.4 The DSLP Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.4.1 Graph of Predicates in DSLP . . . . . . . . . . . . . . . . . . . . . 109
5.4.2 Structure of DSLP . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.4.3 Experiments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
5.5 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6 Conclusion and Future Work 117
6.1 Contributions of this Dissertation . . . . . . . . . . . . . . . . . . . . . . . 117
6.2 Directions for Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . 119
A Evaluation Metrics 125
A.1 Classifier Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
A.2 ROC and PR Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
A.3 Area Under the Curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
B Experimental Comparison to ILP 127
B.1 Systems and Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
B.2 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
B.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
C Clauses Learned by Discriminative Systems 137
Bibliography 141List of Figures
1 L’entrée et la sortie d’un système d’apprentissage de la structure d’un MLN 3
1.1 Input and output of a MLN structure learner . . . . . . . . . . . . . . . . 8
2.1 Example of a Bayesian network . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 of a graph structure of a MLN . . . . . . . . . . . . . . . . . . . 14
2.3 An instantiation of the relational schema for a simple movie domain . . . 19
2.4 An example of a BLP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1 Example of a ground MN . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.1 Propositionalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2 Example of chains in the variabilization process of HGSM . . . . . . . . . 47
4.3 of adding new variable in HGSM . . . . . . . . . . . . . . . . . . 49
4.4 Example of g-chains in DMSP . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.5 of g-links in DMSP . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.6 Example of the variabilization in DMSP . . . . . . . . . . . . . . . . . . . 73
4.7 of the v processes in DMSP and HDSM . . . . . . . 76
5.1 Example of graph of predicates in GSLP . . . . . . . . . . . . . . . . . . . 87
5.2 of graph of in M-GSLP . . . . . . . . . . . . . . . . . 98
5.3 Example of graph of predicates in DSLP . . . . . . . . . . . . . . . . . . . 109
B.1 Results for the predicate WorkedUnder in IMDB . . . . . . . . . . . . . . 131
B.2 for the AdvisedBy in UW-CSE . . . . . . . . . . . . . . . 132
B.3 Results for the predicate SameAuthor in CORA . . . . . . . . . . . . . . . 133
B.4 for the SameBib in CORA . . . . . . . . . . . . . . . . . 134
B.5 Results for the predicate SameTitle in CORA . . . . . . . . . . . . . . . . 135
B.6 for the SameVenue in . . . . . . . . . . . . . . . 136List of Tables
3.1 example.mln: An .mln input file in Alchemy . . . . . . . . . . . . . . . . . 38
4.1 Example of several rows in a boolean table of HGSM . . . . . . . . . . . . 52
4.2 Details of the IMDB, UW-CSE and CORA datasets . . . . . . . . . . . . 58
4.3 CLL, AUC-PR measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.4 Number of clauses and runtimes (minutes) . . . . . . . . . . . . . . . . . . 60
4.5 CLL, AUC-PR measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.6 Runtimes(hour) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.7 CLL, AUC-PR measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.8 Runtimes(hours) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.1 A path of four edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92<