Foundations of inductive logic programming
S.H. Nienhuys-Cheng, R. de Wolf - Collection Lecture Notes in Computer Science
404 pages, parution le 07/08/1997
Résumé
This text focuses on a young and rapidly growing field
combining machine learning and logic programming. This
self-contained tutorial is a theoretical introduction to
ILP and should provide the reader with a rigorous and
sufficiently broad basis for future research in the area.
In the first part, a thorough treatment of first-order
logic, resolution-based theorem proving, and logic
programming is given. The second part introduces the main
concepts of ILP and systematically develops the most
important results on model inference, inverse resolution,
unfolding, refinement operators, least generalizations, and
ways to deal with background knowledge. Furthermore, the
authors give an overview of PAC learning results in ILP and
of some of the most relevant implemented systems.
Table of contents :
About the Book XIII
I Logic 1
1 Propositional Logic 3
1.1 Introduction 3
1.2 Syntax 4
1.3 Semantics 5
1.3.1 Informally 5
1.3.2 Interpretations 7
1.3.3 Models 9
1.4 Conventions to Simplify Notation 15
1.5 Summary 15
2 First-Order Logic 17
2.1 Introduction 17
2.2 Syntax 18
2.3 Semantics 22
2.3.1 Informally 22
2.3.2 Interpretations 24
2.3.3 Models 29
2.4 Conventions to Simplify Notation 33
2.5 Summary 34
3 Normal Forms and Herbrand Models 35
3.1 Introduction 35
3.2 Prenex Conjunctive Normal Form 36
3.3 Skolem Standard Form 39
3.3.1 Clauses and Universal 39
Quantification
3.3.2 Standard Form 40
3.4 Herbrand Models 45
3.5 Results Concerning Herbrand Models 48
3.6 Summary 50
3.A Alternative Notation for Standard Forms 51
4 Resolution 55
4.1 Introduction 55
4.2 What Is a Proof Procedure? 57
4.3 Substitution and Unification 59
4.3.1 Substitution 59
4.3.2 Unification 63
4.4 An Informal Introduction to Resolution 65
4.5 A Formal Treatment of Resolution 68
4.6 Summary 73
5 Subsumption Theorem and Refutation 75
Completeness
5.1 Introduction 75
5.2 Deductions 77
5.3 The Subsumption Theorem 78
5.3.1 The Subsumption Theorem for Ground 78
XXX and C
5.3.2 The Subsumption Theorem when C is 79
Ground
5.3.3 The Subsumption Theorem (General 82
Case)
5.4 Refutation Completeness 84
5.4.1 From the Subsumption Theorem to 84
Refutation Completeness
5.4.2 From Refutation Completeness to 84
the Subsumption Theorem
5.5 Proving Non-Clausal Logical Implication 87
5.6 How to Find a Deduction 87
5.7 Summary 90
5.8 Alternative Definitions of Resolution 91
6 Linear and Input Resolution 93
6.1 Introduction 93
6.2 Linear Resolution 94
6.3 Refutation Completeness 95
6.4 The Subsumption Theorem 98
6.5 The Incompleteness of Input Resolution 100
6.6 Summary 103
7 SLD-Resolution 105
7.1 Introduction 105
7.2 SLD-Resolution 106
7.3 Soundness and Completeness 108
7.3.1 Refutation Completeness 108
7.3.2 The Subsumption Theorem 109
7.4 Definite Programs and Least Herbrand 111
Models
7.5 Correct Answers and Computed Answers 113
7.6 Computation Rules 119
7.7 SLD-Trees 122
7.8 Undecidability 125
7.9 Summary 126
8 SLDNF-Resolution 127
8.1 Introduction 127
8.2 Negation as Failure 130
8.3 SLDNF-Trees for Normal Programs 133
8.4 Floundering, and How to Avoid It 141
8.5 The Completion of a Normal Program 145
8.6 Soundness with Respect to the 150
Completion
8.7 Completeness 153
8.8 Prolog 154
8.8.1 Syntax 154
8.8.2 Prolog and SLDNF-Trees 155
8.8.3 The Cut Operator 157
8.9 Summary 159
II Inductive Logic Programming 161
9 What Is Inductive Logic Programming? 163
9.1 Introduction 163
9.2 The Normal Problem Setting for ILP 165
9.3 The Nonmonotonic Problem Setting 172
9.4 Abduction 173
9.5 A Brief History of the Field 174
9.6 Summary 177
10 The Framework for Model Inference 179
10.1 Introduction 179
10.2 Formalizing the Problem 180
10.2.1 Enumerations and the Oracle 180
10.2.2 Complete Axiomatizations and 182
Admissibility
10.2.3 Formal Statement of the Problem 184
10.3 Finding a False Clause by Backtracing 186
10.4 Introduction to Refinement Operators 191
10.5 The Model Inference Algorithm 192
10.6 Summary 195
11 Inverse Resolution 197
11.1 Introduction 197
11.2 The V-Operator 198
11.3 The W-Operator 203
11.4 Motivation for Studying Generality 205
Orders
11.5 Summary 205
12 Unfolding 207
12.1 Introduction 207
12.2 Unfolding 209
12.3 UDS Specialization 213
12.4 Summary 217
13 The Lattice and Cover Structure of Atoms 219
13.1 Introduction 219
13.2 Quasi-Ordered Sets 220
13.3 Quasi-Ordered Sets of Clauses 225
13.4 Atoms as a Quasi-Ordered Set 225
13.4.1 Greatest Specializations 227
13.4.2 Least Generalizations 227
13.5 Covers 232
13.5.1 Downward Covers 232
13.5.2 Upward Covers 234
13.6 Finite Chains of Downward Covers 234
13.7 Finite Chains of Upward Covers 237
13.8 Size 240
13.9 Summary 241
14 The Subsumption Order 243
14.1 Introduction 243
14.2 Clauses Considered as Atoms 243
14.3 Subsumption 245
14.4 Reduction 247
14.5 Inverse Reduction 249
14.6 Greatest Specializations 251
14.7 Least Generalizations 252
14.8 Covers in the Subsume Order 256
14.8.1 Upward Covers 256
14.8.2 Downward Covers 257
14.9 A Complexity Measure for Clauses 260
14.9.1 Size as Defined by Reynolds 260
14.9.2 A New Complexity Measure 261
14.10 Summary 262
15 The Implication Order 265
15.1 Introduction 265
15.2 Least Generalizations 266
15.2.1 A Sufficient Condition for the 267
Existence of an LGI
15.2.2 The LGI is Computable 274
15.3 Greatest Specializations 275
15.4 Covers in the Implication Order 277
15.5 Summary 278
16 Background Knowledge 279
16.1 Introduction 279
16.2 Relative Subsumption 281
16.2.1 Definition and Some Properties 281
16.2.2 Least Generalizations 285
16.3 Relative Implication 287
16.3.1 Definition and Some Properties 287
16.3.2 Least Generalizations 288
16.4 Generalized Subsumption 289
16.4.1 Definition and Some Properties 289
16.4.2 Least Generalizations 294
16.5 Summary 297
17 Refinement Operators 299
17.1 Introduction 299
17.2 Ideal Refinement Operators for Atoms 300
17.3 Non-Existence of Ideal Refinement 303
Operators
17.4 Complete Operators for Subsumption 305
17.4.1 Downward 305
17.4.2 Upward 306
17.5 Ideal Operators for Finite Sets 310
17.5.1 Downward 311
17.5.2 Upward 315
17.6 Optimal Refinement Operators 316
17.7 Refinement Operators for Theories 317
17.8 Summary 319
18 PAC Learning 321
18.1 Introduction 321
18.2 PAC Algorithms 322
18.3 Sample Complexity 324
18.4 Time Complexity 326
18.4.1 Representations 326
18.4.2 Polynomial Time PAC Learnability 328
18.5 Some Related Settings 329
18.5.1 Polynomial Time PAC Predictability 329
18.5.2 Membership Queries 330
18.5.3 Identification from Equivalence 330
Queries
18.5.4 Learning with Noise 331
18.6 Results in the Normal ILP Setting 332
18.6.1 The Normal ILP Setting in PAC 333
Terms
18.6.2 Learning Non-recursive Programs 335
18.6.3 Learning Recursive Programs 338
18.7 Results in the Nonmonotonic Setting 340
18.8 Summary 341
18.A A Polynomial Time Decision Procedure 342
19 Further Topics 345
19.1 Introduction 345
19.2 Language Bias 346
19.3 Predicate Invention 347
19.4 Flattening 350
19.5 Imperfect Data 352
19.6 Implementation and Application 354
19.7 What Has Not Been Covered 358
19.8 Summary 359
19.A A Results for Flattening 360
List of Symbols 365
Bibliography 369
Author Index 391
Subject Index 395
Caractéristiques techniques
| PAPIER | |
| Éditeur(s) | Springer |
| Auteur(s) | S.H. Nienhuys-Cheng, R. de Wolf |
| Collection | Lecture Notes in Computer Science |
| Parution | 07/08/1997 |
| Nb. de pages | 404 |
| EAN13 | 9783540629276 |
Avantages Eyrolles.com
Livraison à partir de 0,01 € en France métropolitaine
Paiement en ligne SÉCURISÉ
Livraison dans le monde
Retour sous 15 jours
+ d'un million et demi de livres disponibles
Consultez aussi
- Les meilleures ventes en Graphisme & Photo
- Les meilleures ventes en Informatique
- Les meilleures ventes en Construction
- Les meilleures ventes en Entreprise & Droit
- Les meilleures ventes en Sciences
- Les meilleures ventes en Littérature
- Les meilleures ventes en Arts & Loisirs
- Les meilleures ventes en Vie pratique
- Les meilleures ventes en Voyage et Tourisme
- Les meilleures ventes en BD et Jeunesse
