Pac-Learning Recursive Logic Programs: Efficient Algorithms

We present algorithms that learn certain classes of function-free recursive logic programs in polynomial time from equivalence queries. In particular, we show that a single k-ary recursive constant-depth determinate clause is learnable. Two-clause programs consisting of one learnable recursive clause and one constant-depth determinate nonrecursive clause are also learnable, if an additional "basecase" oracle is assumed. These results immediately imply the pac-learnability of these classes. Although these classes of learnable recursive programs are very constrained, it is shown in a companion paper that they are maximally general, in that generalizing either class in any natural way leads to a computationally difficult learning problem. Thus, taken together with its companion paper, this paper establishes a boundary of efficient learnability for recursive logic programs.

• Publication year

  1994

• Venue

  Journal of Artificial Intelligence Research

• Publication date

  1994-08-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1613/JAIR.97arXiv cs/9505104
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Pac-Learning Non-Recursive Prolog Clauses

  1995influential reference
• Pac-learning Recursive Logic Programs: Eecient Algorithms

  1995cited by this paper
• A Learnability Model for Universal Representations and Its Application to Top-down Induction of Decision Trees

  1995cited by this paper
• Inverting Implication with Small Training Sets

  1994cited by this paper
• Pac-learning Recursive Logic Programs: Negative Results

  1994influential reference
• First-Order jk-Clausal Theories are PAC-Learnable

  1994influential reference
• Inducing Deterministic Prolog Parsers from Treebanks: A Machine Learning Approach

  1994cited by this paper
• Mutagenesis: ILP experiments in a non-determinate biological domain

  1994cited by this paper
• Pac-Learning Nondeterminate Clauses

  1994cited by this paper
• Inductive Logic Programming: Theory and Methods

  1994cited by this paper
• Sample PAC-Learnability in Model Inference

  1994cited by this paper
• Multiple Predicate Learning

  1993cited by this paper
• Generalization under Implication by Recursive Anti-unification

  1993cited by this paper
• Rapid Prototyping of ILP Systems Using Explicit Bias

  1993influential reference
• Two Methods for Improving Inductive Logic Programming Systems

  1993cited by this paper
• Learnability in inductive logic programming: some basic results and techniques

  1993cited by this paper
• An Interactive System to Learn Functional Logic Programs

  1993cited by this paper
• FOIL: A Midterm Report

  1993cited by this paper
• Polynomial-Time Learning with Version Spaces

  1992cited by this paper
• Drug design by machine learning: the use of inductive logic programming to model the structure-activity relationships of trimethoprim analogues binding to dihydrofolate reductase.

  1992cited by this paper
• Background Knowledge and Declarative Bias in Inductive Concept Learning

  1992cited by this paper
• PAC-learnability of determinate logic programs

  1992influential reference
• Protein secondary structure prediction using logic-based machine learning.

  1992cited by this paper
• Inverting Implication

  1992cited by this paper
• Generalization and Learnability: a Study of Constrained Atoms

  1992cited by this paper
• Determinate Literals in Inductive Logic Programming

  1991cited by this paper
• Efficient Induction of Logic Programs

  1990cited by this paper
• Equivalence queries and approximate fingerprints

  1989cited by this paper
• Foundations of logic programming; (2nd extended ed.)

  1987cited by this paper
• A theory of the learnable

  1984influential reference
• Algorithmic Program Debugging

  1983cited by this paper
• The Inference of Regular LISP Programs from Examples

  1978cited by this paper
• A Methodology for LISP Program Construction from Examples

  1977cited by this paper
• Language Identification in the Limit

  1967cited by this paper

• SynGuar: guaranteeing generalization in programming by example

  2021cites this paper
• Generalizable synthesis through unification

  2021cites this paper
• Occam Learning Meets Synthesis Through Unification

  2021cites this paper
• Inductive logic programming at 30: a new introduction

  2020cites this paper
• On Machine Learning with Imbalanced Data and Research Quality Evaluation Methodologies

  2014cites this paper
• Learning schema mappings

  2013cites this paper
• Learning schema mappings

  2012cites this paper
• A Combined Analytical and Search-Based Approach for the Inductive Synthesis of Functional Programs

  2011cites this paper
• Efficient learning of relational models for sequential decision making

  2010cites this paper
• Learning Horn definitions: Theory and an application to planning

  2009cites this paper
• An inference method for the complete inverse of relative subsumption

  2009cites this paper
• An object-oriented representation for efficient reinforcement learning

  2008cites this paper
• Learning Relational Rules for Goal

  2007cites this paper
• Complexity parameters for first order classes

  2006cites this paper
• (Agnostic) PAC Learning Concepts in Higher-Order Logic

  2006cites this paper
• Prediction-hardness of acyclic conjunctive queries

  2005influential citation
• Learning Comprehensible Theories from Structured Data

  2005cites this paper
• Workshop on Approaches and Applications of Inductive Programming, AAIP 2005, to be held in conjunction with the 22nd International Conference on Machine Learning (ICML 2005), Bonn, Germany, August 7, 2005

  2005cites this paper
• Generalization Behaviour of Alkemic Decision Trees

  2005cites this paper
• Learning Recursive Prolog Programs with Local Variables from Examples

  2005cites this paper
• Discovering and debugging algebraic specifications for java classes

  2004cites this paper
• Feature Extraction Languages for Propositionalized Relational Learning

  2003cites this paper
• Inductive Synthesis of Functional Programs

  2003cites this paper
• Learning with Feature Description Logics

  2002cites this paper
• Learning Closed Horn Expressions

  2002cites this paper
• Learning logic programs with structured background knowledge

  2001cites this paper
• Learning in Natural Language: Theory and Algorithmic Approaches

  2000cites this paper
• On the Hardness of Learning Acyclic Conjunctive Queries

  2000cites this paper
• On Sufficient Conditions for Learnability of Logic Programs from Positive Data

  1999cites this paper
• Inductive Synthesis of Recursive Logic Programs: Achievements and Prospects

  1999cites this paper
• Automatically Exploring Hypotheses About Fault Prediction: A Comparative Study of Inductive Logic Programming Methods

  1999influential citation
• Learning Function-Free Horn Expressions

  1999influential citation
• Mind change complexity of learning logic programs

  1999cites this paper
• Learning Range Restricted Horn Expressions

  1999cites this paper
• The Complexity of Revising Logic Programs

  1999cites this paper
• Relational Learning for NLP using Linear Threshold Elements

  1999influential citation
• Function-Free Horn Clauses Are Hard to Approximate

  1998cites this paper
• Learning atomic formulas with prescribed properties

  1998cites this paper
• Learning First-Order Acyclic Horn Programs from Entailment

  1998cites this paper
• Learning first order universal Horn expressions

  1998cites this paper
• Learning Horn Deenitions: Theory and an Appli- Cation to Planning

  1998cites this paper
• Logical Aspects of Several Bottom-Up Fittings

  1998cites this paper
• Learning Weakly Acyclic Horn Programs

  1998cites this paper
• Machine Learning, 1{38 () Learning Function-free Horn Expressions

  1998cites this paper
• Inductive Program Synthesis as Induction of Context-Free Tree Grammars

  1998cites this paper
• Which Hypotheses Can Be Found with Inverse Entailment?

  1997cites this paper
• On the complexity of some inductive logic programming problems

  1997cites this paper
• Learning Horn Definitions with Equivalence and Membership Queries

  1997cites this paper
• Learning logic programs by using the product homomorphism method

  1997cites this paper
• Learning Goal-Decomposition Rules Using Exercises

  1997cites this paper
• Representing Inductive Inference with SOLD-Resolution

  1997cites this paper
• Some classes of prolog programs inferable from positive data

  1996cites this paper
• Learning to Take Actions

  1996cites this paper
• Learning Logic Programs with Random Classification Noise

  1996influential citation
• Pac-Learning Non-Recursive Prolog Clauses

  1995influential citation
• The Complexity of Theory Revision

  1995cites this paper
• Pac-Learning Recursive Logic Programs: E cient Algorithms

  1995cites this paper
• Generalization of Clauses under Implication

  1995cites this paper
• Pac-learning Recursive Logic Programs: Eecient Algorithms

  1995cites this paper
• Pac-learning Recursive Logic Programs: Negative Results

  1994cites this paper
• Feature Extraction Languages for Machine Learning

  year unknowncites this paper
• On Practical Inductive Logic Programming

  year unknowncites this paper