Abstract
Searching the hypothesis space bounded below by a bottom clause is the basis of several state-of-the-art ILP systems (e.g. Progol, Aleph). These systems use refinement operators together with search heuristics to explore a bounded hypothesis space. It is known that the search space of these systems is limited to a sub-graph of the general subsumption lattice. However, the structure and properties of this sub-graph have not been properly characterised. In this paper firstly, we characterise the hypothesis space considered by the ILP systems which use a bottom clause to constrain the search. In particular, we discuss refinement in Progol as a representative of these ILP systems. Secondly, we study the lattice structure of this bounded hypothesis space. Thirdly, we give a new analysis of refinement operators, least generalisation and greatest specialisation in the subsumption order relative to a bottom clause. The results of this study are important for better understanding of the constrained refinement space of ILP systems such as Progol and Aleph, which proved to be successful for solving real-world problems (despite being incomplete with respect to the general subsumption order). Moreover, characterising this refinement sub-lattice can lead to more efficient ILP algorithms and operators for searching this particular sub-lattice. For example, it is shown that, unlike for the general subsumption order, efficient least generalisation operators can be designed for the subsumption order relative to a bottom clause.
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
Badea, L., & Stanciu, M. (1999). Refinement operators can be (weakly) perfect. In Proceedings of the 9th international workshop on inductive logic programming (Vol. 1634, pp. 21–32).
Davey, B.A., & Priestley, H. A. (2002). Introduction to lattices and order. Cambridge: Cambridge University Press.
Duboc, A. L., Paes, A., & Zaverucha, G. (2008). Using the bottom clause and mode declarations on FOL theory revision from examples. In Proceedings of the 18th international conference on inductive logic programming (pp. 91–106). Berlin: Springer.
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: a guide to the theory of NP-completeness. New York: Freeman.
Kuwabara, M., Ogawa, T., Hirata, K., & Harao, M. (2006). On generalization and subsumption for ordered clauses. In Proceedings of the JSAI 2005 Workshops (pp. 212–223).
Laird, P. D. (1987). Learning from good data and bad. PhD thesis, Yale University.
Lee, S. D., & De Raedt, L. (2003). Constraint based mining of first order sequences in SeqLog. In Database Support for Data Mining Applications (pp. 155–176).
Muggleton, S. (1995). Inverse entailment and Progol. New Generation Computing, 13, 245–286.
Muggleton, S., Santos, J., & Tamaddoni-Nezhad, A. (2009). Towards an ILP system based on asymmetric relative minimal generalisation. In Proceedings of the 19th international conference on inductive logic programming (to appear).
Muggleton, S. H., & Feng, C. (1990). Efficient induction of logic programs. In Proceedings of the first conference on algorithmic learning theory, Tokyo, Ohmsha (pp. 368–381).
Muggleton, S. H., & Tamaddoni-Nezhad, A. (2007). QG/GA: A stochastic search for Progol. Machine Learning, 70(2–3), 123–133.
Nienhuys-Cheng, S.-H., & de Wolf, R. (1997). LNAI: Vol. 1228. Foundations of inductive logic programming. Berlin: Springer.
Plotkin, G. D. (1971). Automatic methods of inductive inference. PhD thesis, Edinburgh University.
Reynolds, J. C. (1969). Transformational systems and the algebraic structure of atomic formulas. In B. Meltzer & D. Michie (Eds.), Machine intelligence 5 (pp. 135–151). Edinburgh: Edinburgh University Press.
Rouveirol, C. (1992). Extensions of inversion of resolution applied to theory completion. In S. Muggleton (Ed.), Inductive logic programming. London: Academic Press.
Srinivasan, A. (2000). A study of two probabilistic methods for searching large spaces with ilp. Technical Report PRG-TR-16-00, Oxford University Computing Laboratory, Oxford.
Srinivasan, A. (2007). The Aleph manual. Oxford: University of Oxford.
Tamaddoni-Nezhad, A., & Muggleton, S. H. (2000). Searching the subsumption lattice by a genetic algorithm. In J. Cussens & A. Frisch (Eds.), Proceedings of the 10th international conference on inductive logic programming (pp. 243–252). Berlin: Springer.
Tamaddoni-Nezhad, A., & Muggleton, S. H. (2002). A genetic algorithms approach to ILP. In Proceedings of the 12th international conference on inductive logic programming (pp. 285–300). Berlin: Springer.
Tamaddoni-Nezhad, A., & Muggleton, S. H. (2008). A note on refinement operators for IE-based ILP systems. In LNAI: Vol. 5194. Proceedings of the 18th international conference on inductive logic programming (pp. 297–314). Berlin: Springer.
van der Laag, P. (1995). An analysis of refinement operators in inductive logic programming. Tinbergen institute research series, Rotterdam.
van der Laag, P. R. J., & Nienhuys-Cheng, S. H. (1994). Existence and nonexistence of complete refinement operators. In Machine learning. ECML-94: European conference on machine learning, Catania, Italy, April 6–8, 1994: Proceedings (pp. 307–322). Berlin: Springer.
Zelezny, F., Srinivasan, A., & Page, D. (2003). Lattice-search runtime distributions may be heavy-tailed. In S. Matwin & C. Sammut (Eds), Proceedings of the 12th international conference on inductive logic programming (Vol. 2583, pp. 333–345).
Author information
Authors and Affiliations
Corresponding author
Additional information
Editors: Filip Zelezny and Nada Lavrac
Rights and permissions
About this article
Cite this article
Tamaddoni-Nezhad, A., Muggleton, S. The lattice structure and refinement operators for the hypothesis space bounded by a bottom clause. Mach Learn 76, 37–72 (2009). https://doi.org/10.1007/s10994-009-5117-7
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10994-009-5117-7