×

The lattice structure and refinement operators for the hypothesis space bounded by a bottom clause. (English) Zbl 1470.68186

Summary: 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.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68N17 Logic programming
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Software:

GOLEM; Aleph; SeqLog
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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).
[2] Davey, B.A., & Priestley, H. A. (2002). Introduction to lattices and order. Cambridge: Cambridge University Press. · Zbl 1002.06001
[3] 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. · Zbl 1156.68526
[4] Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: a guide to the theory of NP-completeness. New York: Freeman. · Zbl 0411.68039
[5] 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). · Zbl 1227.68104
[6] Laird, P. D. (1987). Learning from good data and bad. PhD thesis, Yale University. · Zbl 0722.68091
[7] 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). · Zbl 1099.68620
[8] Muggleton, S. (1995). Inverse entailment and Progol. New Generation Computing, 13, 245–286. · Zbl 05479869 · doi:10.1007/BF03037227
[9] 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). · Zbl 1286.68054
[10] 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).
[11] Muggleton, S. H., & Tamaddoni-Nezhad, A. (2007). QG/GA: A stochastic search for Progol. Machine Learning, 70(2–3), 123–133.
[12] Nienhuys-Cheng, S.-H., & de Wolf, R. (1997). LNAI: Vol. 1228. Foundations of inductive logic programming. Berlin: Springer. · Zbl 1293.68014
[13] Plotkin, G. D. (1971). Automatic methods of inductive inference. PhD thesis, Edinburgh University. · Zbl 0261.68042
[14] 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. · Zbl 0219.68044
[15] Rouveirol, C. (1992). Extensions of inversion of resolution applied to theory completion. In S. Muggleton (Ed.), Inductive logic programming. London: Academic Press.
[16] 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.
[17] Srinivasan, A. (2007). The Aleph manual. Oxford: University of Oxford.
[18] 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. · Zbl 0994.68516
[19] 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. · Zbl 1017.68530
[20] 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. · Zbl 1156.68330
[21] van der Laag, P. (1995). An analysis of refinement operators in inductive logic programming. Tinbergen institute research series, Rotterdam. · Zbl 0874.68047
[22] 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. · Zbl 0941.68677
[23] 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). · Zbl 1017.68537
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.