Abstract
Many people believe that every fourth year is a leap year. However, this rule is too general: year X is a leap year if X is divisible by 4 except if X is divisible by 100 except if X is divisible by 400. We call such a theory with alternating generalisation and specialisation a step-wise narrowed theory. We present and evaluate an extension to the ILP system Metagol which facilitates learning such theories. We enabled Metagol to learn over-general theories by allowing a limited number of false positives during learning. This variant is iteratively applied on a learning task. For each iteration after the first, positive examples are the false positives from the previous iteration and negative examples are the true positives from the previous iteration. Iteration continues until no more false positives are present. Then, the theories are combined to a single step-wise narrowed theory. We evaluate the usefulness of our approach in the leap year domain. We can show that our approach finds solutions with fewer clauses, higher accuracy, and in shorter time.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Of course, predicates with a “negative” semantic, like not_father/2, can be supplied in the background knowledge. Nevertheless, no syntactic negation can be induced.
- 2.
Nevertheless, Metagol can only abduce clauses for the predicate symbol of the first positive example and invented predicate symbols derived thereof.
- 3.
We forked from commit 1524600225a65237de9578e46127049f6f95d1a4 in the GitHub Metagol repository [14].
- 4.
Metagol\(_{SN}\) is available at https://github.com/michael-siebers/metagol/tree/ilp2018.
References
Richards, E.G.: Calendars. In: Urban, S.E., Seidelmann, P.K. (eds.) Explanatory Supplement to the Astronomical Almanac, pp. 585–624 (2013)
Quinlan, J.R.: Induction of decision trees. Mach. Learn. 1, 81–106 (1986)
Mitchell, T.M.: Machine Learning. McGraw-Hill, New York (1997)
Muggleton, S., Buntine, W.: Machine invention of first-order predicates by inverting resolution. In: Machine Learning Proceeding, pp. 339–352 (1988), https://doi.org/10.1016/B978-0-934613-64-4.50040-2
Bain, M., Muggleton, S.: Non-monotonic Learning. In: Machine Intelligence 12 - Towards an Automated Logic of Human Thought, pp. 105–120 (1991)
Malerba, D., Esposito, F., Lisi, F.A.: Learning Recursive Theories with ATRE. In: ECAI (European Conference on Artificial Intelligence), pp. 435–439 (1998)
Malerba, D.: Learning recursive theories in the normal ILP setting. Fundamenta Informaticae 57, 39–77 (2003)
Ray, O.: Nonmonotonic abductive inductive learning. J. Appl. Logic 7, 329–340 (2009)
Stahl, I.: Predicate Invention in ILP - an Overview. In: Machine Learning: ECML-1993, pp. 313–322 (1993)
Muggleton, S.H., Lin, D., Pahlavi, N., Tamaddoni-Nezhad, A.: Meta-interpretive learning: application to grammatical inference. Mach. Learn. 94, 25–49 (2014)
Lin, D., Dechter, E., Ellis, K., Tenenbaum, J., Muggleton, S.H.: Bias reformulation for one-shot function induction. In: ECAI (European Conference on Artificial Intelligence), pp. 525–530 (2014). https://doi.org/10.3233/978-1-61499-419-0-525
Cropper, A., Muggleton, S.H.: Learning higher-order logic programs through abstraction and invention. In: IJCAI (International Joint Conference on Artificial Intelligence), pp. 1418–1424 (2016)
Muggleton, S.H., Lin, D., Tamaddoni-Nezhad, A.: Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited. Mach. Learn. 100, 49–73 (2015)
Cropper, A., Muggleton, S.H.: Metagol System (2016). https://github.com/metagol/metagol
Larson, J., Michalski, R.S.: Inductive Inference of VL Decision Rules. ACM SIGART Bull., 38–44, June 1977
Siebers, M., Schmid, U., Seuß, D., Kunz, M., Lautenbacher, S.: Characterizing facial expressions by grammars of action unit sequences - a first investigation using ABL. Inf. Sci. 329, 866–875 (2016)
Acknowledgements
We like to thank Andrew Cropper for valuable discussions on negation in Metagol. This work was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – SCHM 1239/10-1.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Siebers, M., Schmid, U. (2018). Was the Year 2000 a Leap Year? Step-Wise Narrowing Theories with Metagol. In: Riguzzi, F., Bellodi, E., Zese, R. (eds) Inductive Logic Programming. ILP 2018. Lecture Notes in Computer Science(), vol 11105. Springer, Cham. https://doi.org/10.1007/978-3-319-99960-9_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-99960-9_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-99959-3
Online ISBN: 978-3-319-99960-9
eBook Packages: Computer ScienceComputer Science (R0)