An extended transformation approach to inductive logic programming

ABSTRACT

Inductive logic programming (ILP) is concerned with learning relational descriptions that typically have the form of logic programs. In a transformation approach, an ILP task is transformed into an equivalent learning task in a different representation formalism. Propositionalization is a particular transformation method, in which the ILP task is compiled to an attribute-value learning task. The main restriction of propositionalization methods such as LINUS is that they are unable to deal with nondeterminate local variables in the body of hypothesis clauses. In this paper we show how this limitation can be overcome., by systematic first-order feature construction using a particular individual-centered feature bias. The approach can be applied in any domain where there is a clear notion of individual. We also show how to improve upon exhaustive first-order feature construction by using a relevancy filter. The proposed approach is illustrated on the “trains” and “mutagenesis” ILP domains.

REFERENCES

• 1: Rakesh Agrawal , Heikki Mannila , Ramakrishnan Srikant , Hannu Toivonen , A. Inkeri Verkamo, Fast discovery of association rules, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 2: Francesco Bergadano , Daniele Gunetti, Inductive Logic Programming: From Machine Learning to Software Engineering, MIT Press, Cambridge, MA, 1995
• 3: Ivan Bratko , Igor Mozetič , Nada Lavrač, KARDIO: a study in deep and qualitative knowledge for expert systems, MIT Press, Cambridge, MA, 1990
• 4: CARUANA,R.AND FREITAG, D. 1994. Greedy attribute selection. In Proceedings of the 11th International Conference on Machine Learning. Morgan Kaufmann, 28-36.
• 5: CHEVALEYRE,Y.AND ZUCKER, J. 2000. Noise-tolerant rule induction from multi-instance data. In Proceedings of the ICML-2000 workshop on Attribute-Value and Relational Learning: Crossing the Boundaries, L. De Raedt and S. Kramer, Eds.
• 6: Peter Clark , Robin Boswell, Rule induction with CN2: some recent improvements, Proceedings of the European working session on learning on Machine learning, p.151-163, March 1991, Porto, Portugal
• 7: Peter Clark , Tim Niblett, The CN2 Induction Algorithm, Machine Learning, v.3 n.4, p.261-283, March 1989 [doi>10.1023/A:1022641700528]
• 8: COHEN, W. 1996. Learning trees and rules with set-valued features. In Proceedings of the 14th National Conference on Artificial Intelligence. AAAI Press, 709-716.
• 9: Luc De Raedt, Attribute-Value Learning Versus Inductive Logic Programming: The Missing Links (Extended Abstract), Proceedings of the 8th International Workshop on Inductive Logic Programming, p.1-8, July 22-24, 1998
• 10: Luc Dehaspe , Hannu Toivonen, Discovery of frequent DATALOG patterns, Data Mining and Knowledge Discovery, v.3 n.1, p.7-36, March 1999 [doi>10.1023/A:1009863704807]
• 11: Thomas G. Dietterich , Richard H. Lathrop , Tomás Lozano-Pérez, Solving the multiple instance problem with axis-parallel rectangles, Artificial Intelligence, v.89 n.1-2, p.31-71, Jan. 1997 [doi>10.1016/S0004-3702(96)00034-3]
• 12: Sašo Džeroski , Stephen Muggleton , Stuart Russell, PAC-learnability of determinate logic programs, Proceedings of the fifth annual workshop on Computational learning theory, p.128-135, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130399]
• 13: Usama M. Fayyad , Gregory Piatetsky-Shapiro , Padhraic Smyth , Ramasamy Uthurusamy, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 14: FENSEL, D., ZICKWOLFF, M., AND WIESE, M. 1995. Are substitutions the better examples? Learning complete sets of clauses with Frog. In Proceedings of the 5th International Workshop on Inductive Logic Programming, L. De Raedt, Ed. Department of Computer Science, Katholieke Universiteit Leuven, 453-474.
• 15: Peter A. Flach , Christophe G. Giraud-Carrier , John W. Lloyd, Strongly Typed Inductive Concept Learning, Proceedings of the 8th International Workshop on Inductive Logic Programming, p.185-194, July 22-24, 1998
• 16: 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
• 17: Peter A. Flach, Knowledge Representation for Inductive Learning, Proceedings of the European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty, p.160-167, July 05-09, 1999
• 18: FLACH,P.A.AND KAKAS, A. C. 2000. Abductive and inductive reasoning: background and issues. In Abductive and inductive reasoning: essays on their relation and integration, P. A. Flach and A. C. Kakas, Eds. Kluwer Academic Publishers.
• 19: Peter A. Flach , Nicolas Lachiche, Confirmation-guided discovery of first-order rules with tertius, Machine Learning, v.42 n.1/2, p.61-95, Jan. 2001 [doi>10.1023/A:1007656703224]
• 20: Dragan Gamberger, A Minimization Approach to Propositional Inductive Learning, Proceedings of the 8th European Conference on Machine Learning, p.151-160, April 25-27, 1995
• 21: GEIBEL,P.AND WYSOTZKI, F. 1996. Relational learning with decision trees. In Proceedings of the 12th European Conference on Artificial Intelligence. 428-432.
• 22: JOHN, G., KOHAVI, R., AND PFLEGER, K. 1994. Irrelevant features and the subset selection problem. In Proceedings of the 11th International Conference on Machine Learning. Morgan Kaufmann, 190-198.
• 23: Antonis C. Kakas , Fabrizio Riguzzi, Learning with Abduction, Proceedings of the 7th International Workshop on Inductive Logic Programming, p.181-188, September 17-20, 1997
• 24: Khalid Khan , Stephen Muggleton , Rupert Parson, Repeat Learning Using Predicate Invention, Proceedings of the 8th International Workshop on Inductive Logic Programming, p.165-174, July 22-24, 1998
• 25: Willi Klösgen, Explora: a multipattern and multistrategy discovery assistant, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 26: Ron Kohavi , Dan Sommerfield , James Dougherty, Data Mining using MLC++, A Machine Learning Library in C++, Proceedings of the 8th International Conference on Tools with Artificial Intelligence (ICTAI '96), p.234, November 16-19, 1996
• 27: KOLLER,D.AND SAHAMI, M. 1996. Toward optimal feature selection. In Proceedings of the 13th International Conference on Machine Learning. 284-292.
• 28: Stefan Kramer , Bernhard Pfahringer , Christopher Helma, Stochastic Propositionalization of Non-determinate Background Knowledge, Proceedings of the 8th International Workshop on Inductive Logic Programming, p.80-94, July 22-24, 1998
• 29: Nada Lavrac , Saso Dzeroski, Background Knowledge and Declarative Bias in Inductive Concept Learning, Proceedings of the International Workshop on Analogical and Inductive Inference, p.51-71, October 05-09, 1992
• 30: Nada Lavrac , Saso Dzeroski, Inductive Logic Programming: Techniques and Applications, Routledge, New York, NY, 1993
• 31: Nada Lavrač , Sašo Džeroski , Marko Grobelnik, Learning nonrecursive definitions of relations with LINUS, Proceedings of the European working session on learning on Machine learning, p.265-281, March 1991, Porto, Portugal
• 32: LAVRAC, N., GAMBERGER,D.,AND DZEROSKI, S. 1995. An approach to dimensionality reduction in learning from deductive databases. In Proceedings of the 5th International Workshop on Inductive Logic Programming, L. De Raedt, Ed. Department of Computer Science, Katholieke Universiteit Leuven, 337-354.
• 33: LAVRAC, N., GAMBERGER,D.,AND JOVANOSKI, V. 1999. A study of relevance for learning in deductive databases. Journal of Logic Programming 40, 2/3 (August/September), 215-249.
• 34: Nada Lavrac , Dragan Gamberger , Peter Turney, A Relevancy Filter for Constructive Induction, IEEE Intelligent Systems, v.13 n.2, p.50-56, March 1998 [doi>10.1109/5254.671092]
• 35: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 36: LLOYD, J. 1999. Programming in an integrated functional and logic language. Journal of Functional and Logic Programming 1999, 3 (March).
• 37: MICHALSKI, R. 1983. A theory and methodology of inductive learning. In Machine Learning: An Artificial Intelligence Approach, R. Michalski, J. Carbonell, and T. Mitchell, Eds. Vol. I. Tioga, Palo Alto, CA, 83-134.
• 38: MICHIE, D., MUGGLETON, S., PAGE,D.,AND SRINIVASAN, A. 1994. To the international computing community: A new East-West challenge. Tech. rep., Oxford University Computing laboratory, Oxford, UK.
• 39: Fumio Mizoguchi , Hayato Ohwada , Makiki Daidoji , Shiroteru Shirato, Learning Rules That Classify Ocular Fundus Images for Glaucoma Diagnosis, Selected Papers from the 6th International Workshop on Inductive Logic Programming, p.146-159, August 26-28, 1996
• 40: MUGGLETON, S., Ed. 1992. Inductive Logic Programming. Academic Press.
• 41: MUGGLETON, S. 1995. Inverse entailment and Progol. New Generation Computing, Special issue on Inductive Logic Programming 13, 3-4, 245-286.
• 42: MUGGLETON,S.AND DE RAEDT, L. 1994. Inductive logic programming: Theory and methods. Journal of Logic Programming 19/20, 629-679.
• 43: MUGGLETON,S.AND FENG, C. 1990. Efficient induction of logic programs. In Proceedings of the 1st Conference on Algorithmic Learning Theory. Ohmsha, Tokyo, Japan, 368-381.
• 44: MUGGLETON, S., KING, R., AND STERNBERG, M. 1992. Protein secondary structure prediction using logic. In Proceedings of the 2nd International Workshop on Inductive Logic Programming, S. Muggleton, Ed. Report ICOT TM-1182. 228-259.
• 45: Stephen Muggleton , Ashwin Srinivasan , Ross D. King , Michael J. E. Sternberg, Biochemical Knowledge Discovery Using Inductive Logic Programming, Proceedings of the First International Conference on Discovery Science, p.326-341, December 14-16, 1998
• 46: Shan-Hwei Nienhuys-Cheng , R. De Wolf , Ronald de Wolf , J. Siekmann , J. G. Carbonell, Foundations of Inductive Logic Programming, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 47: Arlindo L. Oliveira , Alberto Sangiovanni-Vincentelli, Constructive induction using a non-greedy strategy for feature selection, Proceedings of the ninth international workshop on Machine learning, p.355-360, July 1992, Aberdeen, Scotland, United Kingdom
• 48: Giulia Pagallo , David Haussler, Boolean Feature Discovery in Empirical Learning, Machine Learning, v.5 n.1, p.71-99, Mar. 1990 [doi>10.1023/A:1022611825350]
• 49: J. R. Quinlan, Learning Logical Definitions from Relations, Machine Learning, v.5 n.3, p.239-266, Aug. 1990 [doi>10.1023/A:1022699322624]
• 50: Céline Rouveirol, Flattening and Saturation: Two Representation Changes for Generalization, Machine Learning, v.14 n.2, p.219-232, Feb. 1994 [doi>10.1023/A:1022678217288]
• 51: SEBAG,M.AND ROUVEIROL, C. 1997. Tractable induction and classification in first-order logic via stochastic matching. In Proceedings of the 15th International Joint Conference on Artificial In-telligence. Morgan Kaufmann, 888-893.
• 52: SKALAK, D. 1994. Prototype and feature selection by sampling and random mutation hill climbing algorithms. In Proceedings of the 11th International Conference on Machine Learning. Morgan Kaufmann, 293-301.
• 53: Ashwin Srinivasan , Ross D. King, Feature Construction with Inductive Logic Programming: A Study of Quantitative Predictions of Biological Activity by Structural Attributes, Selected Papers from the 6th International Workshop on Inductive Logic Programming, p.89-104, August 26-28, 1996
• 54: STAHL, I. 1996. Predicate invention in inductive logic programming. In Advances in Inductive Logic Programming, L. De Raedt, Ed. IOS Press, 34-47.
• 55: TURNEY, P. 1996. Low size-complexity inductive logic programming: The East-West challenge considered as a problem in cost-sensitive classification. In Advances in Inductive Logic Programming, L. De Raedt, Ed. IOS Press, 308-321.
• 56: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 57: Ian H. Witten , Eibe Frank, Data mining: practical machine learning tools and techniques with Java implementations, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 58: WNEK,J.AND MICHALSKI, R. 1991. Hypothesis-driven constructive induction in AQ17: A method and experiments. In Proceedings of IJCAI-91 Workshop on Evaluating and Changing Represen-tations in Machine Learning. Sydney, 13-22.
• 59: Stefan Wrobel, An Algorithm for Multi-relational Discovery of Subgroups, Proceedings of the First European Symposium on Principles of Data Mining and Knowledge Discovery, p.78-87, June 24-27, 1997
• 60: 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
• 61: ZUCKER, J.-D. AND GANASCIA, J.-G. 1996. Representation changes for efficient learning in structural domains. In Proceedings of the 13th International Conference on Machine Learning, L. Saitta, Ed. Morgan Kaufmann, 543-551.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Predicate logic
      I.2.6 Learning
          Subjects: Induction

General Terms:
Algorithms, Experimentation

Keywords:
data mining, inductive logic programming, machine learning, relational databases