Abstract
The field of Inductive Logic Programming (ILP), which is concerned with the induction of Hornclauses from examples and background knowledge, has received increased attention over the last time. Recently, some positive results concerning the learnability of restricted logic programs have been published. In this paper we review these restrictions and prove some lower-bounds of the computational complexity of learning. In particular, we show that a learning algorithm for i2-determinate Hornclauses (with variable i) could be used to decide the PSPACE-complete problem of Finite State Automata Intersection, and that a learning algorithm for 12-nondeterminate Hornclauses could be used to decide the NP-complete problem of Boolean Clause Satisfiability (SAT). This also shows, that these Hornclauses are not PAC-learnable, unless RP=NP=PSPACE.
Chapter PDF
Similar content being viewed by others
References
M. Anthony and N.Biggs. Computational Learning Theory. Cambridge University Press, 1992.
L. de Raedt and M. Bruynooghe. An overview of the interactive concept-learner and theory revisor clint. In S. Muggleton, editor, Inductive Logic Programming. Academic Press, 1992.
S. Džeroski, S. Muggleton, and S. Russell. Pac-learnability of determinate logic programs. In Proc. of the 5th ACM Workshop on Computaional Learning Theory (COLT), 1992.
Michael R. Garey and David S. Johnson. Computers and Intractability — A Guide to the Theory of NP-Completeness. Freeman, San Francisco, Cal., 1979.
David Haussler. Learning conjunctive concepts in structural domains. Machine Learning, 4(1):7–40, 1989.
Jörg-Uwe Kietz and Stefan Wrobel. Controlling the complexity of learning through syntactic and task-oriented models. In S. Muggleton, editor, Inductive Logic Programming, pages 107–126. Academic Press, 1992.
Stephan Muggleton and Cao Feng. Efficient induction of logic programs. In S. Muggleton, editor, Inductive Logic Programming. Academic Press, 1992.
Stephen Muggleton and Wray Buntine. Machine invention of first-order predicates by inverting resolution. In Proc. Fifth Intern. Conf. on Machine Learning, Los Altos, CA, 1988. Morgan Kaufman.
C. D. Page and A. M. Frisch. Generalisation and learnability: a study in constained atoms. In S. Muggleton, editor, Inductive Logic Programming. Academic Press, 1992.
Gordon D. Plotkin. A further note on inductive generalization. In B. Meltzer and D. Michie, editors, Machine Intelligence, volume 6, chapter 8, pages 101–124. American Elsevier, 1971.
J. R. Quinlan. Learning logical definitions from relations. Machine Learning, 5(3):239–266, 1990.
J. R. Quinlan. Determinate literals in inductive logic programming. In Proc. of the 12th IJCAI, 1991.
Celine Rouveirol. Completness for inductive procedures. In Proc. Eigth Intern. Workshop on Machine Learning, pages 452–456, 1991.
Celine Rouveirol. Semantic model for induction of first order theories. In Proc. 12th International Joint Conference on Artificial Intelligence, 1991.
Stefan Wrobel. Higher-order concepts in a tractable knowledge representation. In K. Morik, editor, GWAI-87 11th German Workshop on Artificial Intelligence, Informatik-Fachberichte Nr. 152, pages 129–138, Berlin, New York, Tokyo, October 1987. Springer.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kietz, JU. (1993). Some lower bounds for the computational complexity of inductive logic programming. In: Brazdil, P.B. (eds) Machine Learning: ECML-93. ECML 1993. Lecture Notes in Computer Science, vol 667. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56602-3_131
Download citation
DOI: https://doi.org/10.1007/3-540-56602-3_131
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56602-1
Online ISBN: 978-3-540-47597-2
eBook Packages: Springer Book Archive