PAC-learnability of determinate logic programs

ABSTRACT

The field of Inductive Logic Programming (ILP) is concerned with inducing logic programs from examples in the presence of background knowledge. This paper defines the ILP problem, and describes the various syntactic restrictions that are commonly used for learning first-order representations. We then derive some positive results concerning the learnability of these restricted classes of logic programs, by reduction to a standard propositional learning problem. More specifically, k-clause predicate definitions consisting of determinate, function-free, non-recursve Horn clauses with variables of bounded depth are polynomially learnable under simple distributions. Similarly, recursive k-clause definitions are polynomially learnable under simple distributions if we allow existential and membership queries about the target concept.

REFERENCES

• Benedek and Itai 1988: Gyora M. Benedek , Alon Itai, Learnability by fixed distributions, Proceedings of the first annual workshop on Computational learning theory, p.80-90, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• De Raedt and Bruynooghe 1992: Luc De Raedt , Maurice Bruynooghe, Interactive Concept-Learning and Constructive Induction by Analogy, Machine Learning, v.8 n.2, p.107-150, March 1992 [doi>10.1023/A:1022664419589]
• Dzeroski and Lavrac 1992: S. Dieroski and N. LavraL Refinement graphs for FOIL and LINUS. In S. H. Muggleton, editor, Inductive Logic Programming, Academic Press, London, 1992. In press.
• Haussler 1988: D. Haussler, Quantifying inductive bias: AI learning algorithms and Valiant's learning framework, Artificial Intelligence, v.36 n.2, p.177-221, September 1988 [doi>10.1016/0004-3702(88)90002-1]
• Lavrac et al. 1991: Nada Lavrač , Sašo Džeroski , Marko Grobelnik, Learning nonrecursive definitions of relations with LINUS, Proceedings of the European working session on learning on Machine learning, p.265-281, March 1991, Porto, Portugal
• Lloyd 1987: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• Li and Vitanyi 1991: Ming Li , Paul M. B. Vitányi, Learning simple concepts under simple distributions, SIAM Journal on Computing, v.20 n.5, p.911-935, Oct. 1991 [doi>10.1137/0220056]
• Muggleton 1987: S. H. Muggleton. Duce, an oraclebased approach to constructive induction. In Proc. Tenth International Joint Conference on Artificial Intelligence, pages 287-292, Morgan Kaufmann, San Mateo, CA, 1989.
• Muggleton 1991: Stephen Muggleton, Inductive logic programming, New Generation Computing, v.8 n.4, p.295-318, 1991 [doi>10.1007/BF03037089]
• Muggleton 1992: S. H. Muggleton, editor. Inductive Logic Programming, Academic Press, London, 1992. In press.
• Muggleton and Buntine 1988: S. H. Muggleton and W. Buntine. Machine invention of first-order predicates by inverting resolution. In Proc. Fifth International Conference on Machine Learning, pages 339- 352, Morgan Kaufmann, San Mateo, CA, 1988.
• Muggleton and Feng 1990: S. H. Muggleton and C. Feng. Efficient induction of logic programs. In Proc. First Conference on Algorithmic Learning Theory, pages 368-381, Ohmsha, Tokyo, 1990.
• Page and Frisch 1992: C. D. Page and A. M. Frisch. Generalization and learnability: a study of constrained atoms. In S. H. Mugglcton, editor, Inductive Logic Programming, Academic Press, London, 1992. In press.
• Quinlan 1990: Pat Langley, Editorial: Advice to Machine Learning Authors, Machine Learning, v.5 n.3, p.233-237, Aug. 1990 [doi>10.1023/A:1022647305786]
• Quinlan 1991: J. Ross Quinlan, Knowledge Acquisition from Structured Data: Using Determinate Literals to Assist Search, IEEE Expert: Intelligent Systems and Their Applications, v.6 n.6, p.32-37, December 1991 [doi>10.1109/64.108949]
• Rivest 1987: Ronald L. Rivest, Learning Decision Lists, Machine Learning, v.2 n.3, p.229-246, November 1987 [doi>10.1023/A:1022607331053]
• Rouveirol 1991: C. Rouveirol. Completeness for inductive procedures. In Proc. Eighth International Workshop on Machine Learning, pages 452-456, Morgan Kaufmann, San Mateo, CA, 1991.
• Shapiro 1983: Ehud Y. Shapiro, Algorithmic Program DeBugging, MIT Press, Cambridge, MA, 1983
• Valiant 1984: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

General Terms:
Algorithms, Theory, Verification