Knowledge Refactoring for Inductive Program Synthesis
Open accessAbstract
Humans constantly restructure knowledge to use it more efficiently. Our goal is to give a machine learning system similar abilities so that it can learn more efficiently. We introduce the knowledge refactoring problem, where the goal is to restructure a learner's knowledge base to reduce its size and to minimise redundancy in it. We focus on inductive logic programming, where the knowledge base is a logic program. We introduce Knorf, a system which solves the refactoring problem using constraint optimisation. A key feature of Knorf is that, rather than simply removing knowledge, it also introduces new knowledge through predicate invention. We evaluate our approach on two domains: building Lego structures and real-world string transformations. Our experiments show that learning from refactored knowledge can improve predictive accuracies fourfold and reduce learning times by half.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Knorf compresses the learnt program by removing redundancies in it after learning to solve user-supplied tasks in the lifelong learning setting.
“After learning to solve user-supplied tasks in the lifelong learning setting, Knorf compresses the learnt program by removing redundancies in it.”
From Inductive Logic Programming At 30: A New Introduction (2022) · cites this paper as Dumancic et al., 2021
Section 4.4 (p. 5) says Knorf seeks a smaller refactored program with less redundancy, and Related Work (p. 2) says it refactors knowledge after learning. But the lifelong-learning description (p. 6) distinguishes earlier learned background tasks from user-provided target tasks, which are solved using that background knowledge. It does not support the claim that Knorf compresses the program after learning to solve the user-provided tasks. (LLM, conf=0.85)
Experimental — accuracy not yet measuredKnorf substantially reduces the size of the BK program, reducing the number of literals in a program by 50% or more.
“Moreover, the authors also demonstrate that Knorf substantially reduces the size of the BK program, reducing the number of literals in a program by 50% or more.”
From Inductive Logic Programming At 30: A New Introduction (2022) · cites this paper as Dumancic et al., 2021
Section 5.1 (p. 6) says refactoring drastically reduces BK size and leaves the number of literals at only a fraction of the original. Section 4.4 (p. 5) defines program size by its number of literals. The text available in our copy does not establish the claimed reduction of 50% or more; Figure 6 is present only as an image placeholder. (LLM, conf=0.86)
Experimental — accuracy not yet measuredMetagol learns to solve more tasks when using the refactored BK, especially when BK is large.
“More precisely, Metagol learns to solve more tasks when using the refactored BK, especially when BK is large.”
From Inductive Logic Programming At 30: A New Introduction (2022) · cites this paper as Dumancic et al., 2021
The refactored program is smaller in size and contains fewer redundant clauses.
“The refactored program is smaller in size and contains fewer redundant clauses.”
From Inductive Logic Programming At 30: A New Introduction (2022) · cites this paper as Dumancic et al., 2021
Refactoring improves learning performance in lifelong learning.
“The authors experimentally demonstrate that refactoring improves learning performance in lifelong learning.”
From Inductive Logic Programming At 30: A New Introduction (2022) · cites this paper as Dumancic et al., 2021
If the learnt program contains invented predicates, Knorf revises them and introduces new ones that would lead to a smaller program.
“If the learnt program contains invented predicates, Knorf revises them and introduces new ones that would lead to a smaller program 37 .”
From Inductive Logic Programming At 30: A New Introduction (2022) · cites this paper as Dumancic et al., 2021
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Sterling, L., Shapiro, E., & Garrett, R. (1987) · IEEE Expert · doi:10.1109/mex.1987.4307074 · Cited by 1,101 · see citing works
Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited
Muggleton, S. H., Lin, D., & Tamaddoni-Nezhad, A. (2015) · Machine Learning · doi:10.1007/s10994-014-5471-y · Cited by 184 · see citing works
Logical reduction of metarules
Cropper, A., & Tourret, S. (2020) · Machine Learning · doi:10.1007/s10994-019-05834-x · Cited by 29 · see citing works
Self-citationLearning Relational Representations with Auto-encoding Logic Programs
Dumancic, S., Guns, T., Meert, W., & Blockeel, H. (2019) · Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2019/842 · Cited by 27 · see citing works
Self-citation
Flagged first, then by citations
Research works printed but not linked: 24
- Ad´ e, H.; Malfait, B.; and De Raedt, L. 1994. Ruth: an ilp theory revision system. In Ra´ s, Z. W., and Zemankova, M., eds., Methodologies for Intelligent Systems , 336-345. Berlin, Heidelberg: Springer Berlin Heidelberg.
- Balog, M.; Gaunt, A. L.; Brockschmidt, M.; Nowozin, S.; and Tarlow, D. 2017. Deepcoder: Learning to write programs. In ICLR . OpenReview.net.
- Blumer, A.; Ehrenfeucht, A.; Haussler, D.; and Warmuth, M. K. 1987. Occam's razor. Inform. Proc. Lett. 24:377-380.
- Cropper, A. 2019. Playgol: Learning programs through play. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, (IJCAI-19) , 6074-6080.
- Cropper, A. 2020. Forgetting to learn logic programs. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020 , 3676-3683. AAAI Press.
- De Raedt, L.; Kersting, K.; Kimmig, A.; Revoredo, K.; and Toivonen, H. 2008. Compressing probabilistic prolog programs. Machine learning 70(2):151-168.
- De Raedt, L. 1992. Interactive Theory Revision: An Inductive Logic Programming Approach . GBR: Academic Press Ltd.
- Dechter, E.; Malmaud, J.; Adams, R.; and Tenenbaum, J. 2013. Bootstrap learning via modular concept discovery. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence .
- Ellis, K.; Morales, L.; Sabl´ e-Meyer, M.; Solar-Lezama, A.; and Tenenbaum, J. 2018. Learning libraries of subroutines for neurally-guided bayesian program induction. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montr´ eal, Canada , 7816-7826.
- Hemaspaandra, E., and Schnoor, H. 2011. Minimization for generalized boolean formulas. In Walsh, T., ed., IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 1622, 2011 , 566-571. IJCAI/AAAI.
- In Bessiere, C., ed., Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020 , 2312-2318. ijcai.org.
- Karmiloff-Smith, A. 1992. Beyond modularity . MIT Press.
- Mitchell, T. M. 1997. Machine learning . McGraw Hill series in computer science. McGraw-Hill.
- Muggleton, S., and De Raedt, L. 1994. Inductive logic programming: Theory and methods. JOURNAL OF LOGIC PROGRAMMING 19(20):629-679.
- Muggleton, S. 1995. Inverse Entailment and Progol. New Generation Computing, Special issue on Inductive Logic Programming 13(3-4):245-286.
- Plotkin, G. 1971. Automatic Methods of Inductive Inference . Ph.D. Dissertation, Edinburgh University.
- Richards, B. L., and Mooney, R. J. 1995. Automated refinement of first-order horn-clause domain theories. Machine Learning 19(2):95-131.
- Rossi, F.; Beek, P. v.; and Walsh, T. 2006. Handbook of Constraint Programming (Foundations of Artificial Intelligence) . USA: Elsevier Science Inc.
- Saitta, L., and Zucker, J.-D. 2013. Abstraction in artificial intelligence and complex systems . Springer.
- Shapiro, E. 1983. Algorithmic program debugging . MIT Press.
- Sommer, E. 1995. FENDER: an approach to theory restructuring (extended abstract). In Machine Learning: ECML-95, 8th European Conference on Machine Learning, Heraclion, Crete, Greece, April 25-27, 1995, Proceedings , volume 912 of Lecture Notes in Computer Science , 356-359. Springer.
- Srinivasan, A.; Muggleton, S. H.; and King, R. D. 1995. Comparing the use of background knowledge by inductive logic programming systems. In Proceedings of the 5th International Workshop on Inductive Logic Programming , 199230. Department of Computer Science, Katholieke Universiteit Leuven.
- Stahl, I. 1993. Predicate invention in ilp - an overview. In Proceedings of the 6th European Conference on Machine Learning , ECML'93, 311-322.
- Tamaki, H., and Sato, T. 1984. Unfold/fold transformation of logic programs. In T¨ arnlund, S., ed., Proceedings of the Second International Logic Programming Conference, Uppsala University, Uppsala, Sweden, July 2-6, 1984 , 127-138. Uppsala University.
Cited by
Sorted by citations
Inductive Logic Programming At 30: A New Introduction
Cropper, A., & Dumančić, S. (2022) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1.13507 · Cited by 83 · see citing works
“Knorf (Dumancic et al., 2021) pushes the idea of ALPs even further.”
BackgroundInfluentialSelf-citation
- Authors
- Dumancic, S., Guns, T., & Cropper, A.
- Affiliations
- KU Leuven (BE)
- University of Oxford (GB)
- Venue
- Proceedings of the AAAI Conference on Artificial Intelligence
- Published
- 2021-05-18
- Volume
- 35
- Issue
- 8
- Pages
- 7271-7278
- ISSN
- 2159-5399 (ISSN-L)
- 2374-3468
- OpenAlex
- W3109316643
- Cited by
- 2
- References
- 4
- Citations by year
- 2022: 1 · 2021: 1
- FWCI
- 0.23
- Type
- conference paper
- Language
- en
- Open access
- diamond
- doi.org
- Locations
- Proceedings of the AAAI Conference on Artificial Intelligence (publishedVersion)
- Lirias (acceptedVersion, other-oa)
- arXiv (Cornell University) (submittedVersion)
- Lirias (KU Leuven) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Fonds Wetenschappelijk Onderzoek
- Vlaamse regering
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, Reasoning, and Knowledge
- Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
- Physical Sciences › Computer Science › Artificial Intelligence › Evolutionary Algorithms and Applications
- Keywords
- inductive program synthesis, inductive logic programming, knowledge base reduction, constraint optimisation, predicate invention, logic programs, string transformation, learning efficiency
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
