{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T04:22:58Z","timestamp":1783138978219,"version":"3.54.6"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,2,8]],"date-time":"2021-02-08T00:00:00Z","timestamp":1612742400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,2,8]],"date-time":"2021-02-08T00:00:00Z","timestamp":1612742400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2021,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Meta-Interpretive Learners, like most ILP systems, learn by searching for a correct hypothesis in the hypothesis space, the powerset of all constructible clauses. We show how this exponentially-growing search can be replaced by the construction of a Top program: the set of clauses in all correct hypotheses that is itself a correct hypothesis. We give an algorithm for Top program construction and show that it constructs a correct Top program in polynomial time and from a finite number of examples. We implement our algorithm in Prolog as the basis of a new MIL system, Louise, that constructs a Top program and then reduces it by removing redundant clauses. We compare Louise to the state-of-the-art search-based MIL system Metagol in experiments on grid world navigation, graph connectedness and grammar learning datasets and find that Louise improves on Metagol\u2019s predictive accuracy when the hypothesis space and the target theory are both large, or when the hypothesis space does not include a correct hypothesis because of \u201cclassification noise\u201d in the form of mislabelled examples. When the hypothesis space or the target theory are small, Louise and Metagol perform equally well.<\/jats:p>","DOI":"10.1007\/s10994-020-05945-w","type":"journal-article","created":{"date-parts":[[2021,2,9]],"date-time":"2021-02-09T23:02:18Z","timestamp":1612911738000},"page":"755-778","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Top program construction and reduction for polynomial time Meta-Interpretive learning"],"prefix":"10.1007","volume":"110","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2266-4663","authenticated-orcid":false,"given":"S.","family":"Patsantzis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S. H.","family":"Muggleton","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,2,8]]},"reference":[{"key":"5945_CR1","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/3-540-57868-4_49","volume-title":"Machine Learning: ECML-94","author":"DW Aha","year":"1994","unstructured":"Aha, D. W., Lapointe, S., Ling, C. X., & Matwin, S. (1994). Inverting implication with small training sets. In F. Bergadano & L. De Raedt (Eds.), Machine Learning: ECML-94 (pp. 29\u201348). Berlin, Heidelberg: Springer."},{"key":"5945_CR2","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/978-3-662-44923-3_3","volume-title":"Inductive logic programming","author":"D Athakravi","year":"2014","unstructured":"Athakravi, D., Corapi, D., Broda, K., & Russo, A. (2014). Learning through hypothesis refinement using answer set programming. In G. Zaverucha, V. Santos Costa, & A. Paes (Eds.), Inductive logic programming (pp. 31\u201346). Berlin, Heidelberg: Springer."},{"issue":"6","key":"5945_CR3","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1016\/0020-0190(87)90114-1","volume":"24","author":"A Blumer","year":"1987","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1987). Occam\u2019s razor. Information Processing Letters, 24(6), 377\u2013380. https:\/\/doi.org\/10.1016\/0020-0190(87)90114-1.","journal-title":"Information Processing Letters"},{"issue":"1","key":"5945_CR4","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1109\/69.43410","volume":"1","author":"S Ceri","year":"1989","unstructured":"Ceri, S., Gottlob, G., & Tanca, L. (1989). What you always wanted to know about datalog (and never dared to ask). IEEE Transactions on Knowledge and Data Engineering, 1(1), 146\u2013166.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"5945_CR5","doi-asserted-by":"publisher","unstructured":"Corapi, D., Russo, A., Lupu, E. (2010). Inductive logic programming as abductive search. In Hermenegildo MV, Schaub T (eds) Technical Communications of the 26th International Conference on Logic Programming, ICLP 2010, July 16-19, 2010, Edinburgh, Scotland, UK, Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, LIPIcs, vol.\u00a07, pp. 54\u201363, https:\/\/doi.org\/10.4230\/LIPIcs.ICLP.2010.54","DOI":"10.4230\/LIPIcs.ICLP.2010.54"},{"key":"5945_CR6","doi-asserted-by":"publisher","unstructured":"Corapi, D., Russo, A., Lupu, E. (2011). Inductive logic programming in answer set programming. In Muggleton S, Tamaddoni-Nezhad A, Lisi FA (eds) Inductive Logic Programming\u201421st International Conference, ILP 2011, Windsor Great Park, UK, July 31\u2013August 3, 2011, Revised Selected Papers, Springer, Lecture Notes in Computer Science, vol. 7207, pp. 91\u201397, https:\/\/doi.org\/10.1007\/978-3-642-31951-8_12","DOI":"10.1007\/978-3-642-31951-8_12"},{"key":"5945_CR7","unstructured":"Cropper, A., Muggleton, S. (2016). Learning higher-order logic programs through abstraction and invention. In Proceedings of the 25th International Joint Conference Artificial Intelligence (IJCAI 2016), IJCAI, pp. 1418\u20131424, http:\/\/www.doc.ic.ac.uk\/~shm\/Papers\/metafunc.pdf"},{"key":"5945_CR8","doi-asserted-by":"crossref","unstructured":"Cropper, A., Muggleton, S.H. (2015). Logical minimisation of meta-rules within Meta-Interpretive Learning. In Proceedings of the 24th International Conference on Inductive Logic Programming, pp 65\u201378","DOI":"10.1007\/978-3-319-23708-4_5"},{"key":"5945_CR9","first-page":"1","volume-title":"Inductive Logic Programming","author":"A Cropper","year":"2018","unstructured":"Cropper, A., & Tourret, S. (2018). Derivation reduction of metarules in meta-interpretive learning. In F. Riguzzi, E. Bellodi, & R. Zese (Eds.), Inductive Logic Programming (pp. 1\u201321). Cham: Springer."},{"key":"5945_CR10","first-page":"46","volume-title":"Inductive Logic Programming","author":"A Cropper","year":"2016","unstructured":"Cropper, A., Tamaddoni-Nezhad, A., & Muggleton, S. H. (2016). Meta-interpretive learning of data transformation programs. In K. Inoue, H. Ohwada, & A. Yamamoto (Eds.), Inductive Logic Programming (pp. 46\u201359). Cham: Springer."},{"key":"5945_CR11","doi-asserted-by":"publisher","unstructured":"Dumancic, S., Guns, T., Meert, W., Blockeel, H. (2019). Learning relational representations with auto-encoding logic programs. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, International Joint Conferences on Artificial Intelligence Organization, pp. 6081\u20136087, https:\/\/doi.org\/10.24963\/ijcai.2019\/842","DOI":"10.24963\/ijcai.2019\/842"},{"key":"5945_CR12","unstructured":"Emde, W. (1987). Non-cumulative learning in metaxa.3. In Proceedings of IJCAI-87, Morgan Kaufmann, pp. 208\u2013210."},{"key":"5945_CR13","unstructured":"Emde, W., Habel, C.U., rainer Rollinger, C., Berlin, T.U., Kit, P., Fr, S. (1983). The discovery of the equator or concept driven learning. In Proceedings of the 8th International Joint Conference on Artificial Intelligence, Morgan Kaufmann, pp. 455\u2013458."},{"key":"5945_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1613\/jair.5714","volume":"61","author":"R Evans","year":"2018","unstructured":"Evans, R., & Grefenstette, E. (2018). Learning explanatory rules from noisy data. Journal of Artificial Intelligence Research, 61, 1\u201364. https:\/\/doi.org\/10.1613\/jair.5714.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"5945_CR15","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/3-540-63494-0_55","volume-title":"Inductive Logic Programming","author":"P Flener","year":"1997","unstructured":"Flener, P. (1997). Inductive logic program synthesis with dialogs. In S. Muggleton (Ed.), Inductive Logic Programming (pp. 175\u2013198). Berlin Heidelberg: Springer."},{"issue":"5","key":"5945_CR16","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1016\/S0747-7171(06)80012-X","volume":"15","author":"P Flener","year":"1993","unstructured":"Flener, P., & Deville, Y. (1993). Logic program synthesis from incomplete specifications. Journal of Symbolic Computation, 15(5), 775\u2013805.","journal-title":"Journal of Symbolic Computation"},{"issue":"2","key":"5945_CR17","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/S0743-1066(99)00028-X","volume":"41","author":"P Flener","year":"1999","unstructured":"Flener, P., & Yilmaz, S. (1999). Inductive synthesis of recursive logic programs: achievements and prospects. The Journal of Logic Programming, 41(2), 141\u2013195. https:\/\/doi.org\/10.1016\/S0743-1066(99)00028-X.","journal-title":"The Journal of Logic Programming"},{"key":"5945_CR18","unstructured":"Hamfelt, A., Nilsson, J.F. (1994). Inductive metalogic programming. In: Wrobel S (ed) Proceedings of ILP\u201994, GMD-Studien Nr. 237, Sankt Augustin, Germany, pp. 85\u201396"},{"key":"5945_CR19","first-page":"192","volume-title":"Advances in Inductive Logic Programming","author":"P Idestam-Almquist","year":"1996","unstructured":"Idestam-Almquist, P. (1996). Efficient induction of recursive definitions by structural analysis of saturations. In L. DeRaedt (Ed.), Advances in Inductive Logic Programming (pp. 192\u2013205). Amsterdam: IOS Press."},{"key":"5945_CR20","first-page":"571","volume":"18","author":"T Kaminski","year":"2018","unstructured":"Kaminski, T., Eiter, T., & Inoue, K. (2018). Exploiting answer set programming with external sources for meta-interpretive learning. TPLP, 18, 571\u2013588.","journal-title":"TPLP"},{"key":"5945_CR21","unstructured":"Kietz, J. U., & Wrobel, S. (1992). Controlling the complexity of learning in logic through syntactic and task-oriented models. In S. Muggleton (Ed.), Inductive logic programming (pp. 335\u2013359). Academic Press."},{"key":"5945_CR22","unstructured":"Lapointe, S., Ling, C., Matwin, S. (1993). Constructive inductive logic programming. In Muggleton S (ed) Proceedings of ILP\u201993, J. Stefan Institute Ljubljana, Slovenia, pp. 255\u2013264."},{"key":"5945_CR23","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/978-3-319-11558-0_22","volume-title":"Logics in Artificial Intelligence","author":"M Law","year":"2014","unstructured":"Law, M., Russo, A., & Broda, K. (2014). Inductive learning of answer set programs. In E. Ferm\u00e9 & J. Leite (Eds.), Logics in Artificial Intelligence (pp. 311\u2013325). Cham: Springer."},{"key":"5945_CR24","doi-asserted-by":"publisher","unstructured":"Lin, D., Dechter, E., Ellis, K., Tenenbaum, J., Muggleton, S., Dwight, M. (2014). Bias reformulation for one-shot function induction. In Proceedings of the 23rd European Conference on Artificial Intelligence, pp. 525\u2013530, https:\/\/doi.org\/10.3233\/978-1-61499-419-0-525","DOI":"10.3233\/978-1-61499-419-0-525"},{"key":"5945_CR25","doi-asserted-by":"publisher","unstructured":"Marcinkowski, J., Pacholski, L. (1992). Undecidability of the horn-clause implication problem. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, IEEE Computer Society, USA, SFCS \u201992, pp. 354\u2013362, https:\/\/doi.org\/10.1109\/SFCS.1992.267755.","DOI":"10.1109\/SFCS.1992.267755"},{"key":"5945_CR26","doi-asserted-by":"crossref","unstructured":"Morel, R., Cropper, A., Luke, O.C.H.(2019). Typed meta-interpretive learning of logic programs. In Proceedings of the European Conference on Logics in Artificial Intelligence (JELIA), to appear.","DOI":"10.1007\/978-3-030-19570-0_13"},{"key":"5945_CR27","doi-asserted-by":"publisher","unstructured":"Morik, K. (1993). Balanced Cooperative Modeling, Springer US, Boston, MA, pp 109\u2013127. https:\/\/doi.org\/10.1007\/978-1-4615-3202-6_6.","DOI":"10.1007\/978-1-4615-3202-6_6"},{"issue":"4","key":"5945_CR28","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF03037089","volume":"8","author":"S Muggleton","year":"1991","unstructured":"Muggleton, S. (1991). Inductive logic programming. New Generation Computing, 8(4), 295\u2013318. https:\/\/doi.org\/10.1007\/BF03037089.","journal-title":"New Generation Computing"},{"issue":"3","key":"5945_CR29","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/BF03037227","volume":"13","author":"S Muggleton","year":"1995","unstructured":"Muggleton, S. (1995). Inverse entailment and progol. New Generation Computing, 13(3), 245\u2013286. https:\/\/doi.org\/10.1007\/BF03037227.","journal-title":"New Generation Computing"},{"issue":"1","key":"5945_CR30","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s10994-014-5471-y","volume":"100","author":"S Muggleton","year":"2015","unstructured":"Muggleton, S., & Lin, D. (2015). Meta-Interpretive Learning of Higher-Order Dyadic Datalog : Predicate Invention Revisited. Machine Learning, 100(1), 49\u201373.","journal-title":"Machine Learning"},{"issue":"7","key":"5945_CR31","doi-asserted-by":"publisher","first-page":"1097","DOI":"10.1007\/s10994-018-5710-8","volume":"107","author":"S Muggleton","year":"2018","unstructured":"Muggleton, S., Dai, W. Z., Sammut, C., Tamaddoni-Nezhad, A., Wen, J., & Zhou, Z. H. (2018). Meta-interpretive learning from noisy images. Machine Learning, 107(7), 1097\u20131118. https:\/\/doi.org\/10.1007\/s10994-018-5710-8.","journal-title":"Machine Learning"},{"key":"5945_CR32","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1007\/978-3-540-89982-2_58","volume-title":"Logic Programming","author":"SH Muggleton","year":"2008","unstructured":"Muggleton, S. H., Santos, J. C. A., & Tamaddoni-Nezhad, A. (2008). Toplog: Ilp using a logic program declarative bias. In M. Garcia de la Banda & E. Pontelli (Eds.), Logic Programming (pp. 687\u2013692). Berlin Heidelberg: Springer."},{"key":"5945_CR33","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/978-3-642-31951-8_22","volume-title":"Inductive Logic Programming","author":"SH Muggleton","year":"2012","unstructured":"Muggleton, S. H., Lin, D., & Tamaddoni-Nezhad, A. (2012). Mc-toplog: Complete multi-clause learning guided by a top theory. In S. H. Muggleton, A. Tamaddoni-Nezhad, & F. A. Lisi (Eds.), Inductive Logic Programming (pp. 238\u2013254). Berlin Heidelberg: Springer."},{"issue":"1","key":"5945_CR34","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s10994-013-5358-3","volume":"94","author":"SH Muggleton","year":"2014","unstructured":"Muggleton, S. H., Lin, D., Pahlavi, N., & Tamaddoni-Nezhad, A. (2014). Meta-interpretive learning: Application to grammatical inference. Machine Learning, 94(1), 25\u201349. https:\/\/doi.org\/10.1007\/s10994-013-5358-3.","journal-title":"Machine Learning"},{"key":"5945_CR35","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-62927-0","volume-title":"Foundations of Inductive Logic programming","author":"SH Nienhuys-Cheng","year":"1997","unstructured":"Nienhuys-Cheng, S. H., & de Wolf, R. (1997). Foundations of Inductive Logic programming. Berlin: Springer."},{"key":"5945_CR36","unstructured":"Patsantzis, S., Muggleton, S.H. (2019). Louise system. https:\/\/github.com\/stassa\/louise, https:\/\/github.com\/stassa\/louise"},{"key":"5945_CR37","unstructured":"Plotkin, G. D. (1971). A further note on inductive generalization. In B. Meltzer & D. Michie (Eds.), Machine intelligence (Vol.\u00a06, pp. 101\u2013124). Edinburgh University Press."},{"key":"5945_CR38","unstructured":"Plotkin, G. (1972). Automatic Methods of Inductive Inference. Ph.D thesis, The University of Edinburgh."},{"key":"5945_CR39","unstructured":"Plotkin, G. D. (1970). A note on inductive generalization. In B. Meltzer & D. Michie (Eds.), Machine intelligence (Vol. 5, pp. 153\u2013163). Edinburgh University Press."},{"key":"5945_CR40","unstructured":"Scott, R(Director, Khouri C(Writer)., Sarandon, S., Davis, G., Keitel, H(Starring). (1991). Thelma & Louise. Metro-Goldwyn-Mayer."},{"key":"5945_CR41","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/3-540-56602-3_144","volume-title":"Machine Learning: ECML-93","author":"I Stahl","year":"1993","unstructured":"Stahl, I. (1993). Predicate invention in ilp \u2013 an overview. In P. B. Brazdil (Ed.), Machine Learning: ECML-93 (pp. 311\u2013322). Berlin Heidelberg: Springer."},{"issue":"11","key":"5945_CR42","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"LG Valiant","year":"1984","unstructured":"Valiant, L. G. (1984). A theory of the learnable. Communication ACM, 27(11), 1134\u20131142. https:\/\/doi.org\/10.1145\/1968.1972.","journal-title":"Communication ACM"},{"key":"5945_CR43","first-page":"299","volume":"38","author":"R Wirth","year":"1992","unstructured":"Wirth, R., & O\u2019Rorke, P. (1992). Constraints for predicate invention. Inductive Logic Programming APIC, 38, 299\u2013318.","journal-title":"Inductive Logic Programming APIC"},{"key":"5945_CR44","unstructured":"Wizards of the Coast LLC (2018) Magic: The gathering comprehensive rules. https:\/\/media.wizards.com\/2018\/downloads\/MagicCompRules%2020180810.txt, https:\/\/media.wizards.com\/2018\/downloads\/MagicCompRules%2020180810.txt"},{"issue":"4","key":"5945_CR45","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1016\/S0020-7373(88)80006-3","volume":"29","author":"S Wrobel","year":"1988","unstructured":"Wrobel, S. (1988). Design goals for sloppy modeling systems. International Journal of Man-Machine Studies, 29(4), 461\u2013477. https:\/\/doi.org\/10.1016\/S0020-7373(88)80006-3.","journal-title":"International Journal of Man-Machine Studies"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-020-05945-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-020-05945-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-020-05945-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T21:46:35Z","timestamp":1697838395000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-020-05945-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,8]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["5945"],"URL":"https:\/\/doi.org\/10.1007\/s10994-020-05945-w","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,8]]},"assertion":[{"value":"15 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 February 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}