Search improvements in multirelational learning [Elektronische Ressource] / von Maria de Lourdes Peña Castillo

Lourdes Peña Castillo

Sujets

• Informatik

Informations

• Publié par: otto-von-guericke-universitat_magdeburg
• Publié le: 01 janvier 2004
• Nombre de lectures: 21
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Search Improvements in
Multirelational Learning
Dissertation
zur Erlangung des akademischen Grades
Doktoringenieurin
(Dr.-Ing.)
angenommen durch der Fakultat fur Informatik
der Otto-von-Guericke-Universitat Magdeburg
von M. Sc. Mara de Lourdes Pen˜a Castillo
geboren am 02.Mai1974 in Mexico, D.F.
Gutachter: Prof.Dr. Stefan Wrobel
Prof.Dr. Stefan Kramer
Prof.Dr. Andreas Nurnberger
Magdeburg, den 7. June 2004Abstract
In this thesis we lay the foundations to develop multirelational learning systems
which can cope better with the challenges posed by structural and topological
domains. Even though many interesting application domains contain structural
or topological data, current multirelational systems have diculties dealing with
the complexity of the search space of theses domains, their indeterminacy, and
the presence of non-discriminating relations. In this work, we describe macro-
operators which are a formal method to reduce the search space explored in
structural or topological domains and can also be used to alleviate the myopia
of greedy systems. We also explore parallel search based on stochastically se-
lected examples to reduce the instability of example-driven learning. As a third
contribution, we present active inductive learning as an approach to improve the
e ciency of the instance space exploration.Zusammenfassung
Diese Dissertation legt die Grundlage zur Entwicklung multirelationaler Lern-
verfahren, die strukturelle und topologische Anwendungsbereiche erfolgreich
bearbeiten konnen. Obwohl viele gangige Anwendungsbereiche strukturelle und
topologische Daten enthalten, ist es fur herkommliche multirelationale Lernver-
fahren schwierig, diese Lernaufgabe zu bewaltigen. Das liegt an der Komplex-
itat ihres Suchraums, an ihrer Unbestimmtheit und an den vorliegenden nicht-
diskriminierendenRelationen.DieseArbeitstelltdieMethodenmacro-operators,
Parallel-Suche und aktives induktives Lernen vor. Macro-operators sind eine
formale Methode, um den Suchraum in den erwahnten Anwendungsbereichen
einzuschranken. Zudem sind macro-operators geeignet zur Verringerung der
Kurzsichtigkeit von auf gieriger Suche basierenden Systemen. Durch die Anwen-
dungderParallel-Suche,dieaufzufalligausgewahltenBeispielenbasiert,kanndie
Stabilitat von example-driven Verfahren verbessert werden. Aktives induktives
Lernen ist eine Methode, die eine e zientere Erforschung des Instanzenraums
ermoglicht.Acknowledgments
Although a Ph.D. dissertation is usually seen as the result of a long, dedicated,
individual research work, there are many people besides the author who con-
tribute to the completion of it. In my case, I want to thank in this page all those
who directly or indirectly help me to nish this work.
Specially, I would like to thank
Stefan Wrobel for his guidance, support and supervision.
Stefan Kramer and Andreas Nurnberger for reviewing this thesis.
The members of the Institute for Knowledge and Language Processing for
providing a friendly working environment.
All the friends who made my stay in Magdeburg a lot more enjoyable and
the departure a lot more dicult, I feel really honour to have the fortune
of sharing with you so many memories.
My family for always believing in me and for their unconditional love.
My partner in this adventure, Oscar Meruvia, for all we have constructed
together, being who he is, and his involvement in my work.
??????Contents
1 Introduction 1
1.1 Why a Relational Data Representation? . . . . . . . . . . . . . . 2
1.2 Challenges of Structural/Topological Domains . . . . . . . . . . . 4
1.3 Thesis Contributions . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Logic Programming for ILP 9
2.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Programming Aspects . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3 Learning and Search in Multirelational Learning 17
3.1 Learning in ILP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.1.1 Learning Task . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1.2 Re nement Operators . . . . . . . . . . . . . . . . . . . . 20
3.1.3 Covering Algorithm . . . . . . . . . . . . . . . . . . . . . . 22
3.2 Search in Multirelational Learning . . . . . . . . . . . . . . . . . . 25
3.2.1 Breadth- rst. . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2.2 IDA* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2.3 Hill-Climbing . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.4 Beam-search . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3 Multirelational Learning Systems . . . . . . . . . . . . . . . . . . 28
3.3.1 Progol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.2 TILDE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.3 FOIL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3.4 RIBL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3.5 ALEPH . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3.6 ICL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3.7 FOIDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
ivContents
4 A Basic Approach for ILP 33
4.1 Mode Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.2 Bottom Clause . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.3 Literal-Based Re nement Operator . . . . . . . . . . . . . . . . . 39
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5 Macro-operators 42
5.1 Reducing the Search Space . . . . . . . . . . . . . . . . . . . . . . 43
5.2 Macro-based Method . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.2.1 Macros’ Ordering . . . . . . . . . . . . . . . . . . . . . . . 46
5.2.2 Macro-based Re nement Operator . . . . . . . . . . . . . 47
5.3 Macros’ Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.3.1 Correctness of the Algorithms . . . . . . . . . . . . . . . . 51
5.3.2 Completeness of the Algorithms . . . . . . . . . . . . . . . 52
5.3.3 Identifying the Dependent Providers . . . . . . . . . . . . 53
5.3.4 Mio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.4 Empirical Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.4.1 Application Domains . . . . . . . . . . . . . . . . . . . . . 55
5.4.2 Experiment Design . . . . . . . . . . . . . . . . . . . . . . 56
5.4.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.5 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6 Hill-Climbing Search Using Macros 62
6.1 A Hill-Climbing Search Algorithm . . . . . . . . . . . . . . . . . . 63
6.2 Myopia of Hill-Climbing: An Example . . . . . . . . . . . . . . . 65
6.3 How Macros Alleviate the Myopia of Hill-Climbing . . . . . . . . 67
6.4 Empirical Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 68
6.4.1 Comparing Macros with Template-based Lookahead and
Determinate Literals . . . . . . . . . . . . . . . . . . . . . 68
6.4.2 Comparing Macros with Fixed-depth Lookahead and
Beam-Search . . . . . . . . . . . . . . . . . . . . . . . . . 70
6.4.3 Results Summary . . . . . . . . . . . . . . . . . . . . . . . 72
6.5 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
7 Improving the Stability of Example-driven Learning 75
7.1 Stability in Example-driven Learning . . . . . . . . . . . . . . . . 76
7.2 Enhancing the Stability of Example-Driven Learning . . . . . . . 78
7.3 Empirical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
7.4 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
vContents
8 Learning Minesweeper with ILP 85
8.1 Minesweeper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
8.1.1 Why Is Minesweeper Interesting? . . . . . . . . . . . . . . 87
8.1.2 Minesweeper as a Learning Task for ILP . . . . . . . . . . 88
8.2 Actively Exploring the Instance-Space . . . . . . . . . . . . . . . 89
8.3 Background Knowledge . . . . . . . . . . . . . . . . . . . . . . . . 90
8.4 Empirical Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 92
8.4.1 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
8.4.2 Theory Learned . . . . . . . . . . . . . . . . . . . . . . . . 95
8.4.3 Game Playing . . . . . . . . . . . . . . . . . . . . . . . . . 97
8.4.4 Experiments with Other ILP Systems . . . . . . . . . . . . 97
8.5 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
8.5.1 Minesweeper Playing Programs . . . . . . . . . . . . . . . 98
8.5.2 Multirelational Learning for Games . . . . . . . . . . . . . 99
8.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
9 Conclusions and Future Work 101
9.1 Contributions Summary