Abstract
The task of predicate invention in Inductive Logic Programming is to extend the hypothesis language with new predicates if the vocabulary given initially is insufficient for the learning task. However, whether predicate invention really helps to make learning succeed in the extended language depends on the language bias currently employed.
In this paper, we investigate for which commonly employed language biases predicate invention is an appropriate shift operation. We prove that for some restricted languages predicate invention does not help when the learning task fails and we characterize the languages for which predicate invention is useful. We investigate the decidability of the bias shift problem for these languages and discuss the capabilities of predicate invention as a bias shift operation.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Cohen, W., (1993). PAC-learning a restricted class of recursive logic programs. InProc. of the 3rd International Workshop on Inductive Logic Programming.
De Raedt, L. (1992).Interactive theory revision: an inductive logic programming approach. Academic Press.
De Raedt, L. & Bruynooghe, M. (1989). Towards friendly concept learners. InProc. of IJCAI.
De Raedt, L. & Bruynooghe, M. (1992). Interactive concept-learning and constructive induction by analogy.Machine Learning, 8(2):107–150.
De Raedt, L., Feyaerts, J. & Bruynooghe, M. (1991). Acquiring object-knowledge for learning systems. In Y. Kodratoff, editor.Proc. of the Fifth European Working Session on Learning. Springer.
Dzeroski, S., Muggleton, S. & Russel, S. (1992). PAC-learnability of determinate logic programs. InProc. of the 5th ACM Workshop on Computational Learning Theory.
Flach, P.A. (1993). Predicate invention in inductive data engineering. InMachine Learning: ECML-93, European Conference on Machine Learning, Wien, Austria. Springer.
Gold, E.M. (1967). Language identification in the limit.Information and Control, 10:447–474.
Kietz, J.U. & Wrobel, S. (1992). Controlling the complexity of learning in logic through syntactic and task-oriented models. In S. Muggleton, editor,Inductive Logic Programming. Academic Press.
Kietz, J.U. & Morik, K. (1994). A polynomial approach to the constructive induction of structural knowledge.Machine Learning, 14:193–217.
Kleene, S.C. (1952). Finite axiomatizability of theories in the predicate calculus using additional predicate symbols. InTwo Papers on the Predicate Calculus, number 10 in Memoirs of the American Mathematical Society.
Lapointe, S., Ling, C. & Matwin, S. (1993). Constructive inductive logic programming. InProc. of the IJCAI-93. Morgan Kaufmann.
Mitchell, T.M. (1980). The need for biases in learning generalizations. In J. W. Shavlik and T. G. Dietterich, editors,Readings in Machine Learning. Morgan Kaufmann.
Muggleton, S. (1988). A strategy for constructing new predicates in first order logic. InProceedings of the Third European Working Session on Learning. Pitman.
Muggleton, S. (1990). Inductive logic programming. InFirst Conference on Algorithmic Learning Theory, Tokio, Ohmsha.
Muggleton, S. (1993). Inductive logic programming: Derivations, successes and shortcoming. InMachine Learning: ECML-93, European Conference on Machine Learning, Wien, Austria. Springer.
Muggleton, S. & Buntine, W. (1988). Machine invention of first-order predicates by inverting resolution. InFifth International Conference on Machine Learning. Morgan Kaufmann.
Muggleton, S. & De Raedt, L. (1994). Inductive logic programming: Theory and methods. Journal of Logic Programming, Special Issue on 10 Years of Logic Programming.
Muggleton, S. & Feng, C. (1990). Efficient induction of logic programs. InFirst Conference on Algorithmic Learning Theory, Tokyo, Ohmsha.
Quinlan, J.R. (1990). Learning logical definitions from relations.Machine Learning, 5:239–266.
Reinhardt, K. (1993). Personal communication.
Rouveirol, C. (1991).ITOU: Induction de Theories en Ordre Un. PhD thesis, Université Paris Sud, Centre d'Orsay.
Rouveirol, C. (1992). ITOU: Induction of first order theories. In Muggleton, S., editor,Inductive Logic Programming. Academic Press.
Srinivasan, A., Muggleton, S., & Bain, M. (1992). Distinguishing exceptions from noise in non-monotonic learning. InProceedings of ILP'92, Tokyo.
Stahl, I., Tausend, B., & Wirth, R. (1993). Two methods for improving inductive logic programming systems. InMachine Learning: ECML-93, European Conference on Machine Learning, Wien, Austria. Springer.
Tausend, B. (1992). Using and adapting schemes for the induction of horn clauses. InECAI Workshop Logical Approaches to Machine Learning, Wien.
Wirth. R. (1989).Lernverfahren zur Vervollständigung von Hornklauselmengen durch inverse Resolution. Dissertation, Fakultät Informatik, Universität Stuttgart.
Wirth, R. & O'Rorke, P. (1991). Constraints on predicate invention. InEighth International Conference on Machine Learning. Morgan Kaufmann.
Wrobel, S. (1994). Concept formation during interactive theory revision.Machine Learning, 14:169–191.
Yardeni, E. & Shapiro, E. (1991). A type system for logic programs.Journal of Logic Programming, (10):125–153.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Stahl, I. The appropriateness of predicate invention as bias shift operation in ILP. Mach Learn 20, 95–117 (1995). https://doi.org/10.1007/BF00993476
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00993476