Inductive logic programming and learnability

ABSTRACT

The paper gives an overview of theoretical results in the rapidly growing field of inductive logic programming (ILP). The ILP learning situation (generality model, background knowledge, examples, hypotheses) is formally characterized and various restrictions of it are discussed in the light of their impact on learnability. The two dominant models of learnability, PAC-learning and identification in the limit, are extended to take into account the ILP learning situation. Several learnability results for logic programs are then presented, both positive and negative.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Martin Anthony , Norman Biggs, Computational learning theory: an introduction, Cambridge University Press, New York, NY, 1992
	2	R. B. Banerji. Learning in the limit in a growing language. In <i>Proc. Tenth International Joint Conference on Artificial Intelligence,</i> pages 280--282. Morgan Kaufmann, San Mateo, CA, 1987.
	3	Wray Buntine, Generalized subsumption and its applications to induction and redundancy, Artificial Intelligence, v.36 n.2, p.149-176, September 1988 [doi>10.1016/0004-3702(88)90001-X]
	4	K. L. Clark. Negation as failure. In H. Gallaire and J. Minker, editors, <i>Logic and Databases,</i> pages 293--322. Plenum Press, New York, 1978.
	5	W. W. Cohen. Cryptographic limitations on learning one-clause logic programs. In <i>Proc. Tenth National Conference on Artificial Intelligence,</i> pages 80--85. MIT Press, Cambridge, MA, 1993.
	6	W. W. Cohen. Learnability of restricted logic programs. In S. Muggleton, editor, <i>Proc. Third International Workshop on Inductive Logic Programming, ILP'93,</i> pages 41--71. Jo&zcaron;ef Stefan Institute, Ljubljana, Slovenia, 1993.
	7	W. W. Cohen. Pac-learning a restricted class of recursive logic programs. In <i>Proc. Tenth National Conference on Artificial Intelligence,</i> pages 86--92. MIT Press, Cambridge, MA, 1993.
	8	Luc De Raedt, Interactive theory revision: an inductive logic programming approach, Academic Press Ltd., London, UK, 1992
	9	Luc De Raedt , Maurice Bruynooghe, Belief updating from integrity constraints and queries, Artificial Intelligence, v.53 n.2-3, p.291-307, Feb. 1992 [doi>10.1016/0004-3702(92)90075-9]
	10	S. D&zcaron;eroski and N. Lavra&ccaron;. Refinement graphs for FOIL and LINUS. In S. H. Muggleton, editor, <i>Inductive Logic Programming,</i> pages 319--333. Academic Press, London, 1992.
	11	Sašo Džeroski , Stephen Muggleton , Stuart Russell, PAC-learnability of determinate logic programs, Proceedings of the fifth annual workshop on Computational learning theory, p.128-135, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130399]
	12	M. Frazier and C. D. Page. Learnability in inductive logic programming: Some results and techniques. In <i>Proc. Tenth National Conference on Artificial Intelligence,</i> pages 93--98. MIT Press, Cambridge, MA, 1993.
	13	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	14	E. M. Gold. Language identification in the limit. <i>Information and Control,</i> 10:447--474, 1967.
	15	Georg Gottlob, Subsumption and implication, Information Processing Letters, v.24 n.2, p.109-111, January 1987 [doi>10.1016/0020-0190(87)90103-7]
	16	Philipp Hanschke , Jörg Würtz, Satisfiability of the smallest binary program, Information Processing Letters, v.45 n.5, p.237-241, April 2, 1993 [doi>10.1016/0020-0190(93)90210-Z]
	17	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]
	18	David Haussler, Learning Conjunctive Concepts in Structural Domains, Machine Learning, v.4 n.1, p.7-40, October 1989 [doi>10.1023/A:1022601210986]
	19	Peter Idestam-Almquist, Generalization under Implication by using Or-Introduction, Proceedings of the European Conference on Machine Learning, p.56-64, April 05-07, 1993
	20	P. Idestam-Almquist. Recursive anti-unification. In S. Muggleton, editor, <i>Proc. Third International Workshop on Inductive Logic Programming, ILP'93,</i> pages 241--254. Jo&zcaron;ef Stefan Institute, Ljubljana, Slovenia, 1993.
	21	J.-U. Kietz. A comparative study of structural most specific generalizations used in machine learning. In S. Muggleton, editor, <i>Proc. Third International Workshop on Inductive Logic Programming, ILP'93,</i> pages 149--164. Jo&zcaron;ef Stefan Institute, Ljubljana, Slovenia, 1993.
	22	J.-U. Kietz and S. Wrobel. Controlling the complexity of learning through syntactic and task-oriented models. In S. H. Muggleton, editor, <i>Inductive Logic Programming,</i> pages 107--126. Academic Press, London, 1992.
	23	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
	24	Nada Lavrac , Saso Dzeroski, Inductive Logic Programming: Techniques and Applications, Routledge, New York, NY, 1993
	25	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]
	26	J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
	27	J. Marcinkowski and L. Pacholski. Undecidability of the Hornclause implication problem. In <i>Proc. 33rd Annual IEEE Symposium on Foundations of Computer Science,</i> pages 354--362. 1992.
	28	Katherina Morik , Borg-Ewe Kietz , Werner Emde , Stephan Wrobel, Knowledge Acquisition and Machine Learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
	29	S. H. Muggleton, editor. <i>Inductive Logic Programming.</i> Academic Press, London, 1992.
	30	S. H. Muggleton. Inverting implication. <i>Artificial Intelligence Journal,</i> 1993. To appear.
	31	S. H. Muggleton and C. Feng. Efficient induction of logic programs. In <i>Proc. First Conference on Algorithmic Learning Theory,</i> pages 368--381. Ohmsha, Tokyo, 1990.
	32	T. Niblett. A study of generalization in logic programs. In <i>Proc. Third European Working Session on Learning.</i> Pitmann, London, 1988.
	33	C. D. Page and A. M. Frisch. Generalization and learn-ability: a study of constrained atoms. In S. H. Muggleton, editor, <i>Inductive Logic Programming,</i> pages 29--61. Academic Press, London, 1992.
	34	Leonard Pitt , Manfred K. Warmuth, Prediction-preserving reducibility, Journal of Computer and System Sciences, v.41 n.3, p.430-467, Dec. 1990 [doi>10.1016/0022-0000(90)90028-J]
	35	G. D. Plotkin. A note on inductive generalization. In B. Meltzer and D. Michie, editors, <i>Machine Intelligence,</i> pages 153 - 163. American Elsevier, 1970.
	36	G. D. Plotkin. <i>Automatic Methods of Inductive Inference.</i> PhD thesis, Edinburgh University, 1971.
	37	G. D. Plotkin. A further note on inductive generalization. In B. Meltzer and D. Michie, editors, <i>Machine Intelligence,</i> pages 101 - 124. American Elsevier, 1971.
	38	K. R. Popper. <i>The Logic of Scientific Discovery.</i> Basic Books, New York, 1959.
	39	J. R. Quinlan, Learning Logical Definitions from Relations, Machine Learning, v.5 n.3, p.239-266, Aug. 1990 [doi>10.1023/A:1022699322624]
	40	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]
	41	J. A. Robinson, A Machine-Oriented Logic Based on the Resolution Principle, Journal of the ACM (JACM), v.12 n.1, p.23-41, Jan. 1965 [doi>10.1145/321250.321253]
	42	Manfred Schmidt-Schauss, Implication of clauses is undecidable, Theoretical Computer Science, v.59 n.3, p.287-296, Aug. 1988 [doi>10.1016/0304-3975(88)90146-6]
	43	Ehud Y. Shapiro, Algorithmic Program DeBugging, MIT Press, Cambridge, MA, 1983
	44	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]
	45	Rolf Wiehagen , Thomas Zeugmann, Too Much Can be Too Much for Learning Efficiently, Proceedings of the International Workshop on Analogical and Inductive Inference, p.72-86, October 05-09, 1992
	46	Stefan Wrobel, Higher-order Concepts in a Tractable Knowledge Representation, Proceedings of the 11th German Workshop on Artificial Intelligence, p.129-138, September 28-October 02, 1987