A comparative study on methods for reducing myopia of hill-climbing search in multirelational learning

ABSTRACT

Hill-climbing search is the most commonly used search algorithm in ILP systems because it permits the generation of theories in short running times. However, a well known drawback of this greedy search strategy is its myopia. Macro-operators (or macros for short), a recently proposed technique to reduce the search space explored by exhaustive search, can also be argued to reduce the myopia of hill-climbing search by automatically performing a variable-depth look-ahead in the search space. Surprisingly, macros have not been employed in a greedy learner. In this paper, we integrate macros into a hill-climbing learner. In a detailed comparative study in several domains, we show that indeed a hill-climbing learner using macros performs significantly better than current state-of-the-art systems involving other techniques for reducing myopia, such as fixed-depth look-ahead, template-based look-ahead, beam-search, or determinate literals. In addition, macros, in contrast to some of the other approaches, can be computed fully automatically and do not require user involvement nor special domain properties such as determinacy.

REFERENCES

• 1: Hendrik Blockeel , Luc De Raedt, Lookahead and Discretization in ILP, Proceedings of the 7th International Workshop on Inductive Logic Programming, p.77-84, September 17-20, 1997
• 2: Hendrik Blockeel , Luc De Raedt, Top-down induction of first-order logical decision trees, Artificial Intelligence, v.101 n.1-2, p.285-297, May 1998 [doi>10.1016/S0004-3702(98)00034-4]
• 3: William W. Cohen, Pac-learning non-recursive Prolog clauses, Artificial Intelligence, v.79 n.1, p.1-38, Nov. 1995 [doi>10.1016/0004-3702(94)00034-4]
• 4: Luc De Raedt , Wim Van Laer, Inductive Constraint Logic, Proceedings of the 6th International Conference on Algorithmic Learning Theory, p.80-94, October 18-20, 1995
• 5: Dolšak, B., Bratko, I., & Jezernik, A. (1998). Application of machine learning in finite element computation. Machine learning and data mining: methods and applications, 147--171.
• 6: Džeroski, S., & Bratko, I. (1992). Handling noise in inductive logic programming. Proc. of the 2nd Int. Workshop on ILP.
• 7: Saso Dzeroski , Nico Jacobs , Martín Molina , Carlos Moure , Stephen Muggleton , Wim Van Laer, Detecting Traffic Problems with ILP, Proceedings of the 8th International Workshop on Inductive Logic Programming, p.281-290, July 22-24, 1998
• 8: Džeroski, S., & Lavračč, N. (2001). Introduction to inductive logic programming. In S. Džeroski and N. Lavrač (Eds.), Relational data mining, 48--73.
• 9: Peter A. Flach , Nicolas Lachiche, IBC: A First-Order Bayesian Classifier, Proceedings of the 9th International Workshop on Inductive Logic Programming, p.92-103, June 24-27, 1999
• 10: Johannes Fürnkranz, Separate-and-Conquer Rule Learning, Artificial Intelligence Review, v.13 n.1, p.3-54, Jan. 1999 [doi>10.1023/A:1006524209794]
• 11: Fürnkranz, J., & Flach, P. (2003). An analysis of rule evaluation metrics. Proc. of the 20th ICML (pp. 202--209).
• 12: Nada Lavrač , Peter A. Flach, An extended transformation approach to inductive logic programming, ACM Transactions on Computational Logic (TOCL), v.2 n.4, p.458-494, Oct. 2001 [doi>10.1145/383779.383781]
• 13: Lavrač, N., Železný, F., & Flach, P. (2003). RSD: Relational subgroup discovery through first-order feature construction. Proc. of the 12th Int. Conf. on ILP (pp. 149--165).
• 14: Muggleton, S. (1995). Inverse entailment and Progol. New Generation Computing, 13, 245--286.
• 15: Michael J. Pazzani , Clifford A. Brunk, Detecting and correcting errors in rule-based expert systems: an integration of empirical and explanation-based learning, Knowledge Acquisition, v.3 n.2, p.157-173, June 1991 [doi>10.1016/1042-8143(91)90003-6]
• 16: Peña Castillo, L. (2004). Search improvements in multirelational learning. Doctoral dissertation, Ottovon-Guericke-University Magdeburg.
• 17: Lourdes Peña Castillo , Stefan Wrobel, Macro-Operators in Multirelational Learning: A Search-Space Reduction Technique, Proceedings of the 13th European Conference on Machine Learning, p.357-368, August 19-23, 2002
• 18: Quinlan, J. R. (1991). Determinate literals in inductive logic programming. Proc. of the 12th IJCAI (pp. 746--750).
• 19: Quinlan, J. R., & Cameron-Jones, R. M. (1995). Induction of logic programs: FOIL and related systems. New Generation Computing, 13, 287--312.
• 20: Silverstein, G., & Pazzani, M. J. (1991). Relational clichéés: constraining constructive induction during relational learning. Proc. of the 8th Int. Workshop on Machine Learning (pp. 203--207).
• 21: Ashwin Srinivasan , S. H. Muggleton , M. J. E. Sternberg , R. D. King, Theories for mutagenicity: a study in first-order and feature-based induction, Artificial Intelligence, v.85 n.1-2, p.277-299, Aug. 1996 [doi>10.1016/0004-3702(95)00122-0]
• 22: Jean-Daniel Zucker , Jean-Gabriel Ganascia, Learning Structurally Indeterminate Clauses, Proceedings of the 8th International Workshop on Inductive Logic Programming, p.235-244, July 22-24, 1998