Inductive logic programming: derivations, successes and shortcomings

ABSTRACT

Inductive Logic Programming (ILP) is a research area which investigates the construction of first-order definite clause theories from examples and background knowledge. ILP systems have been applied successfully in a number of real-world domains. These include the learning of structure-activity rules for drug design, finite-element mesh design rules, rules for primary-secondary prediction of protein structure and fault diagnosis rules for satellites. There is a well established tradition of learning-in-the-limit results in ILP. Recently some results within Valiant's PAC-learning framework have also been demonstrated for ILP systems. In this paper it is argued that algorithms can be directly derived from the formal specifications of ILP. This provides a common basis for Inverse Resolution, Explanation-Based Learning, Abduction and Relative Least General Generalisation. A new general-purpose, efficient approach to predicate invention is demonstrated. ILP is underconstrained by its logical specification. Therefore a brief overview of extra-logical constraints used in ILP systems is given. Some present limitations and research directions for the field are identified.

REFERENCES

• 1: R. Banerji. Learning in the limit in a growing language. In <i>IJCAI-87,</i> pages 280--282, San Mateo, CA, 1987. Morgan-Kaufmann.
• 2: F. Bergadano. Towards an inductive logic programming language. Technical report, University of Torino, Torino, Italy, 1992.
• 3: Francesco Bergadano , Attilio Giordana, Guiding induction with domain theories, Machine learning: an artificial intelligence approach volume III, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 4: I. Bratko, S. Muggleton, and A. Varsek. Learning qualitative models of dynamic systems. In <i>Proceedings of the Eighth International Machine Learning Workshop,</i> San Mateo, Ca, 1991. Morgan-Kaufmann.
• 5: B. Cestnik, I. Kononenko, and I. Bratko. Assistant 86: a knowledge-elicitation tool for sophisticated users. In <i>Progress in machine learning,</i> pages 31--45, Wilmslow, England, 1987. Sigma.
• 6: Peter Clark , Tim Niblett, The CN2 Induction Algorithm, Machine Learning, v.3 n.4, p.261-283, March 1989 [doi>10.1023/A:1022641700528]
• 7: William W. Cohen, Compiling prior knowledge into an explicit basis, Proceedings of the ninth international workshop on Machine learning, p.102-110, July 1992, Aberdeen, Scotland, United Kingdom
• 8: D. Conklin and I. Witten. Complexity-based induction. Technical report, Dept. of Computing and Information Science, Queen's University, Kingston, Ontario, Canada, 1992.
• 9: Luc De Raedt , Maurice Bruynooghe, Interactive Concept-Learning and Constructive Induction by Analogy, Machine Learning, v.8 n.2, p.107-150, March 1992 [doi>10.1023/A:1022664419589]
• 10: L. de Raedt and M. Bruynooghe. A theory of clausal discovery. CW 165, Dept. of Computer Science, Katholieke Universiteit Leuven, Leuven, Belgium, 1992.
• 11: L. de Raedt, N. Lavrac, and S. Dzeroski. Multiple predicate learning. CW 65, Dept. of Computer Science, Katholieke Universiteit Leuven, Leuven, Belgium, 1992.
• 12: G. DeJong. Generalisations based on explanations. In <i>IJCAI-81,</i> pages 67--69, San Mateo, CA, 1981. Morgan-Kaufmann.
• 13: B. Dolsak and S. Muggleton. The application of Inductive Logic Programming to finite element mesh design. In S. Muggleton, editor, <i>Inductive Logic Programming,</i> London, 1992. Academic Press.
• 14: S. Dzeroski. Handling noise in inductive logic programming, 1991. MSc thesis: University of Ljubljana.
• 15: S. Dzeroski and N. Lavrac. Refinement graphs for FOIL and LINUS. In S. Muggleton, editor, <i>Inductive Logic Programming.</i> Academic Press, London, 1992.
• 16: 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]
• 17: C. Feng. Inducing temporal fault dignostic rules from a qualitative model. In S. Muggleton, editor, <i>Inductive Logic Programming.</i> Academic Press, London, 1992.
• 18: Cao Feng , Stephen Muggleton, Towards inductive generalisation in higher order logic, Proceedings of the ninth international workshop on Machine learning, p.154-162, July 1992, Aberdeen, Scotland, United Kingdom
• 19: D. Gentner. Structure-mapping: a theoretical framework for analogy. <i>Cognitive Science,</i> 7:155--170, 1983.
• 20: D. Gillies. Confirmation theory and machine learning. In <i>Proceedings of the Second Inductive Learning Workshop,</i> Tokyo, 1992. ICOT TM-1182.
• 21: M. Harao. Analogical reasoning based on higher-order unification. In <i>Proceedings of the First International Conference on Algorithmic Learning Theory,</i> Tokyo, 1990. Ohmsha.
• 22: David Haussler, Applying valiant's learning framework to Al concept-learning problems, Machine learning: an artificial intelligence approach volume III, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 23: P. Idestam-Almquist. Generalization under implication: Expansion of clauses for linear roots. Technical report, Dept. of Computer and Systems Sciences, Stockholm University, 1992.
• 24: Jörg-Uwe Kietz, Some Lower Bounds for the Computational Complexity of Inductive Logic Programming, Proceedings of the European Conference on Machine Learning, p.115-123, April 05-07, 1993
• 25: J-U. Kietz and S. Wrobel. Controlling the complexity of learning in logic through syntactic and task-oriented models. In S. Muggleton, editor, <i>Inductive Logic Programming.</i> Academic Press, London, 1992.
• 26: R. King, S. Muggleton R. Lewis, and M. Sternberg. Drug design by machine learning: The use of inductive logic programming to model the structure-activity relationships of trimethoprim analogues binding to dihydrofolate reductase. <i>Proceedings of the National Academy of Sciences,</i> 89(23), 1992.
• 27: R. Kowalski. Logic Programming in Artificial Intelligence. In <i>IJCAI-91: proceedings of the twelfth international joint conference on artificial intelligence,</i> pages 596--603, San Mateo, CA, 1991. Morgan-Kaufmann.
• 28: P. Langley, G. L Bradshaw, and H. Simon. Rediscovering chemistry with the Bacon system. In R. Michalski, J. Carbonnel, and T. Mitchell, editors, <i>Machine Learning: An Artificial Intelligence Approach,</i> pages 307--330. Tioga, Palo Alto, CA, 1983.
• 29: Stéphane Lapointe , Stan Matwin, Sub-unification: a tool for efficient induction of recursive programs, Proceedings of the ninth international workshop on Machine learning, p.273-281, July 1992, Aberdeen, Scotland, United Kingdom
• 30: D. B. Lenat. On automated scientific theory formation: a case study using the AM program. In J. E. Hayes and D. Michie, editors, <i>Machine Intelligence 9.</i> Horwood, New York, 1981.
• 31: J. W. Lloyd, Foundations of logic programming, Springer-Verlag New York, Inc., New York, NY, 1984
• 32: A. Kakas P. Mancarella. Generalized stable models: a semantics for abduction. In L. Aiello, E. Sandewall, G. Hagert, and B. Gustavsson, editors, <i>ECAI-90: proceedings of the ninth European conference on artificial intelligence,</i> pages 385--391, London, 1990. Pitman.
• 33: R. Michalski, I. Mozetic, J. Hong, and N. Lavrac. The AQ15 inductive learning system: an overview and experiments. In <i>Proceedings of IMAL 1986,</i> Orsay, 1986. Universit&eacute; de Paris-Sud.
• 34: Tom M. Mitchell , Richard M. Keller , Smadar T. Kedar-Cabelli, Explanation-Based Generalization: A Unifying View, Machine Learning, v.1 n.1, p.47-80 [doi>10.1023/A:1022691120807]
• 35: F. Mizoguchi and H. Ohwada. Constraint-directed generalization for learning spatial relations. In <i>Proceedings of the Second Inductive Learning Workshop,</i> Tokyo, 1992. ICOT TM-1182.
• 36: E. Morales. Learning chess patterns. In S. Muggleton, editor, <i>Inductive Logic Programming.</i> Academic Press, London, 1992.
• 37: S. Muggleton. A strategy for constructing new predicates in first order logic. In <i>Proceedings of the Third European Working Session on Learning,</i> pages 123--130. Pitman, 1988.
• 38: Stephen Muggleton, Inductive logic programming, New Generation Computing, v.8 n.4, p.295-318, 1991 [doi>10.1007/BF03037089]
• 39: S. Muggleton. <i>Inductive Logic Programming.</i> Academic Press, 1992.
• 40: S. Muggleton. Inverting implication. <i>Artificial Intelligence Journal,</i> 1993. (to appear).
• 41: S. Muggleton. Predicate invention and utility. <i>Journal of Experimental and Theoretical Artificial Intelligence,</i> 1993. (to appear).
• 42: S. Muggleton and C. Feng. Efficient induction of logic program. In S. Muggleton, editor, <i>Inductive Logic Programming,</i> London, 1992. Academic Press.
• 43: S. Muggleton, R. King, and M. Sternberg. Protein secondary structure prediction using logic-based machine learning. <i>Protein Engineering,</i> 5(7):647--657, 1992.
• 44: Stephen Muggleton , Ashwin Srinivasan , Michael Bain, Compression, significance and accuracy, Proceedings of the ninth international workshop on Machine learning, p.338-347, July 1992, Aberdeen, Scotland, United Kingdom
• 45: S. H. Muggleton and W. Buntine. Machine invention of first-order predicates by inverting resolution. In <i>Proceedings of the Fifth International Conference on Machine Learning,</i> pages 339--352. Kaufmann, 1988.
• 46: D. Page and A. Frisch. Generalization and learnability: A study of constrained atoms. In S. Muggleton, editor, <i>Inductive Logic Programming.</i> Academic Press, London, 1992.
• 47: M. Pazzani, C. Brunk, and G. Silverstein. An information-based approach to integrating empirical and explanation-based learning. In S. Muggleton, editor, <i>Inductive Logic Programming.</i> Academic Press, London, 1992.
• 48: G. D. Plotkin, <i>Automatic Methods of Inductive Inference.</i> PhD thesis, Edinburgh University, August 1971.
• 49: J. R. Quinlan. Generating production rules from decision trees. In <i>Proceedings of the Tenth International Conference on Artificial Intelligence,</i> pages 304--307, San Mateo, CA:, 1987. Morgan-Kaufmann.
• 50: J. R. Quinlan. Determinate literals in inductive logic programming. In <i>IJCAI-91: Proceedings of the Twelfth International Joint Conference on Artificial Intelligence,</i> pages 746--750, San Mateo, CA:, 1991. Morgan-Kaufmann.
• 51: J. R. Quinlan, Learning Logical Definitions from Relations, Machine Learning, v.5 n.3, p.239-266, Aug. 1990 [doi>10.1023/A:1022699322624]
• 52: Bradley Lance Richards, An operator-based approach to first-order theory revision, University of Texas at Austin, Austin, TX, 1992
• 53: C. Rouveirol. Extensions of inversion of resolution applied to theory completion. In S. Muggleton, editor, <i>Inductive Logic Programming.</i> Academic Press, London, 1992.
• 54: S. Russell. Tree-structured bias. In <i>Proceedings of the Eighth National Conference on Artificial Intelligence,</i> San Mateo, CA, 1988. Morgan-Kaufmann.
• 55: C. Sammut and R. B Banerji. Learning concepts by asking questions. In R. Michalski, J. Carbonnel, and T. Mitchell, editors, <i>Machine Learning: An Artificial Intelligence Approach. Vol. 2,</i> pages 167--192. Morgan-Kaufmann, San Mateo, CA, 1986.
• 56: Ehud Y. Shapiro, Algorithmic Program DeBugging, MIT Press, Cambridge, MA, 1983
• 57: A. Srinivasan, S. Muggleton, and M. Bain. Distinguishing exceptions from noise in non-monotonic learning. In S. Muggleton, editor, <i>Proceedings of the Second Inductive Logic Programming Workshop.</i> ICOT TM-1182, Tokyo, 1992.
• 58: M. Sternberg, R. Lewis, R. King, and S. Muggleton. Modelling the structure and function of enzymes by machine learning. <i>Proceedings of the Royal Society of Chemistry: Faraday Discussions,</i> 93:269--280, 1992.
• 59: Mark E. Stickel, A Prolog technology theorem prover: implementation by an extended Prolog computer, Journal of Automated Reasoning, v.4 n.4, p.353-380, Dec. 1988 [doi>10.1007/BF00297245]
• 60: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• 61: R. Wirth. Learning by failure to prove. In <i>EWSL-88,</i> pages 237--251, London, 1988. Pitman.
• 62: R. Wirth and P. O'Rorke. Constraints for predicate invention. In S. Muggleton, editor, <i>Inductive Logic Programming,</i> London, 1992. Academic Press.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

General Terms:
Theory