ÉCOLE DOCTORALE SCIENCES ET TECHNOLOGIES

Christel Vrain

Description

Niveau: Supérieur, Doctorat, Bac+8

• dissertation

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 Professeur, 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 Professeur, Université de Nantes, Président du jury Céline Rouveirol Professeur, Université Paris 13 Lorenza Saitta Professeur, Université Piémont Oriental Christel Vrain Professeur, Université d'Orléans

• apprentissage de structures


• evaluating hdsm


• système d'apprentissage de la structure


• statistical relational


• quang-thang dinh soutenue


• markov logic


• structure learning

Sujets

• Dissertation
• Organization
• Fundraising
• Exbrayat
• Université de Nantes

Informations

• Publié par: profil-feym-2012
• Publié le: 01 novembre 2011
• Nombre de lectures: 102
• Poids de l'ouvrage: 3 Mo

Extrait

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<