Abstract
Inductive Logic Programming is a subfield of Machine Learning concerned with the induction of logic programs. In Shapiro's Model Inference System — a system that infers theories from examples — the use of downward refinement operators was introduced to walk through an ordered search space of clauses. Downward and upward refinement operators compute specializations and generalizations of clauses respectively. In this article we present the results of our study of completeness and properness of refinement operators for an unrestricted search space of clauses ordered by θ-subsumption. We prove that locally finite downward and upward refinement operators that are both complete and proper for unrestricted search spaces ordered by θ-subsumption do not exist. We also present a complete but improper upward refinement operator. This operator forms a counterpart to Laird's downward refinement operator with the same properties.
Chapter PDF
Similar content being viewed by others
References
P. Idestam-Almquist. Generalization under Implication by Using Or-Introduction. In P.B. Brazdil, editor, ECML-93, pages 56–64, Vienna, Austria, April 1993. LNAI-667, Springer-Verlag.
P. Idestam-Almquist. Recursive Anti-unification. In S. Muggleton, editor, ILP'93, pages 241–253, Bled, Slovenia, March 1993. Technical Report IJS-DP-6707, J. Stefan Institute.
B. Jung. On Inverting Generality Relations. In S. Muggleton, editor, ILP'93, pages 87–101, Bled, Slovenia, March 1993. Technical Report IJS-DP-6707, J. Stefan Institute.
P.R.J. van der Laag. Een Meest Algemene Verfijningsoperator voor Gereduceerde Zinnen. In NAIC-92, pages 29–39. Delftse Universitaire Pers, 1992. In Dutch, English version has appeared as Technical Report EUR-CS-92-03, Erasmus Univerity of Rotterdam, Dept. of Computer Science.
P.R.J. van der Laag and S.H. Nienhuys-Cheng. A Locally Finite and Complete Upward Refinement Operator for θ-Subsumption. In Benelearn-93. Artificial Intelligence Laboratory, Vrije Universiteit Brussel, Brussels, 1993.
P.R.J. van der Laag and S.H. Nienhuys-Cheng. Subsumption and Refinement in Model Inference. In ECML-93, pages 95–114, Vienna, Austria, April 1993. LNAI-667, Springer Verlag.
P.D. Laird. Learning from Good and Bad Data. Kluwer Academic Publishers, 1988.
S. Lapointe and S. Matwin. Subunification: A Tool for Efficient Induction of Recursive Programs. In ML-92, pages 273–280, Aberdeen, 1992. Morgan Kaufmann.
C. Ling and M. Dawes. SIM the Inverse of Shapiro's MIS. Technical report, Department of Computer Science, University of Western Ontario, London, Ontario, Canada., 1990.
S.H. Muggleton. Inverting Implication. In Muggleton, S.H., editor, Proceedings of the International Workshop on Inductive Logic Programming, 1992.
T. Niblett. A Note on Refinement Operators. In ECML-93, pages 329–335. LNAI-667, Springer Verlag, 1993.
S.H. Nienhuys-Cheng, P.R.J. van der Laag, and L.W.N. van der Torre. Constructing Refinement Operators by Decomposing Logical Implication. In P. Torasso, editor, AI * IA'93, pages 178–189, Torino, Italy, October 1993. LNAI-728, Springer-Verlag.
G.D. Plotkin. A Note on Inductive Generalization. Machine Intelligence, 5:153–163, 1970.
J.C. Reynolds. Transformational Systems and the Algebraic Structure of Atomic Formulas. Machine Intelligence, 5:135–153, 1970.
E.Y. Shapiro. Inductive Inference of Theories from Facts. Technical Report 192, Department of Computer Science, Yale University, New Haven. CT., 1981.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
van der Laag, P.R.J., Nienhuys-Cheng, SH. (1994). Existence and nonexistence of complete refinement operators. In: Bergadano, F., De Raedt, L. (eds) Machine Learning: ECML-94. ECML 1994. Lecture Notes in Computer Science, vol 784. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57868-4_66
Download citation
DOI: https://doi.org/10.1007/3-540-57868-4_66
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57868-0
Online ISBN: 978-3-540-48365-6
eBook Packages: Springer Book Archive