{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T22:39:03Z","timestamp":1776897543117,"version":"3.51.2"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2019,12,3]],"date-time":"2019-12-03T00:00:00Z","timestamp":1575331200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,12,3]],"date-time":"2019-12-03T00:00:00Z","timestamp":1575331200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/N509711\/1"],"award-info":[{"award-number":["EP\/N509711\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2020,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A key feature of inductive logic programming is its ability to learn first-order programs, which are intrinsically more expressive than propositional programs. In this paper, we introduce techniques to learn higher-order programs. Specifically, we extend meta-interpretive learning (MIL) to support learning higher-order programs by allowing for <jats:italic>higher-order definitions<\/jats:italic> to be used as background knowledge. Our theoretical results show that learning higher-order programs, rather than first-order programs, can reduce the textual complexity required to express programs, which in turn reduces the size of the hypothesis space and sample complexity. We implement our idea in two new MIL systems: the Prolog system <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\text {Metagol}_{ho}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mtext>Metagol<\/mml:mtext>\n                    <mml:mrow>\n                      <mml:mi>ho<\/mml:mi>\n                    <\/mml:mrow>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and the ASP system <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\text {HEXMIL}_{ho}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mtext>HEXMIL<\/mml:mtext>\n                    <mml:mrow>\n                      <mml:mi>ho<\/mml:mi>\n                    <\/mml:mrow>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Both systems support learning higher-order programs and higher-order predicate invention, such as inventing functions for  and conditions for . We conduct experiments on four domains (robot strategies, chess playing, list transformations, and string decryption) that compare learning first-order and higher-order programs. Our experimental results support our theoretical claims and show that, compared to learning first-order programs, learning higher-order programs can significantly improve predictive accuracies and reduce learning times.\n<\/jats:p>","DOI":"10.1007\/s10994-019-05862-7","type":"journal-article","created":{"date-parts":[[2019,12,16]],"date-time":"2019-12-16T10:52:50Z","timestamp":1576493570000},"page":"1289-1322","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Learning higher-order logic programs"],"prefix":"10.1007","volume":"109","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4543-7199","authenticated-orcid":false,"given":"Andrew","family":"Cropper","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Morel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen","family":"Muggleton","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,12,3]]},"reference":[{"issue":"1\u20132","key":"5862_CR1","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/S0004-3702(98)00034-4","volume":"101","author":"H Blockeel","year":"1998","unstructured":"Blockeel, H., & De Raedt, L. (1998). Top-down induction of first-order logical decision trees. Artificial Intelligence, 101(1\u20132), 285\u2013297.","journal-title":"Artificial Intelligence"},{"issue":"6","key":"5862_CR2","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.","journal-title":"Information Processing Letters"},{"key":"5862_CR3","first-page":"31","volume":"2","author":"I Bratko","year":"1980","unstructured":"Bratko, I., & Michie, D. (1980). A representation for pattern-knowledge in chess endgames. Advances in Computer Chess, 2, 31\u201356.","journal-title":"Advances in Computer Chess"},{"issue":"4","key":"5862_CR4","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1145\/6041.6042","volume":"17","author":"L Cardelli","year":"1985","unstructured":"Cardelli, L., & Wegner, P. (1985). On understanding types, data abstraction, and polymorphism. ACM Computing Surveys, 17(4), 471\u2013522.","journal-title":"ACM Computing Surveys"},{"key":"5862_CR5","first-page":"311","volume-title":"Readings in nonmonotonic reasoning","author":"KL Clark","year":"1987","unstructured":"Clark, K. L. (1987). Negation as failure. In M. L. Ginsberg (Ed.), Readings in nonmonotonic reasoning (pp. 311\u2013325). Los Altos: Kaufmann."},{"key":"5862_CR6","unstructured":"Cropper, A. (2017). Efficiently learning efficient programs. PhD thesis, Imperial College London, UK."},{"key":"5862_CR7","unstructured":"Cropper, A., & Muggleton, S. H. (2015). Learning efficient logical robot strategies involving composable objects. In Qiang ,Y. & Wooldridge, M. (Eds.), Proceedings of the twenty-fourth international joint conference on artificial intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25\u201331, 2015 (pp. 3423\u20133429). AAAI Press."},{"key":"5862_CR8","unstructured":"Cropper, A., & Muggleton, S. H. (2016). Learning higher-order logic programs through abstraction and invention. In Kambhampati, S. (Ed.), Proceedings of the twenty-fifth international joint conference on artificial intelligence, IJCAI 2016, New York, NY, USA, 9\u201315 July 2016 (pp. 1418\u20131424). IJCAI\/AAAI Press."},{"key":"5862_CR9","unstructured":"Cropper, A., & Muggleton, S.\u00a0H. (2016). Metagol system. https:\/\/github.com\/metagol\/metagol"},{"key":"5862_CR10","unstructured":"Cropper, A., & Muggleton, S. H. (2019). Learning efficient logic programs. Machine Learning, 108(7), 1063\u20131083. https:\/\/doi.org\/10.1007\/s10994-018-5712-6.. Accessed 12 July 2019."},{"key":"5862_CR11","unstructured":"Cropper, A., Tamaddoni-Nezhad, A., Muggleton, S.\u00a0H. (2015). Meta-interpretive learning of data transformation programs. In Inoue, K., Ohwada, H., & Yamamoto, A. (Eds.), Inductive logic programming - 25th international conference, ILP 2015, Kyoto, Japan, August 20\u201322, 2015, Revised selected papers, Lecture notes in computer science (Vol. 9575, pp. 46\u201359). Springer, Berlin."},{"key":"5862_CR12","doi-asserted-by":"crossref","unstructured":"Cropper, A., & Tourret, S. (2018). Derivation reduction of metarules in meta-interpretive learning. In Riguzzi, F., Bellodi, E., & Zese, R. (Eds.), Proceedings of the inductive logic programming - 28th international conference, ILP 2018, Ferrara, Italy, September 2\u20134, 2018, Lecture notes in computer science, (Vol. 11105, pp. 1\u201321). Springer, Berlin.","DOI":"10.1007\/978-3-319-99960-9_1"},{"issue":"4","key":"5862_CR13","first-page":"418","volume":"16","author":"T Eiter","year":"2016","unstructured":"Eiter, T., Fink, M., Ianni, G., Krennwallner, T., Redl, Christoph, & Sch\u00fcller, Peter. (2016). A model building framework for answer set programming with external computations. TPLP, 16(4), 418\u2013464.","journal-title":"TPLP"},{"key":"5862_CR14","unstructured":"Emde, W., Habel, C., & Rollinger, C.-R. (1983). The discovery of the equator or concept driven learning. In Bundy, A. (Ed.), Proceedings of the 8th international joint conference on artificial intelligence. Karlsruhe, FRG, August 1983 (pp. 455\u2013458). William Kaufmann."},{"key":"5862_CR15","unstructured":"Feng, C., & Muggleton, S. (1992). Towards inductive generalization in higher order logic. In Sleeman D.\u00a0H., & Edwards, P. (Eds.), Proceedings of the ninth international workshop on machine learning (ML 1992), Aberdeen, Scotland, UK, July 1\u20133, 1992 (pp. 154\u2013162). Morgan Kaufmann."},{"key":"5862_CR16","doi-asserted-by":"crossref","unstructured":"Feser, J.\u00a0K., Chaudhuri, S., & Dillig, I. (2015). Synthesizing data structure transformations from input-output examples. In Proceedings of the 36th ACM SIGPLAN conference on programming language design and implementation, Portland, OR, USA, June 15\u201317, 2015 (pp. 229\u2013239).","DOI":"10.1145\/2737924.2737977"},{"issue":"2\u20133","key":"5862_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\u20133), 141\u2013195.","journal-title":"The Journal of Logic Programming"},{"key":"5862_CR18","doi-asserted-by":"crossref","unstructured":"Frankle, J., Osera, P.-M., Walker, D., & Zdancewic, S. (2016). Example-directed synthesis: A type-theoretic interpretation. In Bod\u00edk, R., & Majumdar, R. (Eds.), Proceedings of the 43rd annual ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL 2016, St. Petersburg, FL, USA, January 20\u201322, 2016 (pp. 802\u2013815). ACM.","DOI":"10.1145\/2837614.2837629"},{"issue":"3\/4","key":"5862_CR19","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF03037169","volume":"9","author":"M Gelfond","year":"1991","unstructured":"Gelfond, M., & Lifschitz, V. (1991). Classical negation in logic programs and disjunctive databases. New Generation Computing, 9(3\/4), 365\u2013386.","journal-title":"New Generation Computing"},{"key":"5862_CR20","doi-asserted-by":"crossref","unstructured":"Gulwani, S. (2011). Automating string processing in spreadsheets using input-output examples. In Proceedings of the 38th ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL 2011, Austin, TX, USA, January 26-28, 2011 (pp. 317\u2013330).","DOI":"10.1145\/1926385.1926423"},{"key":"5862_CR21","unstructured":"Harris, L. (1988). The heuristic search and the game of chess. A study of quiescence, sacrifices, and plan oriented play. In Computer chess compendium (pp. 136\u2013142). Springer, Berlin."},{"issue":"2","key":"5862_CR22","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s10994-013-5341-z","volume":"91","author":"K Inoue","year":"2013","unstructured":"Inoue, K., Doncescu, A., & Nabeshima, H. (2013). Completing causal networks by meta-level abduction. Machine Learning, 91(2), 239\u2013277.","journal-title":"Machine Learning"},{"issue":"3\u20134","key":"5862_CR23","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(3\u20134), 571\u2013588.","journal-title":"TPLP"},{"key":"5862_CR24","unstructured":"Katayama, S. (2008). Efficient exhaustive generation of functional programs using monte-carlo search with iterative deepening. In  Proceedings of the PRICAI 2008: Trends in artificial intelligence, 10th pacific rim international conference on artificial intelligence, Hanoi, Vietnam, December 15\u201319, 2008 (pp. 199\u2013210)."},{"key":"5862_CR25","unstructured":"Kitzelmann, E. (2008). Data-driven induction of functional programs. In Proceedings of the ECAI 2008 - 18th European conference on artificial intelligence, Patras, Greece, July 21\u201325, 2008 (pp. 781\u2013782)."},{"key":"5862_CR26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-08406-9","volume-title":"Logic for learning","author":"JW Lloyd","year":"2003","unstructured":"Lloyd, J. W. (2003). Logic for learning. Berlin: Springer."},{"issue":"1","key":"5862_CR27","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1145\/357084.357090","volume":"2","author":"Z Manna","year":"1980","unstructured":"Manna, Z., & Waldinger, R. J. (1980). A deductive approach to program synthesis. ACM Transactions on Programming Languages and Systems, 2(1), 90\u2013121.","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"5862_CR28","unstructured":"McCarthy, J. (1995). Making robots conscious of their mental states. In Machine intelligence 15, Intelligent Agents [St. Catherine\u2019s College, Oxford, July 1995] (pp. 3\u201317)."},{"key":"5862_CR29","unstructured":"Mitchell, T.\u00a0M. (1997). Machine learning. McGraw Hill series in computer science. McGraw-Hill."},{"key":"5862_CR30","doi-asserted-by":"crossref","unstructured":"Morel, R., Cropper, A., & Luke Ong, C.-H. (2019). Typed meta-interpretive learning of logic programs. In Calimeri, F., Leone, N., & Manna, M. (Eds.), Proceedings of logics in artificial intelligence - 16th European conference, JELIA 2019, Rende, Italy, May 7\u201311, 2019, Lecture notes in computer science, (Vol. 11468, pp. 198\u2013213). Springer, Berlin.","DOI":"10.1007\/978-3-030-19570-0_13"},{"issue":"3&4","key":"5862_CR31","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&4), 245\u2013286.","journal-title":"New Generation Computing"},{"key":"5862_CR32","doi-asserted-by":"crossref","unstructured":"Muggleton, S., Buntine, W.\u00a0L. (1988). Machine invention of first order predicates by inverting resolution. In Proceedings of the fifth international conference on machine learning, Ann Arbor, Michigan, USA, June 12\u201314, 1988 (pp. 339\u2013352).","DOI":"10.1016\/B978-0-934613-64-4.50040-2"},{"issue":"1","key":"5862_CR33","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10994-011-5259-2","volume":"86","author":"S Muggleton","year":"2012","unstructured":"Muggleton, S., De Raedt, L., Poole, D., Bratko, I., Flach, P. A., Inoue, K., et al. (2012). ILP turns 20 - biography and future challenges. Machine Learning, 86(1), 3\u201323.","journal-title":"Machine Learning"},{"issue":"1","key":"5862_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.","journal-title":"Machine Learning"},{"issue":"1","key":"5862_CR35","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s10994-014-5471-y","volume":"100","author":"SH Muggleton","year":"2015","unstructured":"Muggleton, S. H., Lin, D., & Tamaddoni-Nezhad, A. (2015). Meta-interpretive learning of higher-order dyadic datalog: Predicate invention revisited. Machine Learning, 100(1), 49\u201373.","journal-title":"Machine Learning"},{"key":"5862_CR36","doi-asserted-by":"crossref","unstructured":"Osera, P.-M., & Zdancewic, S. (2015). Type-and-example-directed program synthesis. In Grove, D., & Blackburn, S. (Eds.), Proceedings of the 36th ACM SIGPLAN conference on programming language design and implementation, Portland, OR, USA, June 15\u201317, 2015 (pp. 619\u2013630). ACM.","DOI":"10.1145\/2737924.2738007"},{"key":"5862_CR37","first-page":"239","volume":"5","author":"JR Quinlan","year":"1990","unstructured":"Quinlan, J. R. (1990). Learning logical definitions from relations. Machine Learning, 5, 239\u2013266.","journal-title":"Machine Learning"},{"key":"5862_CR38","first-page":"107","volume":"8","author":"L De Raedt","year":"1992","unstructured":"De Raedt, L., & Bruynooghe, M. (1992). Interactive concept-learning and constructive induction by analogy. Machine Learning, 8, 107\u2013150.","journal-title":"Machine Learning"},{"key":"5862_CR39","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-7052-6","volume-title":"Abstraction in artificial intelligence and complex systems","author":"L Saitta","year":"2013","unstructured":"Saitta, L., & Zucker, J.-D. (2013). Abstraction in artificial intelligence and complex systems. Berlin: Springer."},{"key":"5862_CR40","first-page":"197","volume":"5","author":"RE Schapire","year":"1990","unstructured":"Schapire, R. E. (1990). The strength of weak learnability. Machine Learning, 5, 197\u2013227.","journal-title":"Machine Learning"},{"key":"5862_CR41","unstructured":"Srinivasan, A. (2001). The ALEPH manual. Machine Learning at the Computing Laboratory: Oxford University."},{"issue":"1\u20132","key":"5862_CR42","first-page":"95","volume":"20","author":"I Stahl","year":"1995","unstructured":"Stahl, I. (1995). The appropriateness of predicate invention as bias shift operation in ILP. Machine Learning, 20(1\u20132), 95\u2013117.","journal-title":"Machine Learning"},{"issue":"1\u20132","key":"5862_CR43","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1017\/S1471068411000494","volume":"12","author":"J Wielemaker","year":"2012","unstructured":"Wielemaker, J., Schrijvers, T., Triska, M., & Lager, T. (2012). SWI-Prolog. Theory and Practice of Logic Programming, 12(1\u20132), 67\u201396.","journal-title":"Theory and Practice of Logic Programming"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-019-05862-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10994-019-05862-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-019-05862-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,1]],"date-time":"2020-12-01T19:23:10Z","timestamp":1606850590000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10994-019-05862-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,3]]},"references-count":43,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["5862"],"URL":"https:\/\/doi.org\/10.1007\/s10994-019-05862-7","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,3]]},"assertion":[{"value":"14 February 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 July 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 November 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 December 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}