ICML-98 Submission #187

Learning First-Order Acyclic Horn Programs from Entailment

                  Chandra Reddy and Prasad  Tadepalli  
                  Dearborn 303  
                  Department  of Computer Science 
                  Oregon State  University,  
                  Corvallis, OR 97331-3202.                
                  (541) 737-4967
		  {reddyc,tadepalli}@cs.orst.edu

Abstract

Learning first-order Horn programs---sets of first-order Horn
clauses---is an important problem in inductive logic programming with
applications ranging from speedup learning to grammatical inference.
In this paper, we consider learning first-order Horn programs from
entailment.  In particular, we show 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.  One consequence of this is that first-order acyclic
determinate Horn programs with constant arity are exactly learnable
from equivalence and entailment membership queries.

Keywords:  Horn programs,  inductive logic  programming,  speedup learning,
           learning from entailment, queries
           
Author Contact: reddyc@cs.orst.edu, (541) 737-4967