Learning Recursive Theories in the Normal ILP Setting

• Autorzy: Malerba D.
• Języki publikacji: EN

Abstrakty

EN

Induction of recursive theories in the normal ILP setting is a difficult learning task whose complexity is equivalent to multiple predicate learning. In this paper we propose computational solutions to some relevant issues raised by the multiple predicate learning problem. A separate-and-parallel-conquer search strategy is adopted to interleave the learning of clauses supplying predicates with mutually recursive definitions. A novel generality order to be imposed on the search space of clauses is investigated, in order to cope with recursion in a more suitable way. The consistency recovery is performed by reformulating the current theory and by applying a layering technique, based on the collapsed dependency graph. The proposed approach has been implemented in the ILP system ATRE and tested on some laboratory-sized and real-world data sets. Experimental results demonstrate that ATRE is able to learn correct theories autonomously and to discover concept dependencies. Finally, related works and their main differences with our approach are discussed.

Słowa kluczowe

EN

machine learning; inductive logic programming; learning recursive theories; multiple predicate learning

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 57, nr 1
• Strony: 39--77
• Opis fizyczny: Bibliogr. 66 poz.

Twórcy

autor

Malerba D.

• Dipartimento di Informatica, via Orabona 4, I-70126 Bari, Italy,

Bibliografia

• [1] Aha, D.W., Lapointe, S., Ling, C. X., Matwin, S.: Learning recursive relations with randomly selected small training sets, Proc. Eleventh International Conference on Machine Learning, 1994.
• [2] Apt, K. R.: Logic programming, in: Handbook of Theoretical Computer Science (J. van Leeuwen, Ed.), vol. B, Elsevier, Amsterdam, 1990, 493-574.
• [3] Bergadano, F., Gunetti, D.: Learning clauses by tracing derivations, in: Proc. of the Fourth International Workshop on Inductive Logic Programming (S. Wrobel, Ed.), vol. 237 of GMD-Studien, 1994.
• [4] Bergadano, F., Gunetti, D.: Inductive Logic Programming: from machine learning to software engineering, The MIT Press, Cambridge, MA, 1996.
• [5] Boström, H.: Specialization of recursive predicates, in: Machine Learning: ECML-95 (N. Lavrač, S. Wrobel, Eds.), vol. 912 of LNAI, Springer-Verlag, Berlin, 1995, 92-106.
• [6] Boström, H.: Induction of Recursive Transfer Rules, in: Learning Language in Logic (J. Cussens, S. Džeroski, Eds.), vol. 1925 of LNAI, Springer-Verlag, Berlin, 2000, 237-246.
• [7] Bratko, I.: Applications of machine learning: towards knowledge synthesis, New Generation Computing, 11, 1993, 343-360.
• [8] Buntine, W.: Generalised subsumption and its applications to induction and redundancy, Artificial Intelligence, 36, 1988, 149-176.
• [9] Cameron-Jones, R. M., Quinlan, J. R.: Avoiding pitfalls when learning recursive theories, Proc. Twelfth International Joint Conference on Artificial Intelligence, 1993.
• [10] Ceri, S., Gottlob, G., L. Tanca: What you always wanted to know about Datalog (and never dared to ask), IEEE Transactions on Knowledge and Data Engineering, 1(1), 1989, 146-166.
• [11] Cohen, W. W.: Learnability of restricted logic programs, Proc. 3rd International Workshop on Inductive Logic Programming (S. Muggleton, Ed.), 1993.
• [12] De Raedt, L.: Interactive Theory Revision, Academic Press, London, 1992.
• [13] De Raedt, L., Dehaspe, L.: Clausal discovery, Machine Learning Journal, 26(2/3), 1997, 99-146.
• [14] De Raedt, L., Lavrač, N.: The many faces of inductive logic programming, in: Methodologies for Intelligent Systems (J. Komorowski, Z.W.Raś, Eds.), vol. 689 of LNAI, Springer-Verlag, 1993, 435-449.
• [15] De Raedt, L., Lavrač, N.: Multiple predicate learning in two Inductive Logic Programming settings, Journal on Pure and Applied Logic, 4(2), 1996, 227-254.
• [16] De Raedt, L., Lavrač, N., Džeroski, S.: Multiple predicate learning, Proc. 13th International Joint Conference on Artificial Intelligence, 1993.
• [17] Džeroski, S., Bratko, I.: Handling Noise in Inductive Logic Programming, Proc. Second International Workshop on Inductive Logic Programming, Institute for New Generation Computing Technology, 1992.
• [18] Džeroski, S., Lavrač, N.: Relational Data Mining, Springer-Verlag, Berlin, 2001.
• [19] Esposito, F., D. Malerba, Lisi, F. A.: Induction of recursive theories in the normal ILP setting: issues and solutions, in: Inductive Logic Programming (J. Cussens, A. Frisch, Eds.), vol. 1866 of LNAI, Springer-Verlag, Berlin, 2000, 93-111.
• [20] Esposito, F., Malerba, D., Lisi, F. A.: Machine Learning for Intelligent Processing of Printed Documents, Journal of Intelligent Information Systems, 14(2/3), 2000, 175-198.
• [21] Esposito, F., Malerba, D., Marengo, V.: Inductive Learning from Numerical and Symbolic Data: An Integrated Framework, Intelligent Data Analysis, 5(6), 2001, 445-461.
• [22] Esposito, F., Semeraro, G., Fanizzi, N., Ferilli, S.: Multistrategy Theory Revision: Induction and Abduction in INTHELEX, Machine Learning Journal, 38(1/2), 2000, 133-156.
• [23] Flener, P., Yilmaz, S.: Inductive synthesis of recursive logic programs: achievements and prospects, Journal of Logic Programming, Special Issue on Synthesis, Transformation, and Analysis, 41(2-3), 1999, 141-195.
• [24] Fogel, L., Zaverucha, G.: Normal Programs and Multiple Predicate Learning, in: Inductive Logic Programming (D. Page, Ed.), vol. 1446 of LNAI, Springer-Verlag, 1998, 175-184.
• [25] Gelfond, M., Lifschitz, V.: Logic programs with classical negation, Proc. of the Seventh International Logic Programming Conference, MIT Press, Cambridge, 1990.
• [26] Giordana, A., Saitta, L., Baroglio, C.: Learning simple recursive theories, in: Methodologies for Intelligent Systems (J. Komorowski, Z. Raś, Eds.), vol. 689 of LNAI, Springer-Verlag, 1993, 425-434.
• [27] Gottlob, G.: Subsumption and Implication, Information Processing Letters, 24(2), 1987, 109-111.
• [28] Idestam-Almquist, P.: Generalization of clauses, Ph.D. Thesis, Department of Computer and Systems Sciences, Stockholm University and Royal Institute of Technology, Stockholm, Sweden, 1993.
• [29] Idestam-Almquist, P.: Efficient induction of recursive definitions by structural analysis of saturations, in: Advances in Inductive Logic Programming (L. De Raedt, Ed.), IOS Press, Amsterdam, 1996, 192-205.
• [30] Jorge, A., Brazdil, P.: Architecture for iterative learning of recursive definitions, in: Advances in Inductive Logic Programming (L. De Raedt, Ed.), IOS Press, Amsterdam, 1996, 206-218.
• [31] Khardon, R.: Learning to take Actions, Machine Learning Journal, 35(1), 1999, 57-90.
• [32] Khardon, R.: Learning Horn Expressions with LogAn-H, Proc. of the Seventeenth International Conference on Machine Learning, 2000.
• [33] Lamma, E., Mello, P., Milano, M., Riguzzi, F.: Integrating Extensional and Intensional ILP Systems through Abduction, Proc. of the Seventh International Workshop on Logic Program Synthesis and Transformation (LOPSTR’97), 1997.
• [34] Lapointe, S., Matwin, S.: Sub-unification: A tool for efficient induction of recursive programs, Proc. of the Ninth International Conference on Machine Learning, Morgan Kaufmann, Aberdeeen, 1992.
• [35] Lavrač, N., Džeroski, S.: Inductive Logic Programming: techniques and applications, Ellis Horwood, Chichester, 1994.
• [36] Lavrač, N., Džeroski, S., Bratko, I.: Handling imperfect data in inductive logic programming, in: Advances in Inductive Logic Programming (L. De Raedt, Ed.), IOS Press, Amsterdam, 1996, 48-64.
• [37] van Leeuwen, J.: Graph Algorithms, vol. A of Handbook of Theoretical Computer Science, Elsevier, Amsterdam, 1990, 525-631.
• [38] Levi, G., Sirovich, F.: Generalized and-or graphs, Artificial Intelligence, 7, 1976, 243-259.
• [39] Lloyd, J. W.: Foundations of Logic Programming, Second edition, Springer-Verlag, Berlin, 1987.
• [40] Lorenzo, D., Otero, R. P.: Learning to reason about actions, Proc. of the Fourteenth European Conference on Artificial Intelligence (W. Horn, Ed.), IOS Press, Amsterdam, 2000.
• [41] Malerba, D., Esposito, F., Lanza, A., Lisi, F.: Machine learning for information extraction from topographic maps, in: Geographic Data Mining and Knowledge Discovery (H. J. Miller, J. Han, Eds.), Taylor and Francis, London, 2001, 291-314.
• [42] Malerba, D., Esposito, F., Lisi, F.: Learning Recursive Theories with ATRE, Proc. Thirteenth European Conference on Artificial Intelligence (H. Prade, Ed.), JohnWiley & Sons, Chichester, 1998.
• [43] Malerba, D., Esposito, F., Semeraro, G., Caggese, S.: Learning simple recursive theories, in: AI*IA 97: Advances in Artificial Intelligence (M. Lenzerini, Ed.), vol. 1321 of LNAI, Springer-Verlag, 1997, 24-35.
• [44] Malerba, D., Semeraro, G., Esposito, F.: A multistrategy approach to learning multiple dependent concepts, in: Machine Learning and Statistics: The interface (G. Nakhaeizadeh, C. Taylor, Eds.), John Wiley & Sons, New York, 1997, 87-106.
• [45] Martin, L., Vrain, C.: A three-valued framework for the induction of general logic programs, in: Advances in Inductive Logic Programming (L. De Raedt, Ed.), IOS Press, Amsterdam, 1996, 219-235.
• [46] Michalski, R.: A theory and methodology of inductive learning, in: Machine Learning - An Artificial Intelligence Approach (R. Michalski, J. Carbonell, T. Mitchell, Eds.), Tioga Publishing Co., Palo Alto, CA, 1983, 83-133.
• [47] Mitchell, T.: Machine Learning, McGraw-Hill, 1997.
• [48] Mofizur, C., Numao, M.: Top-down induction of recursive programs from small number of sparse examples, in: Advances in Inductive Logic Programming (L. De Raedt, Ed.), IOS Press, Amsterdam, 1996, 236-253.
• [49] Muggleton, S.: Inductive Logic Programming, Academic Press, London, 1992.
• [50] Muggleton, S.: Inverting Implication, Proceedings of the 2nd International Workshop on Inductive Logic Programming (S. Muggleton, K. Furukawa, Eds.), 1992.
• [51] Muggleton, S.: Inverse Entailment and Progol, New Generation Computing, 13(3/4), 1995, 245-286.
• [52] Muggleton, S., Bryant, C.: Theory completion using inverse entailment, in: Inductive Logic Programming (J. Cussens, A. Frisch, Eds.), vol. 1866 of LNAI, Springer-Verlag, 2000, 130-146.
• [53] Nagy, G., Seth, S., Stoddard, S.: A prototype document image analysis system for technical journals, IEEE Computer, 25(7), 1992, 10-22.
• [54] Nienhuys-Cheng, S.-W., de Wolf, R.: A complete method for program specialization based upon unfolding, Proc. Twelfth European Conference on Artificial Intelligence, 1996.
• [55] Nienhuys-Cheng, S.-W., de Wolf, R.: The Subsumption theorem in inductive logic programming: Facts and fallacies, in: Advances in Inductive Logic Programming (L. De Raedt, Ed.), IOS Press, Amsterdam, 1996, 265-276.
• [56] Nienhuys-Cheng, S.-W., de Wolf, R.: Foundations of inductive logic programming, Springer, Heidelberg, 1997.
• [57] Pazzani, M., Kibler, D.: The utility of knowledge in inductive learning, Machine Learning Journal, 9, 1992, 57-94.
• [58] Plotkin, G.: A note on inductive generalization, vol. 5 of Machine Intelligence, Edinburgh University Press, Edinburgh, 1970, 153-163.
• [59] Plotkin, G.: A further note on inductive generalization, vol. 6 of Machine Intelligence, Edinburgh University Press, Edinburgh, 1971, 101-124.
• [60] Ramakrishnan, R., Srivastava, D., Sudarshan, S.: Rule ordering in bottom-up fixpoint evaluation of logic programs, IEEE Transactions on Knowledge and Data Engineering, 6, 1994, 501-517.
• [61] Rouveirol, C.: Flattening and saturation: Two representation changes for generalization, Machine Learning Journal, 14(2), 1994, 219-232.
• [62] Sommer, E.: FENDER: an approach to theory restructuring (extended abstract), in: Machine Learning: ECML-95 (N. Lavrač, S. Wrobel, Eds.), vol. 912 of LNAI, Springer-Verlag, 1994, 356-359.
• [63] Sommer, E.: An approach to quantifying the quality of induced theories, Proc. IJCAI Workshop on Machine Learning and Comprehensibility (C. Nedellec, Ed.), 1995.
• [64] Toussaint, J., Schmid, U., Wysotzki, F.: Using recursive control rules in planning, Proc. of ICAI Session on Learning and Adapting in AI Planning, Las Vegas, 2001.
• [65] Van Laer, W., De Raedt, L., Džeroski, S.: On Multi-Class Problems and Discretization in Inductive Logic Programming, in: Proceedings of the 10th International Symposium on Methodologies for Intelligent Systems (ISMIS97) (Z. Raś, A. Skowron, Eds.), vol. 1325 of LNAI, Springer-Verlag, 1997, 277-286.
• [66] Zelezny, F., Miksovsky, P., Stepankova, O., Zidek, J.: ILP for Automated Telephony, Inductive Logic Programming (Work in Progress) (J. Cussens, A. Frisch, Eds.), 2000.