nach oben

Journal of Intelligent Information Systems

Erschienen in:

01.08.2016

Predicate invention-based specialization in Inductive Logic Programming

verfasst von: Stefano Ferilli

Erschienen in: Journal of Intelligent Information Systems | Ausgabe 1/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Three relevant areas of interest in symbolic Machine Learning are incremental supervised learning, multistrategy learning and predicate invention. In many real-world tasks, new observations may point out the inadequacy of the learned model. In such a case, incremental approaches allow to adjust it, instead of learning a new model from scratch. Specifically, when a negative example is wrongly classified by a model, specialization refinement operators are needed. A powerful way to specialize a theory in Inductive Logic Programming is adding negated preconditions to concept definitions. This paper describes an empowered specialization operator that allows to introduce the negation of conjunctions of preconditions using predicate invention. An implementation of the operator is proposed, and experiments purposely devised to stress it prove that the proposed approach is correct and viable even under quite complex conditions.

Vorheriger Artikel Behavioral process mining for unstructured processes

Nächster Artikel The use of data-derived label hierarchies in multi-label classification

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

The missing expressiveness due to the lack of functions can be recovered by flattening (Rouveirol 1994), a representational change that transforms a program containing function symbols into another, semantically equivalent one, made up of function-free clauses. While in general the latter might be infinite, in a supervised learning setting the universe is limited by what is present in the examples. Applying flattening to constants, seen as 0-ary functions, allows to obtain constant-free programs.

Substitutions are mappings from variables to terms (Siekmann 1990). By extension, applying a substitution σ to a term or clause t means applying σ to all variables in t. σ ⁻¹ denotes the corresponding antisubstitution, i.e. the inverse function, of a substitution σ; σ ⁻¹ maps some terms to variables.

Variables denoted by _ are new variables, managed as in Prolog.

For the sake of readability, in the Examples we use a propositional representation. So, the residual is unique for each subsumption, and the subscript in Δ_i(⋅,⋅) is unnecessary.

Note that maximizing this simple function is equivalent to maximizing more complex functions, e.g.: \(|\mathcal {P}_{\mathcal {S}} \setminus \mathcal {P}_{\mathcal {S}'}| = |\mathcal {P}_{\mathcal {S}}| - |\mathcal {P}_{\mathcal {S}'}| ; |\overline {\mathcal {P}_{\mathcal {S}'}} \setminus \overline {\mathcal {P}_{\mathcal {S}}}| = |\overline {\mathcal {P}_{\mathcal {S}'}}| - |\overline {\mathcal {P}_{\mathcal {S}}}| ; |\mathcal {P}_{\mathcal {S}}| / |\mathcal {P}_{\mathcal {S}'}| ; |\overline {\mathcal {P}_{\mathcal {S}'}}| / |\overline {\mathcal {P}_{\mathcal {S}}}|\). Indeed, considering that \(S \subset S' \Rightarrow \overline {\mathcal {P}_{S}} \subseteq \overline {\mathcal {P}_{S'}} \Rightarrow |\overline {\mathcal {P}_{S'}} \setminus \overline {\mathcal {P}_{S}}| = |\overline {\mathcal {P}_{S'}}| - |\overline {\mathcal {P}_{S}}|\) (already noticed) and \(S \subset S' \Rightarrow \mathcal {P}_{S'} \subseteq \mathcal {P}_{S} \Rightarrow |\mathcal {P}_{S} \setminus \mathcal {P}_{S'}| = |\mathcal {P}_{S}| - |\mathcal {P}_{S'}|\) we have: \(|\mathcal {P}_{S} \setminus \mathcal {P}_{S'}| \cdot |\overline {\mathcal {P}_{S'}} \setminus \overline {\mathcal {P}_{S}}| = (|\mathcal {P}_{S}| - |\mathcal {P}_{S'}|) \cdot (|\overline {\mathcal {P}_{S'}}| - |\overline {\mathcal {P}_{S}}|) = (|\mathcal {P}_{S}| - |\mathcal {P}_{S'}|) \cdot (1 - |\mathcal {P}_{S'}| - (1 - |\mathcal {P}_{S}|)) = (|\mathcal {P}_{S}| - |\mathcal {P}_{S'}|) \cdot (1 - |\mathcal {P}_{S'}| - 1 + |\mathcal {P}_{S}|) = (|\mathcal {P}_{S}| - |\mathcal {P}_{S'}|) \cdot (|\mathcal {P}_{S}| - |\mathcal {P}_{S'}|) = (|\mathcal {P}_{S}| - |\mathcal {P}_{S'}|)^{2} \Rightarrow |\overline {\mathcal {P}_{S'}}| - |\overline {\mathcal {P}_{S}}| = |\mathcal {P}_{S}| - |\mathcal {P}_{S'}|\) (as expected, since elements move between the partition components). So, since \(|\mathcal {P}_{S}|\) is fixed, maximizing \((|\mathcal {P}_{S}| - |\mathcal {P}_{S'}|)\) or \((|\mathcal {P}_{\mathcal {S}}| / |\mathcal {P}_{\mathcal {S}'}|)\) is the same as minimizing \(|\mathcal {P}_{S'}|\) or maximizing \(|\overline {\mathcal {P}_{S'}}|\), which is the same (again, being \(|\overline {\mathcal {P}_{S}}|\) fixed) as maximizing \((|\overline {\mathcal {P}_{S}}| - |\overline {\mathcal {P}_{S'}}|)\) or \((|\overline {\mathcal {P}_{\mathcal {S}'}}| / |\overline {\mathcal {P}_{\mathcal {S}}}|)\). Also, minimizing \(|\mathcal {P}_{S'}|\) (the number of still non-covered positive examples after the addition of r) we have: \(\arg \min _{r \in \mathcal {R}} |\mathcal {P}_{S \cup \{r\}}| = \arg \min _{r \in \mathcal {R}} (-|\mathcal {P}_{S} \setminus \mathcal {P}_{r}|) = \arg \max _{r \in \mathcal {R}} |\mathcal {P}_{S} \setminus \mathcal {P}_{r}|\) Also note that this algorithm encompasses the old single-literal approach. Indeed, if a single literal can preserve coverage of all previous positive examples, it will have \(|\mathcal {P}_{S'}| = |\mathcal {P}_{\{r\}}| = |\mathcal {P}_{r}| = |\mathcal {P}^{C}|\), and since \(|\mathcal {P}_{S'}| \leq |\mathcal {P}^{C}|\) it will be selected at the first iteration. Then, at the end of the first iteration it will be \(\mathcal {P}_{S} = \emptyset \) and the execution will exit the loop and terminate.

This is slightly harder than in (Ferilli et al. 2015), where 7 positive and 1 negative examples were used.

Bain, M, Muggleton S (1992) Non-monotonic learning. Inductive Logic Programming, pages 145–161. Academic Press.

Bergadano, F, Gunetti D, Nicosia M, Ruffo G (1995) Learning logic programs with negation as failure. L. De Raedt, editor Proceedings of ILP-95, 33–51.

Ceri, S, Gottlob G, Tanca L (1990) Logic programming and databases. Springer-verlag, heidelberg Germany.CrossRef

Clark, KL (1978) Negation as failure. H. Gallaire and J. Minker, editors, Logic and Databases, pages 293–322. Plenum Press.

Esposito, F, Fanizzi N, Ferilli S, Semeraro G (2001a) A generalization model based on oi-implication for ideal theory refinement. Fundamenta Informaticae 47 (1-2): 15–33.

Esposito, F, Fanizzi N, Ferilli S, Semeraro G (2001b) OI-implication, Soundness and refutation completeness. Inproceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI-2001), pages 847–852 Morgan Kaufmann.

Esposito, F, Laterza A, Malerba D, Semeraro G (1996) Locally finite, proper and complete operators for refining datalog programs. Z. W. Raś and M. Michalewicz, editors, Foundations of Intelligent Systems, number 1079 in Lecture Notes in Artificial Intelligence, pages 468–478.. Springer.

Esposito, F., Semeraro G., Fanizzi N., revision S. Ferilli. (2000) Multistrategy theory Induction and abduction in inthelex. Machine Learning Journal 38 (1/2): 133–156.CrossRefMATH

Fanizzi, N, Ferilli S, Semeraro G, Esposito F (2001) On the decidability of OI-implication. proceedings of the Work in Progress Track of the 11th International Conference on Inductive Logic Programming (ILP-2001)– Research report, 27–37.

Ferilli, S (2014) Toward an improved downward refinement operator for inductive logic programming. Atti del 11th Italian Convention on Computational Logic (CILC-2014), volume 1195 of Central Europe (CEUR) Workshop Proceedings, 99–113.

Ferilli, S, Fatiguso G (2015) An approach to predicate invention based on statistical relational model. AI*IA Advances in Artificial Intelligence, volume 9336 of Lecture Notes in Artificial Intelligence, pages 274–287, 2015.

Ferilli, S, Pazienza A, Esposito F (2015) Empowered negative specialization in inductive logic programming. AI*IA Advances in Artificial Intelligence, volume 9336 of Lecture Notes in Artificial Intelligence, pages 288–300, 2015.

Idestam-Almquist, P (1993) Generalization of Clauses. PhD thesis, Stockholm University and Royal Institute of Technology. Kista, Sweden.MATH

Inoue, K, Kudoh Y (1997) Learning extended logic programs. proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI-97), volume 1, pages 176–181 Morgan Kaufmann.

Kok, S, Domingos P (2007) Statistical predicate invention. Zoubin Ghahramani, editor, ICML, volume 227 of ACM International Conference Proceeding Series, pages 433–440. ACM.

Lloyd, JW (1987) Foundations of logic programming. Springer-Verlag, Berlin. second edition.CrossRefMATH

Muggleton, S, de Raedt L (1994) Inductive logic programming (ILP). J Log Program 19: 629–679.MathSciNetCrossRefMATH

Muggleton, SH, Lin D, Tamaddoni-Nezhad A (2015) Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited. Mach Learn 100 (1): 49–73.MathSciNetCrossRefMATH

Nédellec, C, Rouveirol C, Adé H, Bergadano F, Tausend B (1996) Declarative bias in ILP. L. de Raedt, editor, Advances in Inductive Logic Programming, pages 82–103. IOS Press, Amsterdam, NL.

Nienhuys-cheng, S-H, de Wolf R (1997) Foundations of Inductive Logic Programming, volume 1228 of Lecture Notes in Artificial Intelligence Springer.

Reiter, R (1980) Equality and domain closure in first order databases. J ACM 27: 235–249.MathSciNetCrossRefMATH

Reynolds, JC (1970) Transformational systems and the algebraic structure of atomic formulas. Mach Intell 5: 135–151.MathSciNetMATH

Rouveirol, C (1994) Flattening and saturation: Two representation changes for generalization. Mach Learn 14 (2): 219–232.CrossRefMATH

Schmidt-Schauss, M (1988) Implication of clauses is undecidable. Theor Comput Sci 59: 287–296.MathSciNetCrossRefMATH

Semeraro, G, Esposito F, Malerba D, Fanizzi N, Ferilli S (1998) A logic framework for the incremental inductive synthesis of datalog theories. N. E. Fuchs, editor, Logic Program Synthesis and Transformation, number 1463 in Lecture Notes in Computer Science, pages 300–321. Springer-Verlag.

Shapiro, EY (1981) Inductive inference of theories from facts. Technical Report Research Report 192 Yale University.

Shapiro, EY (1983) Algorithmic program debugging MIT Press.

Siekmann, JH (1990). R. B. Banerji, editor, Formal Techniques in Artificial Intelligence - A Sourcebook, pages 460–464. Elsevier Science Publisher.

Srinivasan, A, Muggleton S, Bain M (1995) Machine intelligence, 13. chapter The Justification of Logical Theories Based on Data Compression, pages 87–121. Oxford University Press, Inc, New York, USA.

Wrobel, S (1994) Concept formation and knowledge revision. Kluwer Academic Publishers, Dordrecht Boston London.CrossRefMATH

Titel: Predicate invention-based specialization in Inductive Logic Programming
verfasst von: Stefano Ferilli
Publikationsdatum: 01.08.2016
Verlag: Springer US
Erschienen in: Journal of Intelligent Information Systems / Ausgabe 1/2016
Print ISSN: 0925-9902
Elektronische ISSN: 1573-7675
DOI: https://doi.org/10.1007/s10844-016-0412-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2016

Efficient energy-based embedding models for link prediction in knowledge graphs

Improving the prediction of page access by using semantically enhanced clustering

Recent advances in mining patterns from complex data

A semantic approach to remove incoherent items from a user profile and improve the accuracy of a recommender system

The use of data-derived label hierarchies in multi-label classification

Evidential data mining: precise support and confidence

Premium Partner