More Web Proxy on the site http://driver.im/

article

An extended transformation approach to inductive logic programming

Authors:

Peter A. FlachAuthors Info & Claims

ACM Transactions on Computational Logic (TOCL), Volume 2, Issue 4

Pages 458 - 494

https://doi.org/10.1145/383779.383781

Published: 01 October 2001 Publication History

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]

AGRAWAL, R., MANNILA, H., SRIKANT, R., TOIVONEN, H., AND VERKAMO, A. 1996. Fast discovery of association rules. In Advances in Knowledge Discovery and Data Mining, U. Fayyad, G. Piatetski- Shapiro, P. Smyth, and R. Uthurusamy, Eds. AAAI Press, 307-328.]]

Digital Library

[2]

BERGADANO,F.AND GUNETTI, D. 1995. Inductive Logic Programming: From Machine Learning to Software Engineering. The MIT Press.]]

Digital Library

[3]

BRATKO, I., MOZETIC, I., AND LAVRAC, N. 1989. KARDIO: A Study in Deep and Qualitative Knowledge for Expert Systems. MIT Press, Cambridge, MA.]]

Digital Library

[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]

CLARK,P.AND BOSWELL, R. 1991. Rule induction with CN2: Some recent improvements. In Proc. Fifth European Working Session on Learning. Springer, Berlin, 151-163.]]

Digital Library

[7]

CLARK,P.AND NIBLETT, T. 1989. The CN2 induction algorithm. Machine Learning 3, 4, 261- 283.]]

Digital Library

[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]

DE RAEDT, L. 1998. Attribute-value learning versus inductive logic programming: The missing links. In Proceedings of the 8th International Conference on Inductive Logic Programming, D. Page, Ed. Lecture Notes in Artificial Intelligence, vol. 1446. Springer-Verlag, 1-8.]]

Digital Library

[10]

DEHASPE,L.AND TOIVONEN, H. 1999. Discovery of frequent datalog patterns. Data Mining and Knowledge Discovery 3, 1, 7-36.]]

Digital Library

[11]

DIETTERICH, T., LATHROP, R., AND LOZANO-PEREZ, T. 1997. Solving the multiple-instance problem with axis-parallel rectangles. Artificial Intelligence 89, 31-71.]]

Digital Library

[12]

DZEROSKI, S., MUGGLETON,S.,AND RUSSELL, S. 1992. PAC-learnability of determinate logic programs. In Proceedings of the 5th ACMWorkshop on Computational Learning Theory. ACM Press, 128-135.]]

Digital Library

[13]

FAYYAD, U., PIATETSKY-SHAPIRO, G., SMYTH,P.,AND R. UTHURUSAMY, E. 1995. Advances in Knowledge Discovery and Data Mining. The MIT Press.]]

Digital Library

[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]

FLACH, P. A., GIRAUD-CARRIER,C.,AND LLOYD, J. 1998. Strongly typed inductive concept learning. In Proceedings of the 8th International Conference on Inductive Logic Programming, D. Page, Ed. Lecture Notes in Artificial Intelligence, vol. 1446. Springer-Verlag, 185-194.]]

Digital Library

[16]

FLACH,P.A.AND LACHICHE, N. 1999. 1BC: A first-order Bayesian classifier. In Proceedings of the 9th International Workshop on Inductive Logic Programming,S.Dzeroski and P. A. Flach, Eds. Lecture Notes in Artificial Intelligence, vol. 1634. Springer-Verlag, 92-103.]]

Digital Library

[17]

FLACH, P. A. 1999. Knowledge representation for inductive learning. In Symbolic and Quantitative Approaches to Reasoning and Uncertainty (ECSQARU'99), A. Hunter and S. Parsons, Eds. Lecture Notes in Artificial Intelligence, vol. 1638. Springer-Verlag, 160-167.]]

Digital Library

[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]

FLACH,P.A.AND LACHICHE, N. 2001. Confirmation-guided discovery of first-order rules with Tertius. Machine Learning 42, 1/2, 61-95.]]

[20]

GAMBERGER, D. 1995. A minimization approach to propositional inductive learning. In Proceedings of the 8th European Conference on Machine Learning. Springer-Verlag, 151- 160.]]

Digital Library

[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]

KAKAS,A.AND RIGUZZI, F. 1997. Learning with abduction. In Proceedings of the 7th International Workshop on Inductive Logic Programming,S.Dzeroski and N. Lavrac, Eds. Lecture Notes in Artificial Intelligence, vol. 1297. Springer-Verlag, 181-188.]]

Digital Library

[24]

KHAN, K., MUGGLETON,S.,AND PARSON, R. 1998. Repeat learning using predicate invention. In Proceedings of the 8th International Conference on Inductive Logic Programming, D. Page, Ed. Lecture Notes in Artificial Intelligence, vol. 1446. Springer-Verlag, 165-174.]]

Digital Library

[25]

KLOSGEN, W. 1996. Explora: A multipattern and multistrategy discovery assistant. In Advances in Knowledge Discovery and Data Mining, U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, Eds. AAAI Press, 249-271.]]

Digital Library

[26]

KOHAVI, R., SOMMERFIELD,D.,AND DOUGHERTY, J. 1996. Data mining using MLC++: A machine learning library in C++. In Tools with Artificial Intelligence. IEEE Computer Society Press. http://www.sgi.com/Technology/mlc.]]

Digital Library

[27]

KOLLER,D.AND SAHAMI, M. 1996. Toward optimal feature selection. In Proceedings of the 13th International Conference on Machine Learning. 284-292.]]

[28]

KRAMER, S., PFAHRINGER,B.,AND HELMA, C. 1998. Stochastic propositionalization of nondeterminate background knowledge. In Proceedings of the 8th International Conference on Inductive Logic Programming, D. Page, Ed. Lecture Notes in Artificial Intelligence, vol. 1446. Springer-Verlag, 80-94.]]

Digital Library

[29]

LAVRAC,N.AND DZEROSKI, S. 1992. Background knowledge and declarative bias in inductive concept learning. In Proceedings 3rd International Workshop on Analogical and Inductive Inference, K. Jantke, Ed. Springer-Verlag, 51-71. (Invited paper).]]

Digital Library

[30]

LAVRAC,N.AND DZEROSKI, S. 1994. Inductive Logic Programming: Techniques and Applications. Ellis Horwood.]]

Digital Library

[31]

LAVRAC, N., DZEROSKI,S.,AND GROBELNIK, M. 1991. Learning nonrecursive definitions of relations with LINUS. In Proceedings of the 5th European Working Session on Learning, Y. Kodratoff, Ed. Lecture Notes in Artificial Intelligence, vol. 482. Springer-Verlag, 265-281.]]

Digital Library

[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]

LAVRAC, N., GAMBERGER,D.,AND TURNEY, P. 1998. A relevancy filter for constructive induction. IEEE Intelligent Systems 13, 2 (March-April), 50-56.]]

Digital Library

[35]

LLOYD, J. 1987. Foundations of Logic Programming, 2nd ed. Springer, Berlin.]]

Digital Library

[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]

MIZOGUCHI, F., OHWADA, H., DAIDOJI, M., AND SHIRATO, S. 1996. Learning rules that classify ocular fundus images for glaucoma diagnosis. In Proceedings of the 6th International Workshop on Inductive Logic Programming, S. Muggleton, Ed. Lecture Notes in Artificial Intelligence, vol. 1314. Springer-Verlag, 146-162.]]

Digital Library

[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]

MUGGLETON, S., SRINIVASAN, A., KING, R., AND STERNBERG, M. 1998. Biochemical knowledge discovery using Inductive Logic Programming. In Proceedings of the first Conference on Discovery Science, H. Motoda, Ed. Springer-Verlag, Berlin.]]

Digital Library

[46]

NIENHUYS-CHENG, S.-H. AND DE WOLF, R. 1997. Foundations of Inductive Logic Programming. Lecture Notes in Artificial Intelligence, vol. 1228. Springer-Verlag.]]

Digital Library

[47]

OLIVEIRA,A.AND SANGIOVANNI-VINCENTELLI, A. 1992. Constructive induction using a non-greedy strategy for feature selection. In Proceedings of the 9th International Workshop on Machine Learning. 354-360.]]

Digital Library

[48]

PAGALLO,G.AND HAUSSLER, D. 1990. Boolean feature discovery in empirical learning. Machine Learning 5, 71-99.]]

Digital Library

[49]

QUINLAN, J. 1990. Learning logical definitions from relations. Machine Learning 5, 239-266.]]

[50]

ROUVEIROL, C. 1994. Flattening and saturation: Two representation changes for generalization. Machine Learning 14, 2, 219-232.]]

Digital Library

[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]

SRINIVASAN,A.AND KING, R. 1996. Feature construction with inductive logic programming: A study of quantitative predictions of biological activity aided by structural attributes. In Proceedings of the 6th International Workshop on Inductive Logic Programming, S. Muggleton, Ed. Lecture Notes in Artificial Intelligence, vol. 1314. Springer-Verlag, 89- 104.]]

Digital Library

[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]

ULLMAN, J. 1988. Principles of Database and Knowledge Base Systems. Vol. I. Computer Science Press, Rockville, MA.]]

Digital Library

[57]

WITTEN,I.AND FRANK, E. 2000. Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations. Morgan Kaufmann.]]

Digital Library

[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]

WROBEL, S. 1997. An algorithm for multi-relational discovery of subgroups. In Proceedings of the 1st European Symposium on Principles of Data Mining and Knowledge Discovery, J. Komorowski and J. Zytkow, Eds. Springer-Verlag.]]

Digital Library

[60]

ZUCKER,J.AND GANASCIA, J. 1998. Learning structurally indeterminate clauses. In Proceedings of the 8th International Conference on Inductive Logic Programming, D. Page, Ed. Lecture Notes in Artificial Intelligence, vol. 1446. Springer-Verlag, 235-244.]]

Digital Library

[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.]]

Cited By

Lavrač NPodpečan VRobnik-Šikonja MLavrač NPodpečan VRobnik-Šikonja M(2021)Propositionalization of Relational DataRepresentation Learning10.1007/978-3-030-68817-2_4(83-105)Online publication date: 10-Mar-2021
https://doi.org/10.1007/978-3-030-68817-2_4
Jiao RZhang LLi A(2020)IEye: Personalized Image Privacy Detection2020 6th International Conference on Big Data Computing and Communications (BIGCOM)10.1109/BigCom51056.2020.00020(91-95)Online publication date: Jul-2020
https://doi.org/10.1109/BigCom51056.2020.00020
Lavrač NŠkrlj BRobnik-Šikonja M(2020)Propositionalization and embeddings: two sides of the same coinMachine Language10.1007/s10994-020-05890-8109:7(1465-1507)Online publication date: 1-Jul-2020
https://dl.acm.org/doi/10.1007/s10994-020-05890-8
Show More Cited By

Index Terms

An extended transformation approach to inductive logic programming
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
      1. Logic programming and answer set programming
  2. Machine learning
    1. Machine learning approaches
      1. Logical and relational learning
        Inductive logic learning
2. Theory of computation
  1. Logic
    1. Constraint and logic programming

Recommendations

Inductive equivalence in clausal logic and nonmonotonic logic programming

This paper provides a logical framework for comparing inductive capabilities among agents having different background theories. A background theory is called inductively equivalent to another background theory if the two theories induce the same ...
An inductive logic programming approach to statistical relational learning: Thesis

Statistical relational learning (SRL) addresses one of the central open questions of AI: the combination of relational or first-order logic with principled probabilistic and statistical approaches to inference and learning. This thesis approaches SRL ...
An extended transformation approach to Inductive Logic Programming

Reviews

Reviewer: Leon S. Sterling

Research on inductive logic programming has advanced a long way since Shapiro’s original work on the model inference system, in the early 1980s. I am a researcher who has not been closely following the field in recent years, and I found this paper to be well worth reading. It starts with a concise but clear overview of the framework of inductive logic programming. It then presents the LINUS and DINUS transformation methods, which allow the learning of both propositional and relational descriptions. The examples used here are from chess end-games and family relationships. The meat of the paper is an extension of the previously described methods to allow for limited nondeterminacy, which is discussed in the context of the well-known problem of classifying trains traveling eastwards or westwards. My only reservation is that little effort has been made trying to characterize the limits of the methods, but hopefully that will arise from further research.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computational Logic

ACM Transactions on Computational Logic Volume 2, Issue 4

Special issue devoted to Robert A. Kowalski

Oct. 2001

224 pages

ISSN:1529-3785

EISSN:1557-945X

DOI:10.1145/383779

Editors:
Krzysztof R. Apt
CWI, Amsterdam, The Netherlands
,
Antonis C. Kakas,
Fariba Sadri

Issue’s Table of Contents

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2001

Published in TOCL Volume 2, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

70
Total Citations
View Citations
837
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lavrač NPodpečan VRobnik-Šikonja MLavrač NPodpečan VRobnik-Šikonja M(2021)Propositionalization of Relational DataRepresentation Learning10.1007/978-3-030-68817-2_4(83-105)Online publication date: 10-Mar-2021
https://doi.org/10.1007/978-3-030-68817-2_4
Jiao RZhang LLi A(2020)IEye: Personalized Image Privacy Detection2020 6th International Conference on Big Data Computing and Communications (BIGCOM)10.1109/BigCom51056.2020.00020(91-95)Online publication date: Jul-2020
https://doi.org/10.1109/BigCom51056.2020.00020
Lavrač NŠkrlj BRobnik-Šikonja M(2020)Propositionalization and embeddings: two sides of the same coinMachine Language10.1007/s10994-020-05890-8109:7(1465-1507)Online publication date: 1-Jul-2020
https://dl.acm.org/doi/10.1007/s10994-020-05890-8
Quintero-Domínguez LMorell CVentura S(2019)WordificationMI: multi-relational data mining through multiple-instance propositionalizationProgress in Artificial Intelligence10.1007/s13748-019-00186-yOnline publication date: 13-May-2019
https://doi.org/10.1007/s13748-019-00186-y
Lu ZFeng YZhou WLi XCao Q(2018)Inferring Correlation between User Mobility and App Usage in Massive Coarse-grained Data TracesProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/31611711:4(1-21)Online publication date: 8-Jan-2018
https://dl.acm.org/doi/10.1145/3161171
Wu HSun MMi PTatti NNorth CRamakrishnan N(2018)Interactive Discovery of Coordinated Relationship Chains with Maximum Entropy ModelsACM Transactions on Knowledge Discovery from Data10.1145/304701712:1(1-34)Online publication date: 31-Jan-2018
https://dl.acm.org/doi/10.1145/3047017
Makki RCarvalho ESoto ABrooks SOliveira MMilios EMinghim R(2018)ATR-VisACM Transactions on Knowledge Discovery from Data10.1145/304701012:1(1-33)Online publication date: 6-Feb-2018
https://dl.acm.org/doi/10.1145/3047010
Rocha ACamacho RRuwaard JRiper H(2018)Using multi-relational data mining to discriminate blended therapy efficiency on patients based on log dataInternet Interventions10.1016/j.invent.2018.03.00312(176-180)Online publication date: Jun-2018
https://doi.org/10.1016/j.invent.2018.03.003
França MD'Avila Garcez AZaverucha G(2015)Relational knowledge extraction from neural networksProceedings of the 2015th International Conference on Cognitive Computation: Integrating Neural and Symbolic Approaches - Volume 158310.5555/2996831.2996849(146-154)Online publication date: 11-Dec-2015
https://dl.acm.org/doi/10.5555/2996831.2996849
Perovšek MVavpetič AKranjc JCestnik BLavrač N(2015)WordificationExpert Systems with Applications: An International Journal10.1016/j.eswa.2015.04.01742:17(6442-6456)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1016/j.eswa.2015.04.017
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents