Inductive Logic Programming: 12th International Conference, ILP 2002, Sydney, Australia, July 9-11, 2002, Revised Papers

✍ Scribed by Stan Matwin (editor), Claude Sammut (editor)

• Publisher: Springer
• Year: 2003
• Tongue: English
• Leaves: 361
• Series: Lecture Notes in Computer Science; 2583
• Category: Library

✦ Synopsis

The Twelfth International Conference on Inductive Logic Programming was held in Sydney, Australia, July 9–11, 2002. The conference was colocated with two other events, the Nineteenth International Conference on Machine Learning (ICML2002) and the Fifteenth Annual Conference on Computational Learning Theory (COLT2002). Startedin1991,InductiveLogicProgrammingistheleadingannualforumfor researchers working in Inductive Logic Programming and Relational Learning. Continuing a series of international conferences devoted to Inductive Logic Programming and Relational Learning, ILP 2002 was the central event in 2002 for researchers interested in learning relational knowledge from examples. The Program Committee, following a resolution of the Community Me- ing in Strasbourg in September 2001, took upon itself the issue of the possible change of the name of the conference. Following an extended e-mail discussion, a number of proposed names were subjected to a vote. In the ?rst stage of the vote, two names were retained for the second vote. The two names were: Ind- tive Logic Programming, and Relational Learning. It had been decided that a 60% vote would be needed to change the name; the result of the vote was 57% in favor of the name Relational Learning. Consequently, the name Inductive Logic Programming was kept.

✦ Table of Contents

Inductive Logic Programming
Preface
Organization
Table of Contents
Propositionalization for Clustering Symbolic Relational Descriptions
1 Introduction
2 Organizing Propositionalized Relational Data
2.1 A Graphical Representation of Relational Data
2.2 Organizing Data in a Generalization Space
2.3 COING: A Practical Approach for Buildinga Generalization Space of Relational Descriptions
2.4 The Generalization Space Representation Language and Related Work
3 Using Abstract Relations to Cluster Relational Data
3.1 Abstract Relations
3.2 Abstract Relations Based on Canonical Graphs
3.3 Propositionalizing Graphs into Arcs Using Abstract Relations
4 KIDS: An Algorithm to Cluster Relational Data Based on Abstract Relations
4.1 Principle of an Iterative Algorithm to Enrich the GS
4.2 Enriching the Description of the GS Nodes
4.3 KIDS Algorithm
4.4 Example of a KIDS Generalization Space
4.5 Algorithmic Complexity and Maximum Level of Abstraction
5 Experiments on Chinese Characters
5.1 Description of Chinese Characters as Relational Data
5.2 Results and Discussion
6 Conclusion
Efficient and Effective Induction of First Order Decision Lists
1 Introduction
2 Background
2.1 First-Order Decision Lists
2.2 The FOIDL Algorithm
2.3 CLOG
3 BUFOIDL
3.1 Clause Construction
3.2 Building the Decision List
4 Experimental Evaluation
4.1 Experimental Design
4.2 Experimental Results
4.3 Discussion
5 Related Work
6 Conclusions and Future Directions
References
Learning with Feature Description Logics
1 Introduction
2 The Learning Framework
2.1 Feature Description Logic
2.2 Concept Graphs
2.3 Feature Generating Functions
3 Experiments and Results
3.1 Learning Kinship Relations
3.2 Mutagenesis
3.3 Results and Discussion
4 Conclusion
References
An Emperical Evaluation of Bagging in Inductive Logic Programming
1 Introduction
2 Ensembles
3 Methodology
3.1 Benchmark Datasets
4 Results
4.1 Carcinogenesis
4.2 Smuggling
4.3 Protein
5 Conclusions and Future Work
References
Kernels for Structured Data
1 Introduction
2 Kernel Methods
2.1 Classes of Kernels
2.2 Valid Kernels
2.3 Good Kernels
3 Knowledge Representation
4 Embedding Basic Terms in Linear Spaces
5 Adapting Kernels
6 Example Applications
6.1 East/West Challenge
6.2 Spatial Clustering
6.3 Drug Activity Prediction
7 Related Work
7.1 Kernels on Discrete Structures
7.2 Distances on Discrete Structures
8 Conclusions
References
Experimental Comparison of Graph-Based Relational Concept Learning with Inductive Logic Programming Systems
1 Introduction
2 Related Work
2.1 Conceptual Graphs
2.2 Subdue
3 Graph-Based Concept Learning
3.1 Substructure Evaluation
3.2 SubdueCL Algorithm
3.3 Relational Aspects of the Approach
4 Experiments
4.1 Artificial Domain
4.1.1 10-Fold Cross Validation
4.2 Comparison of SubdueCL with ILP Systems
4.2.1 Non-relational Domains
4.2.2 Relational Domains
5 Conclusion
References
Autocorrelation and Linkage Cause Bias in Evaluation of Relational Learners
1 Introduction
1.1 Statistical Analysis of Relational Data
1.2 Simple Random Partitioning
1.3 An Example of Test Set Bias
2 Linkage, Autocorrelation, and Overfitting
2.1 Concentrated Linkage
2.2 Correlation and Autocorrelation
3 Effects of Linkage, Autocorrelation, and Overfitting on Bias
3.1 Dependent Training and Test Sets
3.2 How Bias Varies with Autocorrelation, Linkage, and Overfitting
4 Subgraph Sampling
5 Subgraph Sampling Eliminates Bias
6 Conclusions and Future Work
References
Learnability of Description Logic Programs
1 Introduction
2 The Description Logic $mathcal{ALN}$
3 Induction of Description Logic Programs
3.1 The Relation between (Learning) Carin-$mathcal{ALN}$ and (I)DLP
3.2 The Relation between (I)LP and (I)DLP
3.3 Subsumption between DLP Clauses
3.4 Learning Carin-$mathcal{ALN}$
4 Applying the Results
4.1 Learning from Databases Using Closed World Assumption
4.2 Learning Mesh-Design in DLP
5 Summary and Outlook
References
1BC2: A True First-Order Bayesian Classifier
1 Introduction
2 Probability Distributions over Lists and Sets
2.1 Probability Distributions over Lists
2.2 Probability Distributions over Sets and Multisets
3 The {tt 1BC2}/ System
3.1 Data Representation
3.2 The {tt 1BC2}/ Algorithm
4 Experiments
4.1 Alzheimer's Disease
4.2 Mutagenesis
4.3 Diterpene Structure Elucidation
5 Concluding Remarks
References
RSD: Relational Subgroup Discovery through First-Order Feature Construction
1 Introduction
2 Background
2.1 Propositionalization through First-Order Feature Construction
2.2 Irrelevant Feature Elimination
2.3 Rule Induction Using the Covering Algorithm
2.4 The Weighted Relative Accuracy Heuristic
2.5 Probabilistic Classification
2.6 Area Under the ROC Curve Evaluation
3 Relational Subgroup Discovery
3.1 RSD First-Order Feature Construction
3.2 RSD Rule Induction Algorithm
4 Experimental Evaluation
4.1 Materials
4.2 Procedures
4.3 Results
5 Conclusions
References
Mining Frequent Logical Sequences with SPIRIT-LOG
1 Introduction
2 Related Work
3 Logical Sequence Mining
4 SPIRIT-LoG for Mining Frequent Logical Sequences
4.1 Generic Algorithm SPIRIT-LoG
4.2 SPIRIT-LoG(N)
4.3 SPIRIT-LoG(L)
4.4 SPIRIT-LoG(V)
4.5 SPIRIT-LoG(R)
5 Experimental Results
6 Conclusion
References
Using Theory Completion to Learn a Robot Navigation Control Program
1 Introduction
2 An Event Calculus Program to Control the Navigation of a Robot
2.1 The Event Calculus
2.2 An Event Calculus Program to Control a Robot's Navigation
3 Theory Completion in Inductive Logic Programming
3.1 Generating Abductive Explanation
3.2 Theory Completion with {tt ALECTO}hbox {}
4 An Experiment to Learn a Robot Navigation Control Program
4.1 Results
5 Discussion
6 Conclusions
References
Learning Structure and Parameters of Stochastic Logic Programs
1 Introduction
2 Stochastic Logic Programs
2.1 Syntax of SLPs
2.2 Proof for SLPs
3 Generalisation Model
4 Optimal Parameter Choice
4.1 General Case
4.2 Analytical Solution for Two Example Case
4.3 Iterative Numerical Method for $n$ Example Case
5 Discussion of Related Work
5.1 Learning PRMS
5.2 Learning SLPs
6 Conclusions and Further Work
References
A Novel Approach to Machine Discovery: Genetic Programming and Stochastic Grammars
1 Introduction
2 Symbolic Regression with Evolutionary Computation
2.1 Genetic Programming
2.2 Grammar-Based GP
2.3 Initialization in Grammar-Based GP
2.4 Distribution-Based Evolution
3 Stochastic Grammar-Based GP (SG-GP)
3.1 Overview
3.2 Scalar and Vectorial SG-GP
4 Experiment Goal
5 Experimental Validation
5.1 Test Problem
5.2 Experimental Setting
5.3 Experimental Results
5.4 Sensitivity Analysis
5.5 Resisting the Bloat
5.6 Identification and Generalization
6 Related Works
7 Conclusion
References
Revision of First-Order Bayesian Classifiers
1 Introduction
2 Background Knowledge
2.1 Bayesian Logic Program
2.2 FORTE
2.3 Structure Learning Algorithms
3 Revision of Bayesian Logic Program
3.1 RBLP Approximating Procedure
3.2 RBLP Maximization Procedure
4 Relationship to Other Frameworks
5 Conclusion
References
The Applicability to ILP of Results Concerning the Ordering of Binomial Populations
1 Introduction
2 Selecting the Best Binomial Population
2.1 Application to ILP
2.2 Comparison with the Agnostic PAC Bound
3 Empirical Evaluation
3.1 Materials and Method
3.2 Experimental Results
4 Concluding Remarks
References
1 An Upper Bound on the Probability of Wrong Selection
Compact Representation of Knowledge Bases in ILP
1 Introduction
2 Knowledge Base Graph
2.1 Hypergraphs
2.2 Structure
2.3 Examples
3 Representing the ${KBG}$ in Prolog
3.1 Defining Explicit Nodes
3.2 Defining $ {@mathrm {@mathcal Diff}} $ Hyperedges
3.3 Defining $ {@mathrm {@mathcal Comb}} $ Hyperedges
3.4 Defining Examples
4 Traversing the ${KBG}$
4.1 ILP Algorithm Interface
4.2 A Planning Problem
4.3 An Efficient Example Iterator
5 Experimental Evaluation
6 Conclusions
References
A Polynomial Time Matching Algorithm of Structured Ordered Tree Pattern for Data Mining from Semistructured Data
1 Introduction
2 Preliminaries -- Ordered Term Trees
3 A Polynomial Time Algorithm for Solving Membership Problem for ${cal OTT}_Lambda ^{,}$
3.1 C-Sets
3.2 A Data Structure for C-Sets
3.3 Subproblems
3.4 C-Set-Attaching Rules
3.5 How to Use C-Set-Attaching Rules
3.6 A Matching Algorithm
4 Implementation and Experimental Results
5 Conclusions
References
A Genetic Algorithms Approach to ILP
1 Introduction
2 Representation, Encoding and Operators
3 Evaluation Mechanism
4 Stochastic Refinement
5 Implementation and Empirical Evaluation
6 Related Work
7 Conclusions and Further Work
References
Experimental Investigation of Pruning Methods for Relations Pattern Discovery
1 Introduction
2 Subgroup Discovery in the Framework of Descriptive ILP
3 The Basic Search Algorithm
4 Pruning Methods
5 Experimental Setup
5.1 Task Settings
5.2 Databases and Search Spaces
5.3 Search Runs
6 Experimental Results
7 Conclusion
References
Noise-Resistant Incremental Relational Learning Using Possible Worlds
1 Motivation
2 Approaches to Noise Handling
3 Approaches to Incremental Relational Rule Learning
3.1 Selecting a Revision Method
4 Implementation
4.1 General Information
4.2 Nile's Learning Algorithm
4.3 Example Processing within a Single World
4.4 The Revision Operators for a Single World
4.5 Handling Noise in a Possible World
4.6 Post-processing
4.7 Putting It All together
5 Results
5.1 Learning Illegal Chess Positions
5.2 Learning a Tetris-Style Game
6 Conclusions
References
Lattice-Search Runtime Distributions May Be Heavy-Tailed
1 Introduction
2 Heavy-Tailed Distributions and Randomized Rapid Restarts
3 Randomizing the Lattice Search
4 Experiments
4.1 The Aim
4.2 Materials
4.3 Methods and Results
5 Related Work
6 Conclusions
References
Learning in Rich Representations: Inductive Logic Programming and Computational Scientific Discovery*
References
Author Index