Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Scaling Up Inductive Logic Programming by Learning from Interpretations

  • Published:
Data Mining and Knowledge Discovery Aims and scope Submit manuscript

Abstract

When comparing inductive logic programming (ILP) and attribute-value learning techniques, there is a trade-off between expressive power and efficiency. Inductive logic programming techniques are typically more expressive but also less efficient. Therefore, the data sets handled by current inductive logic programming systems are small according to general standards within the data mining community. The main source of inefficiency lies in the assumption that several examples may be related to each other, so they cannot be handled independently.

Within the learning from interpretations framework for inductive logic programming this assumption is unnecessary, which allows to scale up existing ILP algorithms. In this paper we explain this learning setting in the context of relational databases. We relate the setting to propositional data mining and to the classical ILP setting, and show that learning from interpretations corresponds to learning from multiple relations and thus extends the expressiveness of propositional learning, while maintaining its efficiency to a large extent (which is not the case in the classical ILP setting).

As a case study, we present two alternative implementations of the ILP system TILDE (Top-down Induction of Logical DEcision trees): TILDEclassic, which loads all data in main memory, and TILDELDS, which loads the examples one by one. We experimentally compare the implementations, showing TILDELDS can handle large data sets (in the order of 100,000 examples or 100 MB) and indeed scales up linearly in the number of examples.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Agrawal, R., H. Mannila, H., Srikant, R., Toivonen, H. and Verkamo, A.I. 1996. Fast discovery of association rules. In U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, editors, Advances in Knowledge Discovery and Data Mining, pages 307-328. The MIT Press.

  • Blockeel, H. and De Raedt, L. 1997. Lookahead and discretization in ILP. In Proceedings of the 7th International Workshop on Inductive Logic Programming, volume 1297 of Lecture Notes in Artificial Intelligence, pages 77-85. Springer-Verlag.

  • Blockeel, H. and De Raedt, L. 1998. Top-down induction of first order logical decision trees. Artificial Intelligence, 101(1–2):285-297.

    Google Scholar 

  • Blockeel, H., De Raedt, L. and Ramon, J. 1998. Top-down induction of clustering trees. In Proceedings of the 15th International Conference on Machine Learning, pages 55-63. http://www.cs.kuleuven.ac.be/~ml/PS/ML 98-56.ps.

  • Bongard, M. 1970. Pattern Recognition. Spartan Books.

  • Bratko, I. 1990. Prolog Programming for Artificial Intelligence. Addison-Wesley. 2nd Edition.

  • Bratko, I. and Muggleton, S. 1995. Applications of inductive logic programming. Communications of the ACM, 38(11):65-70.

    Google Scholar 

  • Breiman, L., Friedman, J.H., Olshen, R.A. and Stone, C.J. 1984. Classification and Regression Trees. Wadsworth, Belmont.

    Google Scholar 

  • Cohen, W.W. 1995. Pac-learning recursive logic programs: Negative results. Journal of Artificial Intelligence Research, 2:541-573.

    Google Scholar 

  • Cohen, W.W. and Page, D. 1995. Polynomial learnability and inductive logic programming: methods and results. New Generation Computing, 13.

  • Cussens, J. 1997. Part-of-speech tagging using progol. In Proceedings of the 7th International Workshop on Inductive Logic Programming, volume 1297 of Lecture Notes in Artificial Intelligence, pages 93-108. Springer-Verlag.

  • De Raedt, L., editor. 1996. Advances in Inductive Logic Programming, volume 32 of Frontiers in Artificial Intelligence and Applications. IOS Press.

  • De Raedt, L. 1997. Logical settings for concept learning. Artificial Intelligence, 95:187-201.

    Google Scholar 

  • De Raedt, L. 1998. Attribute-value learning versus inductive logic programming: the missing links (extended abstract). In Proceedings of the 8th International Conference on Inductive Logic Programming, volume 1446 of Lecture Notes in Artificial Intelligence, pages 1-8. Springer-Verlag.

  • De Raedt, L., Blockeel, H., Dehaspe, L. and Van Laer, W. 1998. Three companions for first order data mining. In S. Džeroski and N. Lavrač, editors, Inductive Logic Programming for Knowledge Discovery in Databases, Lecture Notes in Artificial Intelligence. Springer-Verlag. To appear.

  • De Raedt, L. and Dehaspe, L. 1997. Clausal discovery. Machine Learning, 26:99-146.

    Google Scholar 

  • De Raedt, L. and Džeroski, S. 1994. First order jk-clausal theories are PAC-learnable. Artificial Intelligence, 70:375-392.

    Google Scholar 

  • De Raedt, L. and Van Laer, W. 1995. Inductive constraint logic. In Klaus P. Jantke, Takeshi Shinohara, and Thomas Zeugmann, editors, Proceedings of the 6th International Workshop on Algorithmic Learning Theory, volume 997 of Lecture Notes in Artificial Intelligence, pages 80-94. Springer-Verlag.

  • Dehaspe, L. and De Raedt, L. 1997. Mining association rules in multiple relations. In Proceedings of the 7th International Workshop on Inductive Logic Programming, volume 1297 of Lecture Notes in Artificial Intelligence, pages 125-132. Springer-Verlag.

  • Dietterich, T. G., Lathrop, R.H. and Lozano-Pérez, T. 1997. Solving the multiple-instance problem with axis-parallel rectangles. Artificial Intelligence, 89(1–2):31-71.

    Google Scholar 

  • Dougherty, J., Kohavi, R. and Sahami, M. 1995. Supervised and unsupervised discretization of continuous features. In A. Prieditis and S. Russell, editors, Proc. Twelfth International Conference on Machine Learning. Morgan Kaufmann.

  • Džeroski, S., Muggleton, S. and Russell, S. 1992. PAC-learnability of determinate logic programs. In Proceedings of the 5th ACM workshop on Computational Learning Theory, pages 128-135.

  • Elmasri, R. and Navathe, S.B. 1989. Fundamentals of Database Systems. The Benjamin/Cummings Publishing Company, 2nd edition.

  • Fayyad, U.M. and Irani, K.B. 1993. Multi-interval discretization of continuous-valued attributes for classification learning. In Proceedings of the 13th International Joint Conference on Artificial Intelligence, pages 1022-1027, San Mateo, CA. Morgan Kaufmann.

    Google Scholar 

  • Fürnkranz, J. 1997a. Dimensionality reduction in ILP: a call to arms. In L. De Raedt and S. Muggleton, editors, Proceedings of the IJCAI-97 Workshop on Frontiers of ILP. http://www.cs.kuleuven.ac.be/~lucdr/filp.html.

  • Fürnkranz, J. (1997b). Noise-tolerant windowing. In M. E. Pollack, editor, Proceedings of the 15th International Joint Conference on Artificial Intelligence, pages 852-857. Morgan Kaufmann.

  • Jacobs, N., Driessens, K. and De Raedt, L. 1998. Using ILP systems for verification and validation of multi agent systems. In Proceedings of the 8th International Conference on Inductive Logic Programming, pages 145-154. Springer-Verlag.

  • Kitano, H., Veloso, M., Matsubara, H., Tambe, M., Coradeschi, S., Noda, I., Stone, P., Osawa, E. and Asada, M. 1997. The robocup synthetic agent challenge 97. In Proceedings of the 15th International Joint Conference on Artificial Intelligence, pages 24-29. Morgan Kaufmann.

  • Kramer, S. 1996. Structural regression trees. In Proceedings of the 13th National Conference on Artificial Intelligence (AAAI-96).

  • Lavrač, N. and S. Džeroski, editors. 1997. Proceedings of the 7th International Workshop on Inductive Logic Programming, volume 1297 of Lecture Notes in Artificial Intelligence. Springer-Verlag.

  • Mehta, M., Agrawal, R. and Rissanen, J. 1996. SLIQ: A fast scalable classifier for data mining. In Proceedings of the Fifth International Conference on Extending Database Technology.

  • Morik, K. and Brockhausen, P. 1997. A multistrategy approach to relational discovery in databases. Machine Learning, 27(3): 287-312.

    Google Scholar 

  • Muggleton, S. 1993. Optimal layered learning: a PAC approach to incremental sampling. In Proceedings of the 4th Conference on Algorithmic Learning Theory. Ohmsha, Tokyo, Japan. Invited paper.

  • Muggleton, S. 1995. Inverse entailment and Progol. New Generation Computing, 13.

  • Muggleton, S., editor. 1997. Proceedings of the 6th International Workshop on Inductive Logic Programming, volume 1314 of Lecture Notes in Artificial Intelligence. Springer-Verlag.

  • Muggleton, S. and De Raedt, L. 1994. Inductive logic programming: Theory and methods. Journal of Logic Programming, 19, 20:629-679.

    Google Scholar 

  • Page, D., editor. 1998. Proceedings of the 8th International Conference on Inductive Logic Programming, volume 1446 of Lecture Notes in Artificial Intelligence. Springer-Verlag.

  • Plotkin, G. 1970. A note on inductive generalization. In Machine Intelligence, volume 5, pages 153-163. Edinburgh University Press.

  • Quinlan, J.R. 1993a. C4.5: Programs for Machine Learning. Morgan Kaufmann series in machine learning. Morgan Kaufmann.

  • Quinlan, J.R. 1986. Induction of decision trees. Machine Learning, 1:81-106.

    Google Scholar 

  • Quinlan, J.R. 1990. Learning logical definitions from relations. Machine Learning, 5:239-266.

    Google Scholar 

  • Quinlan, J.R. 1993b. FOIL: A midterm report. In P. Brazdil, editor, Proceedings of the 6th European Conference on Machine Learning, Lecture Notes in Artificial Intelligence. Springer-Verlag.

  • Sebag, M. 1998. A stochastic simple similarity. In Proceedings of the 8th International Conference on Inductive Logic Programming, volume 1446 of Lecture Notes in Artificial Intelligence, pages 95-105. Springer-Verlag.

  • Shafer, J.C., Agrawal, R. and Mehta, M. 1996. SPRINT: A scalable parallel classifier for data mining. In Proceedings of the 22th International Conference on Very Large Databases.

  • Srinivasan, A., Muggleton, S.H., Sternberg, M.J.E. and King, R.D. 1996. Theories for mutagenicity: A study in first-order and feature-based induction. Artificial Intelligence, 85.

  • Srinivasan, A. 1998. A study of two sampling methods for analysing large data sets with ILP. This volume.

  • Van Laer, W., De Raedt, L. and Džeroski, S. 1997. On multi-class problems and discretization in inductive logic programming. In Zbigniew W. Ras and Andrzej Skowron, editors, Proceedings of the 10th International Symposium on Methodologies for Intelligent Systems (ISMIS97), volume 1325 of Lecture Notes in Artificial Intelligence, pages 277-286. Springer-Verlag.

  • Watanabe, L. and Rendell, L. 1991. Learning structural decision trees from examples. In Proceedings of the 12th International Joint Conference on Artificial Intelligence, pages 770-776.

  • Wrobel, S., Wettschereck, D., Sommer, E. and Emde, W. 1996. Extensibility in data mining systems. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). AAAI Press.

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200A, B-3001, Heverlee, Belgium

    Hendrik Blockeel, Luc De Raedt, Nico Jacobs & Bart Demoen

Authors
  1. Hendrik Blockeel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Luc De Raedt
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Nico Jacobs
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Bart Demoen
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Blockeel, H., De Raedt, L., Jacobs, N. et al. Scaling Up Inductive Logic Programming by Learning from Interpretations. Data Mining and Knowledge Discovery 3, 59–93 (1999). https://doi.org/10.1023/A:1009867806624

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1009867806624

Search

Navigation