How to Upgrade Propositional Learners to First Order Logic: A Case Study
Published 1 January 2001
Wim Van Laer, Luc De Raedt
Citations32
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A methodology for upgrading existing attribute-value learners towards first-order logic and there is a clear relationship between the new relational system and its propositional counterpart, which makes the ILP system easy to use and understand by users familiar with the propositional counterparts.
Abstract
We describe a methodology for upgrading existing attribute-value learners towards first-order logic. This method has several advantages: one can profit from existing research on propositional learners (and inherit its efficiency and effectiveness), relational learners (and inherit its expressiveness) and PAC-learning (and inherit its theoretical basis). Moreover there is a clear relationship between the new relational system and its propositional counterpart. This makes the ILP system easy to use and understand by users familiar with the propositional counterpart. We demonstrate the methodology on the ICL system which is an upgrade of the propositional learner CN2.
Keywords
Computer Science
BiometricsClassification and Regression Trees.
23,841 Citations1984Alexander Gordon, Leo Breiman +3 more
C4.5: Programs for Machine Learning
23,665 Citations1992J. R. Quinlan
A complete guide to the C4.5 system as implemented in C for the UNIX environment, which starts from simple core learning methods and shows how they can be elaborated and extended to deal with typical problems such as missing data and over hitting.
Machine LearningInduction of Decision Trees
14,815 Citations1986J. R. Quinlan
This paper summarizes an approach to synthesizing decision trees that has been used in a variety of systems, and it describes one such system, ID3, in detail, which is described in detail.
Mining association rules between sets of items in large databases
14,720 Citations1993Rakesh Agrawal, Tomasz Imieliński +1 more
An efficient algorithm is presented that generates all significant association rules between items in the database of customer transactions and incorporates buffer management and novel estimation and pruning techniques.
ACM SIGMOD RecordMining association rules between sets of items in large databases
4,475 Citations1993Rakesh Agrawal, Tomasz Imieliński +1 more
A theory of the learnable
4,242 Citations1984Leslie G. Valiant
This paper regards learning as the phenomenon of knowledge acquisition in the absence of explicit programming, and gives a precise methodology for studying this phenomenon from a computational viewpoint.
Elsevier eBooksFast Effective Rule Induction
3,767 Citations1995William W. Cohen
This paper evaluates the recently-proposed rule learning algorithm IREP on a large and diverse collection of benchmark problems, and proposes a number of modifications resulting in an algorithm RIPPERk that is very competitive with C4.5 and C 4.5rules with respect to error rates, but much more efficient on large samples.
Communications of the ACMA theory of the learnable
3,268 Citations1984Leslie G. Valiant
This paper regards learning as the phenomenon of knowledge acquisition in the absence of explicit programming, and gives a precise methodology for studying this phenomenon from a computational viewpoint.
Computational LinguisticsA maximum entropy approach to natural language processing
3,120 Citations1996Adam Berger, Vincent J. Della Pietra +1 more
A maximum-likelihood approach for automatically constructing maximum entropy models is presented and how to implement this approach efficiently is described, using as examples several problems in natural language processing.
International Joint Conference on Artificial IntelligenceMulti-Interval Discretization of Continuous-Valued Attributes for Classification Learning
2,832 Citations1993Usama M. Fayyad, Keki B. Irani
This paper addresses the use of the entropy minimization heuristic for discretizing the range of a continuous-valued attribute into multiple intervals.
Machine LearningThe CN2 Induction Algorithm
2,015 Citations1989Peter Clark, Tim Niblett
A description and empirical evaluation of a new induction system, CN2, designed for the efficient induction of simple, comprehensible production rules in domains where problems of poor description language and/or noise may be present.
Elsevier eBooksSupervised and Unsupervised Discretization of Continuous Features
1,931 Citations1995James Dougherty, Ron Kohavi +1 more
Binning, an unsupervised discretization method, is compared to entropy-based and purity-based methods, which are supervised algorithms, and it is found that the performance of the Naive-Bayes algorithm significantly improved when features were discretized using an entropy- based method.
The Journal of Logic ProgrammingInductive Logic Programming: Theory and methods
1,550 Citations1994Stephen Muggleton, Luc De Raedt
The most important theories and methods of Inductive Logic Programming, a new discipline which investigates the inductive construction of first-order clausal theories from examples and background knowledge, are surveyed.
Machine LearningLearning Logical Definitions from Relations
1,425 Citations1990J. R. Quinlan
FOIL is a system that learns Horn clauses from data expressed as relations, but extends them to a first-order formalism, which has been applied successfully to several tasks taken from the machine learning literature.
New Generation ComputingInverse entailment and progol
1,408 Citations1995Stephen Muggleton
Mode-Directed Inverse Entailment (MDIE) is introduced as a generalisation and enhancement of previous approaches for inverting deduction and an implementation of MDIE in the Progol system is described.
DSpace@MIT (Massachusetts Institute of Technology)Learning Structural Descriptions From Examples
1,007 Citations1970Patrick Henry Winston
New Generation ComputingInductive logic programming
932 Citations1991Stephen Muggleton
A discussion of the feasibility of extending the RLGG framework to allow for the invention of new predicates and the possible relationship between Algorithmic Complexity theory and Probably-Approximately-Correct Learning is discussed.
Lecture notes in computer scienceRule induction with CN2: Some recent improvements
866 Citations1991Peter Clark, Robin Boswell
Improvements to the CN2 algorithm are described, including the use of the Laplacian error estimate as an alternative evaluation function and it is shown how unordered as well as ordered rules can be generated.
Computer CompactsA theory and methodology of inductive learning
778 Citations1983Ryszard S. Michalski
National Conference on Artificial IntelligenceThe multi-purpose incremental learning system AQ15 and its testing application to three medical domains
761 Citations1986Ryszard S. Michalski, Igor Mozetič +2 more
The demonstration that by applying the proposed method of cover truncation and analogical matching, called TRUNC, one may drastically decrease the complexity of the knowledge base without affecting its performance accuracy is demonstrated.
Efficient Induction of Logic Programs
657 Citations1990Stephen Muggleton, Cheng Feng
The concept of h-easy rlgg clauses is introduced and it is proved that the length of a certain class of \determinate" r lgg is bounded by a polynomial function of certain features of the background knowledge.
Lecture notes in computer scienceFoundations of Inductive Logic Programming
473 Citations1997Shan-Hwei Nienhuys-Cheng, Roland Wolf
Propositional logic, first-order logic, normal forms and Herbrand models, linear and input resolution, and unfolding: the lattice and cover structure of atoms.
Advances in Inductive Logic Programming
313 Citations1996Luc De Raedt
A state-of-the-art overview of Inductive Logic Programming is provided, based on the succesful ESPRIT basic research project no. 6020, which can be used as a thorough introduction to the field.
Artificial IntelligenceTheories for mutagenicity: a study in first-order and feature-based induction
300 Citations1996Ashwin Srinivasan, Stephen Muggleton +2 more
This work considers the problem of predicting the mutagenic activity of small molecules: a property that is related to carcinogenicity, and an important consideration in developing less hazardous drugs, and compares the predictive power of the logical theories constructed against benchmarks set by regression, neural, and tree-based methods.
Machine LearningClausal Discovery
238 Citations1997Luc De Raedt, Luc De Raedt
CLAUDIEN is an inductive logic programming engine that fits in the descriptive data mining paradigm and employs a novel declarative bias mechanism to define the set of clauses that may appear in a hypothesis.
Machine LearningLearning conjunctions of Horn clauses
188 Citations1992Dana Angluin, Michael Frazier +1 more
Lecture notes in computer scienceMining association rules in multiple relations
188 Citations1997Luc De Raedt, Luc De Raedt
The system Warmr is presented, which extends Apriori to mine association rules in multiple relations, and is applied to the natural language processing task of mining part-of-speech tagging rules in a large corpus of English.
Relational instance-based learning
174 Citations1996Werner Emde, Dietrich Wettschereck
The AQ15 Inductive Learning System: An Overview and Experiments
171 Citations1986Ryszard S. Michalski, Igor Mozetič +2 more
Communications of the ACMApplications of inductive logic programming
166 Citations1995Ivan Bratko, Stephen Muggleton
Attribute-based learning is limited to non-relational descriptions of objects in the sense that the learned descriptions do not specify relations among the objects' parts, and the lack of relations makes the concept description language inappropriate for some domains.
Pruning and Grouping Discovered Association Rules
154 Citations1995Hannu Toivonen, Mika Klemettinen +3 more
This work shows how the set of rules can be pruned by forming rule covers, and discusses grouping of association rules by clustering, and presents some experimental results of both pruning and grouping.
Artificial IntelligenceLogical settings for concept-learning
152 Citations1997Luc De Raedt
It is shown that learning from interpretations reduces toLearning from entailment, which in turn reduces to learning from satisfiability, which reduces to inductive logic programming and computational learning theory.
Artificial IntelligenceFirst-order jk-clausal theories are PAC-learnable
142 Citations1994Luc De Raedt, Sašo Džeroski
Positive PAC-learning results for the nonmonotonic inductive logic programming setting are presented and first-order range-restricted clausal theories that consist of clauses with up to k literals of size at most j each are shown to be PAC-learnable with one-sided error from positive examples only.
Communications of the ACMAn interference matching technique for inducing abstractions
124 Citations1978Frederick Hayes‐Roth, John McDermott
Three tasks solved by a program that uses an interference-matching algorithm are presented and several problems concerning the description of the training examples and the adequacy of interference matching are discussed.
Lecture notes in computer scienceAttribute-value learning versus inductive logic programming: The missing links
118 Citations1998Luc De Raedt
It is much more tractable to stick to the relational representation than to apply the sketched transformation, which provides a sound theoretical justification for inductive logic programming.
Lecture notes in computer scienceInductive constraint logic
117 Citations1995Luc De Raedt, Wim Van Laer
A novel approach to learning first order logic formulae from positive and negative examples is presented, which corresponds to a conjuctive normal form where each conjunct forms a constraint on positive examples.
International Joint Conference on Artificial IntelligenceInduction of concepts in the predicate calculus
117 Citations1975Steven A. Vere
This work is directed to providing a formal model for the inductive processes which are observed in artificial intelligence studies in specialized areas, by an induction procedure which operates on the product graph form of positive and negative instances.
International Journal of Biological MacromoleculesThe predictive toxicology evaluation challenge
113 Citations1997Ashwin Srinivasan, Ross D. King +2 more
The paper optimized the parameters of microwave freeze drying of crude Ginkgo biloba protein using response surface methodology (RSM) based on the analysis of its proximate composition and showed that coefficients of determination, R(2) values for drying time and protein solubility were greater than 0.9500.
New Generation ComputingRelating chemical activity to structure: An examination of ILP successes
92 Citations1996Ross D. King, Ashwin Srinivasan +1 more
This paper compared ILP theories with those constructed using standard linear regression and a decision-tree learner on a series of progressively more difficult problems and showed that ILP programs can still continue to construct accurate, understandable theories when a propositional encoding is feasible for the feature-based algorithms.
Structural regression trees
91 Citations1996Stefan Krämer
Structural Regression Trees (SRT) is presented, a new algorithm which integrates the statistical method of regression trees into Inductive Logic Programming and can be applied to a class of problems most other ILP systems cannot handle.
Journal of Artificial Intelligence ResearchLearning First-Order Definitions of Functions
89 Citations1996J. R. Quinlan
This paper shows how a particular first-order learning system is modified to customize it for finding definitions of functional relations, which leads to faster learning times and, in some cases, to definitions that have higher predictive accuracy.
Artificial IntelligenceGrammatically biased learning: Learning logic programs using an explicit antecedent description language
86 Citations1994William W. Cohen
A learning system is described that makes a large part of the concept description language an explicit input, and some of the possible applications of providing this additional input are discussed.
Molecular and Cellular BiologyProceedings of the eighth international workshop on Machine learning
80 Citations1991Lawrence Birnbaum, Gregg Collins
An in vitro system that packages DNA into minichromosomes with regularly spaced nucleosomes containing histones H3, H4, H2A, and H2B but no histone H1 is described, suggesting that histoneH1 is not required for regular nucleosome spacing or for gene repression in this system.
Elsevier eBooksDeterminate Literals in Inductive Logic Programming
74 Citations1991J. R. Quinlan
Key ideas from FOIL and GOLEM are sketched and the use of determinate literals in a greedy search context is discussed and the efficacy of this approach is illustrated on the task of learning the quicksort procedure and other small but non-trivial list-manipulation functions.
International Joint Conference on Artificial IntelligenceMultiple predicate learning
74 Citations1993Luc De Raedt, Nada Lavrač +1 more
Lecture notes in computer scienceRelational distance-based clustering
70 Citations1998Mathias Kirsten, Stefan Wrobel
RDBC is a bottom-up agglomerative clustering algorithm for first-order representations that relies on distance information only and features a novel parameter-free pruning measure for selecting the final clustering from the cluster tree.
European Conference on Artificial IntelligenceConceptual clustering in a first order logic representation
64 Citations1992Gilles Bisson
The Conceptual Clustering system KBG structures information from a set of observations and a domain theory into a directed graph of concepts, generated by an iterative use of clustering and generalization operators, both guided by similarity measures.
An algorithm that infers theories from facts
63 Citations1981Ehud Shapiro
A framework for inductive inference in logic is presented, and it is shown that problems of machine learning and program synthesis from examples can be formulated naturally as model inference problems.
Hrčak Portal of scientific journals of Croatia (University Computing Centre)Using the m -estimate in rule induction
63 Citations1993Sašo Džeroski, Bojan Cestnik +1 more
This work replaces the Laplace estimate in the rule induction system CN2 with a general Bayesian probability estimate, the m- estimate, which does not rely on the Laplacian assumption of equally likely classes and allows for adapting to the learning domain.
New Generation ComputingRelating chemical activity to structure: An examination of ILP successes
61 Citations1995Ross D. King, Michael J.E. Sternberg +1 more
This paper compared ILP theories with those constructed using standard linear regression and a decision-tree learner on a series of progressively more difficult problems, and showed that a propositional encoding is feasible for the feature-based algorithms and are capable of matching the predictive accuracies of an ILP theory.
Artificial IntelligenceTop-down induction of first-order logical decision trees
58 Citations1998Hendrik Blockeel, Luc De Raedt
This dissertation discusses the application domain of decision tree learning and extends it towards the first order logic context of Inductive Logic Programming.
Lecture notes in computer scienceStrongly typed inductive concept learning
49 Citations1998Peter Flach, Christophe Giraud-Carrier +1 more
It is argued that the use of a language with a type system, together with higher-order facilities and functions, provides a suitable basis for knowledge representation in inductive concept learning and illuminates the relationship between attribute-value learning and inductive logic programming (ILP).
Lecture notes in computer scienceExperiments in Predicting Biodegradability
49 Citations1999Sašo Džeroski, Hendrik Blockeel +4 more
A novel application of inductive logic programming (ILP) in the area of quantitative structure-activity relationships (QSARs) is presented, using a number of relational classification and regression methods on the relational representation and comparing these to propositional methods applied to different propositionalisations of the problem.
Institutional Research Information System University of Turin (University of Turin)An Interactive System to Learn Functional Logic Programs.
49 Citations1993Francesco Bergadano, Daniele Gunetti
A system, called FILP, is described, which asks existential queries to the user, and is able to learn multiple predicates and recursive clauses, and it is proved that the learned descriptions are correct in the sense that they are consistent with the given examples.
Lirias (KU Leuven)Frequent pattern discovery in first-order logic
46 Citations1999Luc De Raedt
A general formulation of the frequent pattern discovery problem, where both the database and the patterns are represented in some subset of first-order logic, i.e., essentially Prolog, and each example as it were corresponds to a (mini-)database.
Lecture notes in computer scienceMaximum Entropy modeling with Clausal Constraints
45 Citations1997Luc De Raedt
First experiments indicate MACCENT may be useful for prediction, and for classification in cases where the induced model should be combined with other stochastic information sources, and on an existing maximum-likelihood approach to maximum entropy modeling.
Lecture notes in computer scienceAn Assessment of ILP-assisted models for toxicology and the PTE-3 experiment
42 Citations1999Ashwin Srinivasan, Ross D. King +1 more
An assessment of toxicity models that used findings from ILP programs along scales of quantitative performance, in comparison to models developed with expert collaboration; and potential explanatory value for toxicology.
The Journal of Logic ProgrammingCompleteness and properness of refinement operators in inductive logic programming
39 Citations1998P.R.J. van der Laag, Shan-Hwei Nienhuys-Cheng
If an element in a quasi-ordered set 〈 S, ≥〉 has an infinite or incomplete cover set, then an ideal refinement operator for 〉 does not exist, and it is shown that these chains exist in unrestricted sets of clauses that are ordered by θ-subsumption.
Controlling the Complexity of Learning in Logic through Syntactic and Task-Oriented Models
37 Citations1991Jörg-Uwe Kietz, Stefan Wrobel
Lecture notes in computer scienceOn multi-class problems and discretization in inductive logic programming
36 Citations1997Wim Van Laer, Luc De Raedt +1 more
In practical applications of machine learning and knowledge discovery, handling multi-class problems and real numbers are important issues and attribute-value learners address these problems as a rule, but few ILP systems do so.
Applied Artificial IntelligenceDiterpene structure elucidation from 13cnmr spectra with inductive logic programming
36 Citations1998Sašo Džeroski, Steffen Schulze-Kremer +4 more
A novel application ofuctive Logic Programming (ILP) to the problem of diterpene structure elucidation from 13 CNMR spectra to discover correlations between peak patterns and chemical structure.
Lecture notes in computer scienceLearning first-order acyclic Horn programs from entailment
29 Citations1998Chandra Reddy, Prasad Tadepalli
It is shown that any subclass of first-order acyclic Horn programs with constant arity is exactly learnable from equivalence and entailment membership queries provided it allows a polynomial-time subsumption procedure and satisfies some closure conditions.
Lecture notes in computer scienceDetecting traffic problems with ILP
24 Citations1998Sašo Džeroski, Nico Jacobs +4 more
Three state-of-the art ILP systems are applied to learn how to detect traffic problems and compare their performance to the performance of a propositional learning system on the same problem.
A Process-Oriented Heuristic for Model Selection
22 Citations1998Pedro Domingos
The paper develops the necessary theoretical framework, and applies it to one type of learning: rule induction, and develops a process-oriented version of the CN2 rule learner, which is empirically compared with the default CN2.
Machine LearningOGUST
17 Citations1990Christel Vrain
This chapter presents a system, called OGUST, which learns concepts from sets of examples, and shows that for learning “good” generalizations, one must use all kinds of theorems and not only those expressed by taxonomies.
Lecture notes in computer scienceILP experiments in detecting traffic problems
11 Citations1998Sašo Džeroskil, Nico Jacobs +2 more
Preliminary results show that ILP can be used to successfully learn to detect traffic problems and be used for expert systems for decision support in road transport management.
Lecture notes in computer scienceProbabilistic first-order classification
8 Citations1997Uroš Pompe, Igor Kononenko
This paper proposes an enhancement of classification based on the naive Bayesian scheme that is able to overcome the conditional independence assumption and indicates that the classification performance of propositional learners is reached when the richer first-order knowledge representation is not mandatory.
Lirias (KU Leuven)Multi-class problems and discretization in ICL
1 Citations1996Wim Van Laer, Sašo Džeroski +1 more