Bayesian inductive logic programming

ABSTRACT

Inductive Logic Programming (ILP) involves the construction of first-order definite clause theories from examples and background knowledge. Unlike both traditional Machine Learning and Computational Learning Theory, ILP is based on lock-step development of Theory, Implementations and Applications. ILP systems have successful applications in the learning of structure-activity rules for drug design, semantic grammars rules, finite element mesh design rules and rules for prediction of protein structure and mutagenic molecules. The strong applications in ILP can be contrasted with relatively weak PAC-learning results (even highly restricted forms of logic programs are known to be prediction-hard). It has been recently argued that the mismatch is due to distributional assumptions made in application domains. These assumptions can be modelled as a Bayesian prior probability representing subjective degrees of belief. Other authors have argued for the use of Bayesian prior distributions for reasons different to those here, though this has not lead to a new model of polynomial-time learnability. Incorporation of Bayesian prior distributions over time-bounded hypotheses in PAC leads to a new model called U-learnability. It is argued that U-learnability is more appropriate than PAC for Universal (Turing computable) languages. Time-bounded logic programs have been shown to be polynomially U-learnable under certain distributions. The use of time bounded hypotheses enforces decidability and allows a unified characterization of speed-up learning and inductive learning. U-learnability has as special cases PAC and Natarajan's model of speed-up learning.

REFERENCES

• 1: B. Arbab and D. Michie. Generating rules from examples. In IJCAI-85, pages 631-633, Los Altos, CA, 1985. Kaufmann.
• 2: Shai Ben-David , Benny Chor , Oded Goldreich , Michael Luby, On the theory of average case complexity, Journal of Computer and System Sciences, v.44 n.2, p.193-219, April 1992 [doi>10.1016/0022-0000(92)90019-F]
• 3: R. Board and L. Pitt. On the necessity of Occam algorithms. UIUCDCS-R-89-1544, University of Illinois at Urbana-Champaign, 1989.
• 4: I. Bratko. Generating human-understandable decision rules. Working paper, E. Kardelj University Ljubljana, Ljubljana, Yugoslavia, 1983.
• 5: B. Buchanan, E. Feigenbaum, and N. Sridharan. Heuristic theory formation: data interpretation and rule formation. In B. Meltzer and D. Michie, editors, Machine intelligence 7, pages 267-290. Edinburgh University Press, 1972.
• 6: W. Buntine. A Theory of Learning Classification Rules. PhD thesis, School of Computing Science, University of Technology, Sydney, 1990.
• 7: W. Cohen. Learnability of restricted logic programs. In S. Muggleton, editor, Proceedings of the 3rd International Workshop on Inductive Logic Programming (Technical report IJS-DP-6707 of the Josef Stefan Institute, Ljubljana, Slovenia), pages 41-72, 1993.
• 8: A.K. Debnath, R.L Lopez de Compadre, G. Debnath, A.J. Schusterman, and C. Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds, correlation with molecular orbital energies and hydrophobicity. Journal of Medicinal Chemistry, 34(2):786 - 797, 1991.
• 9: B. Dolsak and S. Muggleton. The application of Inductive Logic Programming to finite element mesh design. In S. Muggleton, editor, Inductive Logic Programming. Academic Press, London, 1992.
• 10: 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]
• 11: 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
• 12: David Haussler , Michael Kearns , Robert Schapire, Bounds on the sample complexity of Bayesian learning using information theory and the VC dimension, Proceedings of the fourth annual workshop on Computational learning theory, p.61-74, August 05-07, 1991, Santa Cruz, California, United States
• 13: Nicolas Helft, Induction as nonmonotonic inference, Proceedings of the first international conference on Principles of knowledge representation and reasoning, p.149-156, December 1989
• 14: Christopher John Hogger, Essentials of logic programming, Oxford University Press, Inc., New York, NY, 1990
• 15: P. Idestam-Almquist. Generalisation of Clauses. PhD thesis, Stockholm University, 1993.
• 16: D. Johnson. The NP-completeness column--an ongoing guide. Journal of Algorithms, 4:284-299, 1984.
• 17: M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73049]
• 18: 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
• 19: 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. Proceedings of the National Academy of Sciences, 89(23), 1992.
• 20: Nada Lavrac , Saso Dzeroski, Inductive Logic Programming: Techniques and Applications, Routledge, New York, NY, 1993
• 21: 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
• 22: J. W. Lloyd, Foundations of logic programming, Springer-Verlag New York, Inc., New York, NY, 1984
• 23: Stephen Muggleton, Inductive logic programming, New Generation Computing, v.8 n.4, p.295-318, 1991 [doi>10.1007/BF03037089]
• 24: S. Muggleton, editor. Inductive Logic Programming. Academic Press, 1992.
• 25: Stephen Muggleton, Inductive logic programming: derivations, successes and shortcomings, ACM SIGART Bulletin, v.5 n.1, p.5-11, Jan. 1994 [doi>10.1145/181668.181671]
• 26: S. Muggleton. Mode-directed inverse resolution. In K. Furukawa, D. Michie, and S. Muggleton, editors, Machine Intelligence 14. Oxford University Press, (to appear).
• 27: S. Muggleton and W. Buntine. Machine invention of first-order predicates by inverting resolution. In Proceedings of the Fifth International Conference on Machine Learning, pages 339-352. Kaufmann, 1988.
• 28: S. Muggleton and C. Feng. Efficient induction of logic programs. In Proceedings of the First Conference on Algorithmic Learning Theory, Tokyo, 1990. Ohmsha.
• 29: S. Muggleton, R. King, and M. Sternberg. Protein secondary structure prediction using logic-based machine learning. Protein Engineering, 5(7):647-657, 1992.
• 30: S. Muggleton and D. Page. A learnability model for universal representations. Technical Report PRG-TR-3- 94, Oxford University Computing Laboratory, Oxford, 1994.
• 31: S. Muggleton and L. De Raedt. Inductive logic programming: Theory and methods. Journal of Logic Programming, 12, 1994. (to appear).
• 32: 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
• 33: B. K. Natarajan, On learning from exercises, Proceedings of the second annual workshop on Computational learning theory, p.72-87, December 1989, Santa Cruz, California, United States
• 34: D. Page and A. Frisch. Generalization and learnability: A study of constrained atoms. In S. Muggleton, editor, Inductive Logic Programming. Academic Press, London, 1992.
• 35: Leonard Pitt , Leslie G. Valiant, Computational limitations on learning from examples, Journal of the ACM (JACM), v.35 n.4, p.965-984, Oct. 1988 [doi>10.1145/48014.63140]
• 36: G. Plotkin. A further note on inductive generalization. In Machine Intelligence, volume 6. Edinburgh University Press, 1971.
• 37: G.D. Plotkin. A note on inductive generalisation. In B. Meltzer and D. Michie, editors, Machine Intelligence 5, pages 153-163. Elsevier North Holland, New York, 1970.
• 38: Pat Langley, Editorial: Advice to Machine Learning Authors, Machine Learning, v.5 n.3, p.233-237, Aug. 1990 [doi>10.1023/A:1022647305786]
• 39: L. De Raedt and M. Bruynooghe. A theory of clausal discovery. In Proceedings of the 13th International Joint Conference on Artificial Intelligence. Morgan Kaufmann, 1993.
• 40: L. De Raedt and S. Dzeroski. First-orderjk-clause theories are pac-learnable. Technical report, Department of Computer Science, Katholieke Universieit Leuven, Heverlee, Belgium, 1994.
• 41: Claude Sammut , Scott Hurst , Dana Kedzier , Donald Michie, Learning to fly, Proceedings of the ninth international workshop on Machine learning, p.385-393, July 1992, Aberdeen, Scotland, United Kingdom
• 42: A. Srinivasan and S. Muggleton. Discovering rules for mutagenesis. Technical Report PRG-TR-4-94, Oxford University Computing Laboratory, Oxford, 1994.
• 43: M. Sternberg, R. King, R. Lewis, and S. Muggleton. Application of machine learning to structural molecular biology. Philosophical Transactions of the Royal Society B, 1994 (to appear).
• 44: M. Sternberg, R. Lewis, R. King, and S. Muggleton. Modelling the structure and function of enzymes by machine learning. Proceedings of the Royal Society of Chemistry: Faraday Discussions, 93:269-280, 1992.
• 45: J. Zelle and R. Mooney. Learning semantic grammars with constructive inductive logic programming. In Proceedings of the Eleventh National Conference on Artificial Intelligence, pages 817-822, San Mateo, CA, 1993. Morgan Kaufmann.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing

General Terms:
Theory