Logical And Relational Learning

by De Raedt, Luc

• ISBN13: 9783540200406
• ISBN10: 3540200401
• Format: Hardcover
• Copyright: 2008-10-04
• Publisher: Springer-Verlag New York Inc

Summary

This textbook covers logical and relational learning in depth, and hence provides an introduction to inductive logic programming (ILP), multirelational data mining (MRDM) and (statistical) relational learning (SRL). These subfields of data mining and machine learning are concerned with the analysis of complex and structured data sets that arise in numerous applications, such as bio- and chemoinformatics, network analysis, Web mining, natural language processing, within the rich representations offered by relational databases and computational logic.The author introduces the machine learning and representational foundations of the field and explains some important techniques in detail by using some of the classic case studies centered around well-known ILP, MRDM and SRL systems. The book is suitable for use in graduate courses and should be of interest to graduate students and researchers in computer science, databases and artificial intelligence, as well as practitioners of data mining and machine learning. It contains numerous figures and exercises, and slides are available for many chapters.

Table of Contents

Introduction	p. 1
What Is Logical and Relational Learning?	p. 1
Why Is Logical and Relational Learning Important?	p. 2
Structure Activity Relationship Prediction	p. 3
A Web Mining Example	p. 5
A Language Learning Example	p. 7
How Does Relational and Logical Learning Work?	p. 8
A Brief History	p. 11
An Introduction to Logic	p. 17
A Relational Database Example	p. 17
The Syntax of Clausal Logic	p. 20
The Semantics of Clausal Logic - Model Theory	p. 22
Inference with Clausal Logic - Proof Theory	p. 28
Prolog and SLD-resolution	p. 35
Historical and Bibliographic Remarks	p. 39
An Introduction to Learning and Search	p. 41
Representing Hypotheses and Instances	p. 41
Boolean Data	p. 43
Machine Learning	p. 44
Data Mining	p. 45
A Generate-and-Test Algorithm	p. 47
Structuring the Search Space	p. 48
Monotonicity	p. 50
Borders	p. 53
Refinement Operators	p. 56
A Generic Algorithm for Mining and Learning	p. 58
A Complete General-to-Specific Algorithm	p. 59
A Heuristic General-to-Specific Algorithm	p. 60
A Branch-and-Bound Algorithm	p. 62
A Specific-to-General Algorithm	p. 63
Working with Borders*	p. 64
Computing a Single Border	p. 64
Computing Two Borders	p. 65
Computing Two Borders Incrementally	p. 66
Operations on Borders	p. 68
Conclusions	p. 69
Bibliographical Notes	p. 69
Representations for Mining and Learning	p. 71
Representing Data and Hypotheses	p. 71
Attribute-Value Learning	p. 73
Multiple-Instance Learning: Dealing With Sets	p. 76
Relational Learning	p. 79
Logic Programs	p. 84
Sequences, Lists, and Grammars	p. 85
Trees and Terms	p. 87
Graphs	p. 89
Background Knowledge	p. 91
Designing It Yourself	p. 95
A Hierarchy of Representations*	p. 97
From AV to BL	p. 99
From MI to AV	p. 100
From RL to MI	p. 102
From LP to RL	p. 103
Propositionalization	p. 106
A Table-Based Approach	p. 106
A Query-Based Approach	p. 108
Aggregation	p. 109
Conclusions	p. 112
Historical and Bibliographical Remarks	p. 113
Generality and Logical Entailment	p. 115
Generality and Logical Entailment Coincide	p. 115
Propositional Subsumption	p. 118
Subsumption in Logical Atoms	p. 119
Specialization Operators	p. 121
Generalization Operators*	p. 123
Computing the lgg and the glb	p. 125
[Theta]-Subsumption	p. 127
Soundness and Completeness	p. 128
Deciding [Theta]-Subsumption	p. 128
Equivalence Classes	p. 131
Variants of [Theta]-Subsumption*	p. 135
Object Identity*	p. 135
Inverse Implication*	p. 137
Using Background Knowledge	p. 138
Saturation and Bottom Clauses	p. 139
Relative Least General Generalization*	p. 141
Semantic Refinement*	p. 143
Aggregation*	p. 145
Inverse Resolution	p. 147
A Note on Graphs, Trees, and Sequences	p. 152
Conclusions	p. 154
Bibliographic Notes	p. 154
The Upgrading Story	p. 157
Motivation for a Methodology	p. 157
Methodological Issues	p. 159
Representing the Examples	p. 159
Representing the Hypotheses	p. 160
Adapting the Algorithm	p. 161
Adding Features	p. 161
Case Study 1: Rule Learning and Foil	p. 161
Foil's Problem Setting	p. 162
Foil's Algorithm	p. 164
Case Study 2: Decision Tree Learning and Tilde	p. 168
The Problem Setting	p. 168
Inducing Logical Decision Trees	p. 172
Case Study 3: Frequent Item-Set Mining and Warmr	p. 174
Relational Association Rules and Local Patterns	p. 174
Computing Frequent Queries	p. 177
Language Bias	p. 179
Syntactic Bias	p. 180
Semantic Bias	p. 183
Conclusions	p. 184
Bibliographic Notes	p. 184
Inducing Theories	p. 187
Introduction to Theory Revision	p. 188
Theories and Model Inference	p. 188
Theory Revision	p. 190
Overview of the Rest of This Chapter	p. 192
Towards Abductive Logic Programming	p. 193
Abduction	p. 193
Integrity Constraints	p. 194
Abductive Logic Programming	p. 196
Shapiro's Theory Revision System	p. 199
Interaction	p. 199
The Model Inference System	p. 203
Two Propositional Theory Revision Systems*	p. 208
Learning a Propositional Horn Theory Efficiently	p. 208
Heuristic Search in Theory Revision	p. 212
Inducing Constraints	p. 213
Problem Specification	p. 214
An Algorithm for Inducing Integrity Constraints	p. 215
Conclusions	p. 220
Bibliographic Notes	p. 220
Probabilistic Logic Learning	p. 223
Probability Theory Review	p. 224
Probabilistic Logics	p. 225
Probabilities on Interpretations	p. 226
Probabilities on Proofs	p. 232
Probabilistic Learning	p. 238
Parameter Estimation	p. 238
Structure Learning	p. 246
First-Order Probabilistic Logics	p. 247
Probabilistic Interpretations	p. 248
Probabilistic Proofs	p. 255
Probabilistic Logic Learning	p. 267
Learning from Interpretations	p. 267
Learning from Entailment	p. 270
Learning from Proof Trees and Traces	p. 271
Relational Reinforcement Learning*	p. 274
Markov Decision Processes	p. 274
Solving Markov Decision Processes	p. 277
Relational Markov Decision Processes	p. 280
Solving Relational Markov Decision Processes	p. 282
Conclusions	p. 287
Bibliographic Notes	p. 287
Kernels and Distances for Structured Data	p. 289
A Simple Kernel and Distance	p. 289
Kernel Methods	p. 291
The Max Margin Approach	p. 291
Support Vector Machines	p. 292
The Kernel Trick	p. 294
Distance-Based Learning	p. 296
Distance Functions	p. 296
The k-Nearest Neighbor Algorithm	p. 297
The k-Means Algorithm	p. 297
Kernels for Structured Data	p. 298
Convolution and Decomposition	p. 299
Vectors and Tuples	p. 299
Sets and Multi-sets	p. 300
Strings	p. 301
Trees and Atoms	p. 302
Graph Kernels*	p. 303
Distances and Metrics	p. 307
Generalization and Metrics	p. 308
Vectors and Tuples	p. 309
Sets	p. 310
Strings	p. 315
Atoms and Trees	p. 318
Graphs	p. 319
Relational Kernels and Distances	p. 321
Conclusions	p. 323
Bibliographical and Historical Notes	p. 323
Computational Aspects of Logical and Relational Learning	p. 325
Efficiency of Relational Learning	p. 325
Coverage as [theta]-Subsumption	p. 326
[theta]-Subsumption Empirically	p. 327
Optimizing the Learner for [theta]-subsumption	p. 328
Computational Learning Theory*	p. 333
Notions of Learnability	p. 334
Positive Results	p. 336
Negative Results	p. 338
Conclusions	p. 342
Historical and Bibliographic Notes	p. 342
Lessons Learned	p. 345
A Hierarchy of Representations	p. 345
From Upgrading to Downgrading	p. 346
Propositionalization and Aggregation	p. 346
Learning Tasks	p. 347
Operators and Generality	p. 347
Unification and Variables	p. 348
Three Learning Settings	p. 349
Knowledge and Background Knowledge	p. 350
Applications	p. 350
References	p. 351
Author Index	p. 375
Index	p. 381
Table of Contents provided by Ingram. All Rights Reserved.