Abstract Scientists form hypotheses and experimentally test them. If a hypothesis fails (is refuted), scientists try toexplainthe 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 thePopperILP 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.

Two fundamental challenges in program synthesis, i.e. learning programs from specifications, are (1) program correctness and (2) search efficiency. We claim logical constraints can address both: (1) by expressing strong requirements on solutions and (2) due to being effective at eliminating non-solutions. When learning from examples, a hypothesis failing on an example means that (a class of) related programs fail as well. We encode these classes into constraints, thereby pruning away many a failing hypothesis. We are expanding this method with failure explanation: identify failing sub-programs the related programs of which can be eliminated as well. In addition to reasoning about examples, programming involves ensuring general properties are not violated. Inspired by the synthesis of functional programs, we intend to encode correctness properties as well as runtime complexity bounds into constraints.

Abstract We describe an inductive logic programming (ILP) approach calledlearning from failures. In this approach, an ILP system (the learner) decomposes the learning problem into three separate stages:generate,test, andconstrain. In the generate stage, the learner generates a hypothesis (a logic program) that satisfies a set ofhypothesis constraints(constraints on the syntactic form of hypotheses). In the test stage, the learner tests the hypothesis against training examples. A hypothesisfailswhen it does not entail all the positive examples or entails a negative example. If a hypothesis fails, then, in the constrain stage, the learner learns constraints from the failed hypothesis to prune the hypothesis space, i.e. to constrain subsequent hypothesis generation. For instance, if a hypothesis is too general (entails a negative example), the constraints prune generalisations of the hypothesis. If a hypothesis is too specific (does not entail all the positive examples), the constraints prune specialisations of the hypothesis. This loop repeats until either (i) the learner finds a hypothesis that entails all the positive and none of the negative examples, or (ii) there are no more hypotheses to test. We introduce Popper, an ILP system that implements this approach by combining answer set programming and Prolog. Popper supports infinite problem domains, reasoning about lists and numbers, learning textually minimal programs, and learning recursive programs. Our experimental results on three domains (toy game problems, robot strategies, and list transformations) show that (i) constraints drastically improve learning performance, and (ii) Popper can outperform existing ILP systems, both in terms of predictive accuracies and learning times.

A key feature of inductive logic programming (ILP) is its ability to learn first-order programs, which are intrinsically more expressive than propositional programs. In this paper, we introduce ILP techniques to learn higher-order programs. We implement our idea in Metagolho, an ILP system which can learn higher-order programs with higher-order predicate invention. Our experiments show that, compared to first-order programs, learning higher-order programs can significantly improve predictive accuracies and reduce learning times.

Abstract 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 higher-order definitions 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 $$\text {Metagol}_{ho}$$ Metagol ho and the ASP system $$\text {HEXMIL}_{ho}$$ HEXMIL ho . 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.