{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T21:44:32Z","timestamp":1748641472538,"version":"3.37.3"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2023,8,7]],"date-time":"2023-08-07T00:00:00Z","timestamp":1691366400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,8,7]],"date-time":"2023-08-07T00:00:00Z","timestamp":1691366400000},"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\/V040340\/1"],"award-info":[{"award-number":["EP\/V040340\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"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":[[2023,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Scientists form hypotheses and experimentally test them. If a hypothesis fails (is refuted), scientists try to<jats:italic>explain<\/jats:italic>the failure to eliminate other hypotheses. The more precise the failure analysis the more hypotheses can be eliminated. Thus inspired, we introduce failure explanation techniques for inductive logic programming. Given a hypothesis represented as a logic program, we test it on examples. If a hypothesis fails, we explain the failure in terms of failing sub-programs. In case a positive example fails, we identify failing sub-programs at the granularity of literals. We introduce a failure explanation algorithm based on analysing branches of SLD-trees. We integrate a meta-interpreter based implementation of this algorithm with the test-stage of the<jats:sc>Popper<\/jats:sc>ILP system. We show that fine-grained failure analysis allows for learning fine-grained constraints on the hypothesis space. Our experimental results show that explaining failures can drastically reduce hypothesis space exploration and learning times.<\/jats:p>","DOI":"10.1007\/s10994-023-06358-1","type":"journal-article","created":{"date-parts":[[2023,8,7]],"date-time":"2023-08-07T21:01:29Z","timestamp":1691442089000},"page":"3917-3943","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Learning logic programs by explaining their failures"],"prefix":"10.1007","volume":"112","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6063-6965","authenticated-orcid":false,"given":"Rolf","family":"Morel","sequence":"first","affiliation":[]},{"given":"Andrew","family":"Cropper","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,8,7]]},"reference":[{"key":"6358_CR1","unstructured":"Ahlgren, J., & Yuen, S.Y. (2013). Efficient program synthesis using constraint satisfaction in inductive logic programming. JMLR."},{"key":"6358_CR2","doi-asserted-by":"crossref","unstructured":"Blockeel, H., & De Raedt, L. (1998). Top-down induction of first-order logical decision trees. AIJ.","DOI":"10.1016\/S0004-3702(98)00034-4"},{"key":"6358_CR3","unstructured":"Bundy, A., & Mitrovic, B. (2016). Reformation: A domain-independent algorithm for theory repair. Technical report, University of Edinburgh."},{"key":"6358_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3106740","volume":"50","author":"R Caballero","year":"2017","unstructured":"Caballero, R., Riesco, A., & Silva, J. (2017). A survey of algorithmic debugging. ACM Computing Surveys, 50, 1\u201335.","journal-title":"ACM Computing Surveys"},{"key":"6358_CR5","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1561\/1900000006","volume":"1","author":"J Cheney","year":"2009","unstructured":"Cheney, J., Chiticariu, L., & Tan, W. C. (2009). Provenance in databases: Why, how, and where. Found. Trends Databases, 1, 379\u2013474.","journal-title":"Found. Trends Databases"},{"key":"6358_CR6","doi-asserted-by":"crossref","unstructured":"Cropper, A. (2019). Playgol: Learning programs through play. IJCAI.","DOI":"10.24963\/ijcai.2019\/841"},{"key":"6358_CR7","doi-asserted-by":"crossref","unstructured":"Cropper, A. (2022). Learning logic programs through divide, constrain, and conquer. In AAAI.","DOI":"10.1609\/aaai.v36i6.20596"},{"key":"6358_CR8","doi-asserted-by":"publisher","first-page":"1393","DOI":"10.1007\/s10994-019-05843-w","volume":"109","author":"A Cropper","year":"2020","unstructured":"Cropper, A., Evans, R., & Law, M. (2020). Inductive general game playing. Machine Learning, 109, 1393\u20131434.","journal-title":"Machine Learning"},{"key":"6358_CR9","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1007\/s10994-020-05934-z","volume":"110","author":"A Cropper","year":"2021","unstructured":"Cropper, A., & Morel, R. (2021). Learning programs by learning from failures. Machine Learning, 110, 801\u2013856.","journal-title":"Machine Learning"},{"key":"6358_CR10","unstructured":"Cropper, A., & Morel, R. (2021). Predicate invention by learning from failures. CoRR. arxiv: abs\/2104.14426."},{"key":"6358_CR11","unstructured":"Cropper, A., & Muggleton, S.H. (2016). Metagol system. https:\/\/github.com\/metagol\/metagol."},{"key":"6358_CR12","unstructured":"Ellis, K., Morales, L., Sabl\u00e9-Meyer, M., Solar-Lezama, A., & Tenenbaum, J. (2018). Learning libraries of subroutines for neurally\u2013guided Bayesian program induction. In NeurIPS."},{"key":"6358_CR13","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.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"6358_CR14","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2020.103438","volume":"293","author":"R Evans","year":"2021","unstructured":"Evans, R., Hern\u00e1ndez-Orallo, J., Welbl, J., Kohli, P., & Sergot, M. (2021). Making sense of sensory input. Artificial Intelligence, 293, 103438.","journal-title":"Artificial Intelligence"},{"issue":"2","key":"6358_CR15","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1017\/S1471068418000534","volume":"19","author":"Jorge Fandinno","year":"2019","unstructured":"Fandinno, Jorge, & Schulz, Claudia. (2019). Answering the \u201cwhy\u2019\u2019 in answer set programming\u2013A survey of explanation approaches. Theory and Practice of Logic Programmin, 19(2), 114\u2013203.","journal-title":"Theory and Practice of Logic Programmin"},{"key":"6358_CR16","doi-asserted-by":"crossref","unstructured":"Feng, Y., Martins, R., Bastani, O., & Dillig, I. (2018). Program synthesis using conflict-driven learning. In PLDI.","DOI":"10.1145\/3192366.3192382"},{"key":"6358_CR17","unstructured":"Gebser, M., Kaminski, R., Kaufmann, B., & Schaub, T. (2014). Clingo = ASP + control: Preliminary report. CoRR, arxiv: abs\/1405.3694."},{"key":"6358_CR18","doi-asserted-by":"crossref","unstructured":"Genesereth, Michael\u00a0R., & Thielscher, Michael: General Game Playing. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, (2014).","DOI":"10.1007\/978-3-031-01569-4"},{"key":"6358_CR19","doi-asserted-by":"crossref","unstructured":"Hocquette, C., & Muggleton, S.H. (2020). Complete bottom-up predicate invention in meta-interpretive learning. In IJCAI.","DOI":"10.24963\/ijcai.2020\/320"},{"key":"6358_CR20","doi-asserted-by":"crossref","unstructured":"Kaminski, T., Eiter, T., & Inoue, K. (2019). Meta-interpretive learning using hex-programs. In IJCAI.","DOI":"10.24963\/ijcai.2019\/860"},{"key":"6358_CR21","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/2930.001.0001","volume-title":"Explanation and cognition","author":"FC Keil","year":"2000","unstructured":"Keil, F. C., & Wilson, R. A. (2000). Explanation and cognition. MIT press."},{"key":"6358_CR22","doi-asserted-by":"crossref","unstructured":"K\u00f6hler, S., Lud\u00e4scher, B., & Smaragdakis, Y. (2012) Declarative datalog debugging for mere mortals. In Datalog in academia and industry.","DOI":"10.1007\/978-3-642-32925-8_12"},{"key":"6358_CR23","first-page":"38","volume":"63","author":"J Larson","year":"1977","unstructured":"Larson, J., & Michalski, R. S. (1977). Inductive inference of VL decision rules. SIGART Newsletter, 63, 38\u201344.","journal-title":"SIGART Newsletter"},{"key":"6358_CR24","unstructured":"Law, M. (2018). Inductive learning of answer set programs. PhD thesis, Imperial College London, UK."},{"key":"6358_CR25","doi-asserted-by":"crossref","unstructured":"Law, M., Russo, A., Bertino, E., Broda, K., & Lobo, J. (2020). Fastlas: Scalable inductive logic programming incorporating domain-specific optimisation criteria. In AAAI.","DOI":"10.1609\/aaai.v34i03.5678"},{"key":"6358_CR26","unstructured":"Lin, D., Dechter, E., Ellis, K., Tenenbaum, J.B., & Muggleton, S. (2014). Bias reformulation for one-shot function induction. In ECAI."},{"key":"6358_CR27","volume-title":"Foundations of logic programming","author":"JW Lloyd","year":"2012","unstructured":"Lloyd, J. W. (2012). Foundations of logic programming. Springer Science & Business Media."},{"key":"6358_CR28","doi-asserted-by":"crossref","unstructured":"Midelfart, H. (1999). A bounded search space of clausal theories. In ILP.","DOI":"10.1007\/3-540-48751-4_20"},{"key":"6358_CR29","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, 295\u2013318.","journal-title":"New Generation Computing"},{"key":"6358_CR30","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, 245\u2013286.","journal-title":"New Generation Computing"},{"key":"6358_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-62927-0","volume-title":"Foundations of Inductive Logic Programming","author":"Shan-Hwei Nienhuys-Cheng","year":"1997","unstructured":"Nienhuys-Cheng, Shan-Hwei., & de Wolf, Ronald. (1997). Foundations of Inductive Logic Programming. Springer-Verlag."},{"issue":"2","key":"6358_CR32","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/1042-8143(91)90003-6","volume":"3","author":"Michael J Pazzani","year":"1991","unstructured":"Pazzani, Michael J., & Brunk, Clifford A. (1991). Detecting and correcting errors in rule-based expert systems: An integration of empirical and explanation-based learning. Knowledge Acquisition, 3(2), 157\u2013173.","journal-title":"Knowledge Acquisition"},{"key":"6358_CR33","unstructured":"Plotkin, G.D. (1971). Automatic methods of inductive inference. PhD thesis, Edinburgh University, August."},{"key":"6358_CR34","volume-title":"Conjectures and refutations: The growth of scientific knowledge","author":"KR Popper","year":"1963","unstructured":"Popper, K. R. (1963). Conjectures and refutations: The growth of scientific knowledge. Routledge."},{"key":"6358_CR35","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/BF00992861","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":"6358_CR36","unstructured":"Raghothaman, M., Mendelson, J., Zhao, D., Naik, M., & Scholz, B. (20202) Provenance-guided synthesis of datalog programs. PACMPL."},{"issue":"2","key":"6358_CR37","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BF01007461","volume":"19","author":"Bradley L Richards","year":"1995","unstructured":"Richards, Bradley L., & Mooney, Raymond J. (1995). Automated refinement of first-order horn-clause domain theories. Machine Learning, 19(2), 95\u2013131.","journal-title":"Machine Learning"},{"key":"6358_CR38","doi-asserted-by":"publisher","first-page":"1141","DOI":"10.1007\/s10994-018-5708-2","volume":"107","author":"P Sch\u00fcller","year":"2018","unstructured":"Sch\u00fcller, P., & Benz, M. (2018). Best-effort inductive logic programming via fine-grained cost-based hypothesis generation. Machine Learning, 107, 1141\u20131169.","journal-title":"Machine Learning"},{"key":"6358_CR39","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/1192.001.0001","volume-title":"Algorithmic program DeBugging","author":"EY Shapiro","year":"1983","unstructured":"Shapiro, E. Y. (1983). Algorithmic program DeBugging. MIT Press."},{"key":"6358_CR40","unstructured":"Marques Silva, J.P., Lynce, I., & Malik, S. (2009). Conflict-driven clause learning SAT solvers. In Handbook of satisfiability."},{"key":"6358_CR41","unstructured":"Silver, T., Allen, K.R., & Lew, A.K., Kaelbling, L.P. & Tenenbaum, J. (20202). Few-shot Bayesian imitation learning with logical program policies. In AAAI."},{"key":"6358_CR42","unstructured":"Srinivasan, A. (2001). The ALEPH manual."},{"key":"6358_CR43","doi-asserted-by":"crossref","unstructured":"Thompson, G., & Sullivan, A.K. (2020). Profl: a fault localization framework for prolog. In ISSTA.","DOI":"10.1145\/3395363.3404367"},{"key":"6358_CR44","first-page":"14","volume":"32","author":"S Wrobel","year":"1996","unstructured":"Wrobel, S. (1996). First order theory refinement. Advances in inductive logic programming, 32, 14\u201333.","journal-title":"Advances in inductive logic programming"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-023-06358-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-023-06358-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-023-06358-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T20:58:49Z","timestamp":1729889929000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-023-06358-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,7]]},"references-count":44,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["6358"],"URL":"https:\/\/doi.org\/10.1007\/s10994-023-06358-1","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"type":"print","value":"0885-6125"},{"type":"electronic","value":"1573-0565"}],"subject":[],"published":{"date-parts":[[2023,8,7]]},"assertion":[{"value":"7 February 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 May 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 June 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 August 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}