PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning programs by learning from failures

Andrew Cropper, Rolf Morel

arXiv:2005.02259v3cs.AIcs.LG

TL;DR

Searching ILP hypothesis spaces efficiently is difficult, with set-covering and ASP approaches facing different challenges. The paper presents learning from failures, implemented in Popper, and reports reduced search spaces and strong performance across three domains.

  • Problem

    ILP must efficiently search large hypothesis spaces, while set-covering systems can learn overly specific solutions and struggle with recursion and ASP-based systems can struggle with scalability.

    Source: §1 · p. 2

  • Method

    Learning from failures has Popper generate hypotheses, test them against examples, and learn constraints from failures to prune later hypothesis generation.

    Source: §4 · p. 20, §6 · p. 45

  • Results

    Across toy game problems, robot strategies, and list transformations, constraints drastically reduce the hypothesis space and Popper substantially outperforms existing ILP systems in predictive accuracy and learning time.

    Source: §6 · p. 46

  • Takeaways & Limitations

    Learned constraints let Popper prune large parts of the hypothesis space by testing a single hypothesis.

    Source: §1 · p. 4

    Popper does not currently support predicate invention.

    Source: §6.1.1 · p. 46

Abstract

from arXiv · show

We describe an inductive logic programming (ILP) approach called learning from failures. In this approach, an ILP system (the learner) decomposes the learning problem into three separate stages: generate, test, and constrain. In the generate stage, the learner generates a hypothesis (a logic program) that satisfies a set of hypothesis constraints (constraints on the syntactic form of hypotheses). In the test stage, the learner tests the hypothesis against training examples. A hypothesis fails when 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.

1 Introduction

Learning from failures (LFF) searches for a logic program by generating and testing hypotheses, then using failures to constrain later search. Popper implements this approach, and experiments report reduced hypothesis spaces and better predictive accuracy and learning times than existing ILP systems.

1 Introduction

  • Set-cover ILP systems are often efficient but tend to learn overly specific solutions and struggle with recursion, while ASP-based systems can struggle with scalability as domains grow.ASP-based systems can often learn optimal and recursive programs.Source: §1 · p. 2
  • LFF generates hypotheses, tests them against training examples, and learns constraints from failures to prune subsequent hypothesis generation.A hypothesis fails if it misses a positive example or entails a negative example.Source: §1 · p. 2
  • Theta-subsumption translates failed hypotheses into constraints that prune generalisations or specialisations, rather than refining clauses or hypotheses directly.Too-general hypotheses prune generalisations; too-specific hypotheses prune specialisations, and the loop ends at a solution or when no hypotheses remain.Source: §1 · pp. 2, 4
  • Popper combines ASP for declarative hypothesis generation and constraints with Prolog testing, supporting lists, numbers, and large domains.ASP constraints can also enforce type restrictions and prune failed-hypothesis generalisations or specialisations.Source: §1 · p. 4
  • The paper defines the LFF hypothesis space and proves theta-subsumption-based generalisation and specialisation constraints sound with respect to optimal solutions.The contribution list also introduces Popper and its support for types, textually minimal and recursive programs, lists, and infinite domains.Source: §1 · pp. 5–6
  • Popper substantially outperforms existing ILP systems in predictive accuracy and learning time across toy game problems, robot strategies, and list transformations.The experiments also report that constraints drastically reduce the hypothesis space and that Popper scales across several problem and example dimensions.Source: §1 · p. 6

2 Related work

Related work frames inductive program synthesis as learning programs from partial specifications, with machine-learning approaches emphasizing generalization. Popper differs through learned hypothesis constraints and supports recursive, optimal programs across settings where existing approaches face limitations.

2.1 Inductive program synthesis

  • Inductive program synthesis induces programs from partial specifications, typically input/output examples; Popper contrasts with approaches that do not evaluate generalization.The paper distinguishes programming-language approaches that seek any fitting program from machine-learning approaches that seek generalization to unseen examples.Source: §2.1 · p. 6

2.2 Inductive logic programming

  • Popper learns constraints from hypotheses to prune the hypothesis space, rather than refining individual clauses or hypotheses directly.Reasoning about the hypothesis space lets it prune large regions by testing a single hypothesis.Source: §2.2 · p. 7

2.3 Recursion

  • Popper searches over logic programs to address set-covering ILP systems’ difficulty learning recursive programs, which can limit generalization from few examples.Set-covering systems are often efficient because their search is example-driven, but tend toward overly specific solutions.Source: §2.3 · p. 7

2.4 Optimality

  • Popper’s optimal solutions minimize the total number of literals, whereas many ILP systems lack guarantees of optimality.The paper notes that better generalization is a claimed advantage of optimal solutions.Source: §2.4 · p. 8

2.5 Language bias

  • Popper uses simple predicate declarations instead of mode declarations, and can simulate metarules through hypothesis constraints when suitable metarules are known.Metarules specify exact clause forms, but choosing them can be difficult, especially with background predicates of arity greater than two.Source: §2.5 · p. 8

2.6 Answer set programming

  • Popper combines ASP generation with Prolog reasoning to handle large or infinite domains, including lists and real numbers.Pure ASP-based ILP systems face grounding limits on large domains; Popper’s comparison with ILASP3 also notes that Popper does not support noise.Source: §2.6 · p. 9

2.7 Hypothesis constraints

  • Popper supports declarative hypothesis constraints for restrictions such as types and metarules, and for pruning redundant or failed-hypothesis generalisations and specialisations.Unlike predefined constraints alone, Popper can learn constraints from failed hypotheses.Source: §2.7 · p. 10

3 Problem setting

The problem setting defines learning definite programs from positive and negative examples with background knowledge. Predicate declarations and hypothesis constraints restrict candidate programs, and solutions must cover all positive examples while excluding negative ones.

3.1 Logic preliminaries

  • Logic preliminaries define clauses and theories as sets of literals and clauses, respectively, and distinguish Horn, definite, and Datalog forms.Datalog clauses contain no function symbols, and every head variable also occurs in the body.Source: §3.1 · pp. 10–11

3.2 Problem setting

  • The learning task takes positive and negative target-predicate examples and background knowledge, and seeks a definite program entailing all positives and none of the negatives.The paper leaves generalization to non-monotonic programs for future work.Source: §3.2 · p. 11
  • Predicate declarations specify which predicate symbols may occur in clause heads or bodies, while hypothesis constraints further restrict the hypothesis space.The input comprises background knowledge, declarations, constraints, and positive and negative examples; the background knowledge is assumed not to depend on any hypothesis.Source: §3.2 · pp. 11, 13
  • A solution is a complete and consistent hypothesis; among solutions, an optimal one minimizes the total number of literals.A failed hypothesis is either incomplete or inconsistent.Source: §3.2 · p. 13

3.3 Hypothesis space

The unconstrained hypothesis space can be extremely large, motivating the use of learned constraints to reduce the candidates considered.

3.3 Hypothesis space

  • The unconstrained hypothesis-space size depends on the declaration bias and bounds on arity, variables, body literals, and clauses.The paper’s size proposition formalizes the maximum number of hypotheses from these parameters, and notes that non-trivial inputs yield huge spaces.Source: §3.3 · p. 14

3.4 Generalisations and specialisations

The paper uses theta-subsumption to define syntactic generality and specialization, which support pruning the hypothesis space.

3.4 Generalisations and specialisations

  • Learned constraints use subsumption to prune generalisations and specialisations of failed hypotheses from the hypothesis space.These definitions provide the basis for the subsequent constraints.Source: §3.4 · pp. 14–15
  • Clause subsumption holds when a substitution makes one clause a subset of another, and is decidable unlike clause entailment.Subsumption is weaker than entailment; deciding it is NP-complete in general.Source: §3.4 · p. 14
  • Theory subsumption requires every clause in the second theory to be subsumed by some clause in the first, and implies entailment.The paper defines a generalisation by theory subsumption and a specialisation by the reverse relation.Source: §3.4 · p. 15

3.5 Learning constraints from failures

Learning from failures derives hypothesis-space constraints from failed tests. Generalisation and specialisation constraints preserve all consistent or complete hypotheses, while elimination constraints allow further pruning under additional assumptions.

3.5.1 Generalisations and specialisations

  • Incompleteness prunes specialisations, while inconsistency prunes generalisations; both constraint types are shown sound because they exclude only hypotheses that remain incomplete or inconsistent.A complete hypothesis or a consistent one, respectively, does not yield pruning by these rules.Source: §3.5.1 · pp. 16–17

3.5.2 Eliminations

  • A totally incomplete hypothesis permits pruning separable hypotheses containing its specialisations, beyond ordinary specialisation pruning.Elimination constraints are sound with respect to optimal solutions for separable definite programs, but can prune solutions outside that guarantee.Source: §3.5.2 · pp. 17–18
  • Elimination constraints rely on definite programs and separability; they cannot safely prune non-separable hypotheses, including recursive hypotheses that may contain an otherwise totally incomplete clause.Separable programs can still be recursive.Source: §3.5.2 · pp. 17, 19

3.5.3 Constraints summary

  • The constraints summary organizes which constraints follow from combinations of test outcomes; Pall and Nnone indicate that a solution has been found.The section points to Popper as using these constraints to learn definite programs.Source: Table 2 · p. 19, §3.5.3 · p. 19

4 Popper

This section describes Popper’s generate-test-constrain search over logic programs, using ASP constraints to shape and prune the hypothesis space and Prolog to test candidates. It illustrates the process with a worked example and presents correctness results on representing eligible hypotheses and finding optimal solutions under a decidability condition.

4 Popper

  • Popper combines generate, test, and constrain stages, searching for programs of increasing size until it finds an optimal solution or exhausts the hypotheses.Its algorithm combines answer set programming and Prolog; the paper states that it proves Popper sound and complete.Source: §4 · p. 20

4.0.1 Validity, redundancy, and efficiency constraints

  • Popper uses constraints to prune invalid recursive programs, subsumption-redundant clauses, and variable-renamed programs that could be generated in a canonical form.Examples include preventing recursion without a base case and requiring variables to be used in order.Source: §4.0.1 · pp. 21–22, Figure 3 · p. 22

4.0.2 Language bias constraints

  • Optional language-bias constraints support type restrictions, Datalog restrictions, mode-declaration recall and input/output arguments, functional and irreflexive constraints, and recursion restrictions.Popper can also impose metarules so each program clause is an instance of a clause template.Source: §4.0.2 · p. 22, Figure 4 · p. 23

4.0.3 Hypothesis constraints

  • Unlike clause constraints, Popper's hypothesis constraints apply to whole programs and can express restrictions such as banning recursive programs without base cases or mutually recursive programs.The paper also describes simulating metarules through hypothesis constraints and claims no other ILP system supports them with the same ease and flexibility.Source: §4.0.3 · pp. 22–23

4.1 Test

  • For testing, Popper converts answer sets to definite programs, orders body literals when input/output directions are specified, and uses Prolog to check entailment with a timeout.If a candidate fails, Popper identifies the failure type to determine which constraints to generate.Source: §4.1 · p. 23

4.2 Constrain

  • From failed hypotheses, Popper derives generalisation, specialisation, and elimination constraints; it also uses banish constraints to prune one exact hypothesis for comparison experiments.Specialisation requires distinct clauses to specialise each original clause and allows no extra clauses; banish constraints prohibit additional literals or clauses.Source: §4.2 · p. 24, §4.2.3 · p. 25, §4.2.4 · p. 26

4.2.1 Encoding atoms

  • Popper encodes atoms as ASP head or body literals with predicate, arity, and variable indices, then encodes clauses with distinct-variable assertions and clause identifiers.Clause inclusion records that a clause contains the encoded literals; exact occurrence additionally checks its body-literal count.Source: §4.2.1 · p. 24, §4.2.2 · pp. 24–25

4.3 Popper loop and multi-shot solving

  • Clingo multi-shot solving preserves solver state across stages, grounding only added constraints and new program-size bounds rather than restarting the search.When a size has no remaining answer sets, Popper increments the size and disables the previous bound; the solver avoids revisiting considered hypotheses.Source: §4.3 · pp. 28–29

4.4 Worked example

  • In the worked example, Popper prunes specialisations of a too-specific hypothesis and generalisations of one that entails a negative example, then returns a hypothesis that passes testing.The too-specific hypothesis entails no positive examples; the overgeneral one entails last([e,m,m,a],m).Source: §4.4 · pp. 30–31

4.5 Correctness

  • The correctness results require a hypothesis space of decidable programs; they do not hold for arbitrary definite programs because entailment checking is only semi-decidable.In practice, list-transformation experiments use a timeout and assume solutions terminate before it.Source: §4.5 · p. 31
  • Popper’s base encoding has a model for every hypothesis consistent with the declaration bias and stated size parameters.The encoding represents head and body literals allowed by the bias while enforcing the limits on variables, body literals, and clauses.Source: §4.5 · p. 31
  • Popper never prunes optimal solutions: it prunes specialisations of incomplete hypotheses, generalisations of inconsistent ones, and separable hypotheses containing totally incomplete ones.These are the three constraint types used by Popper.Source: §4.5 · p. 32
  • Popper is sound and complete, and returns an optimal solution whenever one exists.Every returned hypothesis is a solution; if a solution exists, Popper returns one, and its returned solution is optimal.Source: §4.5 · pp. 31–32

5 Experiments

The experiments evaluate Popper’s learned constraints, scalability, and comparative performance across button-pressing, robot-strategy, and list-transformation tasks. They also examine scaling with example count and size, sensitivity to hypothesis-space parameters, and difficult list problems requiring recursion and large domains.

5 Experiments

  • Direct comparisons among ILP systems are difficult because systems support different problem types and use different biases, so results should not be read as proving one system is generally better.The paper notes differences in list support, noise handling, and parameter settings as examples of these comparability limits.Source: §5 · p. 33

5.1.1 Materials

  • The button experiment varies solution size n = 1–10 across 20- and 200-button domains, using 200 positive and 200 negative examples per task, ten repetitions, and one-minute timeouts.The experiments fix the number of buttons within each dataset and vary how many must be pressed.Source: §5.1.1 · p. 34, §5.1 · p. 34, §5.1.2 · p. 35

5.1.3 Results

  • On both button datasets, Popper learns solutions with ten body literals, while Enumerate reaches only n = 3 for p = 20 and n = 1 for p = 200.Popper learns these solutions comfortably within the time limit, supporting the finding that constraints can drastically improve learning performance.Source: Figure 9 · p. 35, §5.1.3 · p. 35
  • Popper outperforms Metagol, ILASP2i, and ILASP3 on the button task, while Aleph does better on the small dataset for n > 8 and Popper does better on the large dataset for n > 3.Metagol’s largest learned programs take 50 seconds on the small dataset and 57 seconds on the large one, compared with one and eight seconds for Popper; ILASP systems struggle because they pre-compute clauses.Source: §5.1.3 · pp. 35–36

5.2.2 Methods

  • The robot experiment fixes the recursive goal of moving to the top row and varies grid size from 10 × 10 to 100 × 100, evaluating predictive accuracy and learning time.Each task uses 20 positive and 20 negative training examples and 1,000 of each for testing; failures to learn within one minute receive the 50% default accuracy.Source: §5.2 · p. 36, §5.2.2 · p. 38

5.2.3 Results

  • About 40 times quicker than Enumerate on average, Popper achieves the best predictive accuracy and fastest learning time in the robot experiment, with learning time not increasing as grid size grows.The results suggest that Popper scales well with domain size and can outperform other ILP systems on this task.Source: §5.2.3 · pp. 38–39, Figure 11 · p. 39

5.3 List transformation problem

  • The ten list-transformation tasks span monadic, dyadic, and triadic targets and functional and relational problems; they are described as difficult because generalizing solutions requires recursion and large domains.The experiment compares Popper, Enumerate, Metagol, and Aleph because ILASP2i and ILASP3 do not support lists; it generates 10 positive and 10 negative training examples and 1,000 of each for testing.Source: §5.3 · p. 39, §5.3.1 · pp. 39–40, §5.3.2 · p. 40

5.3.3 Results

  • Popper equaled or outperformed Enumerate in accuracy and substantially beat it in learning time, finding evens in 4 seconds versus 159 seconds; constraints improve learning performance overall.The comparison covers list-transformation tasks.Source: §5.3.3 · p. 41, Table 5 · p. 42, Table 6 · p. 42
  • Popper equaled or outperformed Metagol in accuracy except on finddup, where Metagol was 2% higher; Aleph learned accurate solutions only for addhead and threesame.The two Aleph exceptions do not require recursion.Source: §5.3.3 · p. 41, Table 5 · p. 42

5.4.2 Settings

  • The scalability experiments varied training-example count and input-list length, using the same materials as the list-transformation experiment and measuring accuracy and learning time over 10 repetitions.The example-count experiment used 1,000–10,000 positive and negative training examples; the size experiment used 10 of each and list lengths from 50 to 500.Source: §5.4 · pp. 42–43, §5.4.1 · p. 43, §5.4.2 · p. 43

5.4.3 Results

  • With up to 20,000 examples, Popper continued to find a solution while Metagol eventually fell to 50% default accuracy; Popper’s learning time increased linearly with example count.Predictive accuracies were almost identical until around 10,000 examples; the experiment measured accuracy and learning time across 10 repetitions.Source: §5.4.3 · p. 43, §5.4.2 · p. 43, Figure 12 · p. 44
  • For input lists of lengths 50 and 500, Popper’s mean learning times were both under a second, while Metagol’s were 20 and 54 seconds, respectively.Popper outperformed Metagol in all tested cases; Popper’s added runtime mainly came from executing hypotheses, whereas Metagol searched by inducing and executing partial programs over examples.Source: §5.4.3 · p. 43, Figure 13 · p. 44

5.5.1 Results

  • Popper was sensitive to the maximum number of unique variables and scaled linearly with the maximum number of clauses, but was mostly insensitive to the maximum body-literal count.Doubling the variable limit from 4 to 8 had little performance effect; very large variable and clause limits could cause difficulty. The study varied these three parameters on the len task.Source: Figure 14 · p. 45, §5.5.1 · p. 45

6 Conclusions and limitations

Popper implements learning from failures through hypothesis generation, testing, and constraint learning. Across three domains, the authors report reduced hypothesis spaces, good scaling, and better accuracy and learning times than existing ILP systems, while identifying several limitations and research directions.

6.1.1 Features

  • Popper learns definite programs; it does not currently support non-observational predicate learning, predicate invention, or noisy examples.The authors also identify learning non-monotonic programs as future work; Popper can trivially learn Datalog programs tested using ASP.Source: §6 · p. 45, §6.1.1 · p. 46

6 Conclusions and limitations

  • Popper substantially outperforms existing ILP systems in predictive accuracy and learning time across toy game problems, robot strategies, and list transformations.The experiments also show that constraints drastically reduce the hypothesis space and that Popper scales across several problem and data-size dimensions.Source: §6 · p. 46

6.1.2 Better search

  • The authors propose improving program-generation and testing search, since better generation could reduce the number of programs tested and learning time.They also identify improvements to both predefined and learned hypothesis constraints as a promising direction.Source: §6.1.2 · pp. 46–47, §6.1.3 · p. 47

6.1.3 Better constraints

  • Popper supports simple types, while polymorphic and refinement types are future directions for stronger pruning and expressing program properties.The authors give distinguishing lists of integers from lists of characters and specifying that reverse preserves input and output lengths as examples.Source: §6.1.3 · p. 47
  • The learned constraints are shown sound, but their completeness and broader theory remain open; elimination adds pruning for separable definite programs.The authors suggest further constraints could improve learning performance.Source: §6.1.3 · p. 47

A Popper metarule theory constraints

This appendix defines metarules and describes how Popper encodes and enforces metarule conformity. Each clause in a conformant program must instantiate at least one metarule.

A Popper metarule theory constraints

  • A metarule is a second-order Horn clause that quantifies over predicate symbols; the chain form is P(A,B):-Q(A,C),R(C,B).Source: §A.1 · p. 51

A.2 From a metarule to literals

  • Popper uses encodeSizedClause to derive a literal encoding of a metarule, illustrated with the chain metarule.Source: §A.2 · p. 51

A.3 Asserting metarule conformance

  • A clause conforms when it is an instance of some metarule, and generated rules identify such instances and constrain clauses lacking one.The instance relation requires a substitution θ such that Mθ = C; the constraint rejects clauses not identified as meta_clause.Source: §A.3 · p. 51

B.1 ILASP2i and ILASP3

The appendix lists ILASP2i/ILASP3 configurations for a unary target and twenty unary button predicates, alongside corresponding constraints and metarules.

B.1 ILASP2i and ILASP3

  • The mode declarations specify unary target f and unary positive body predicates button1 through button20.Source: §B.1 · p. 51
  • The Popper declarations set one variable and one clause, with f/1 as the head predicate and button1/1 through button20/1 as body predicates.Source: §B.2 · p. 52
  • The Aleph configuration sets i=6, clause length 2, and 5000 nodes, and declares determinations for f/1 and each button predicate.Source: §B.3 · p. 52
  • The Metagol configuration supplies two unary metarules and lists button1/1 through button20/1 as body predicates.Source: §B.4 · p. 52

C.1 ILASP2i and ILASP3

The appendix lists ILASP2i/ILASP3 configurations for state and move predicates, with associated bias constraints, search bounds, and metarules.

C.1 ILASP2i and ILASP3

  • The mode declarations include unary target predicates f and start_state, four binary move predicates, and unary boundary predicates.Source: §C.1 · p. 52
  • The listed bias constraints restrict repeated variable occurrences and specify occurrence rules for start_state, boundary, and move predicates.Source: §C.1 · pp. 52–53
  • The Popper declarations set bounds of four variables, three body literals, and three clauses, and specify predicate arities and argument directions.Source: §C.1 · p. 53
  • The Aleph configuration sets i=6, clause length 6, and 50000 nodes, with modes and determinations for the move and boundary predicates.Source: §C.1 · pp. 53–54
  • The Metagol declarations list metarules covering unary and binary heads, including a chain form linking two body predicates.Source: §C.1 · p. 54

D Language biases in lists experiment

The list-transformation experiments constrain candidate programs with shared size and predicate biases, alongside target-relation declarations tailored to each problem.

D Language biases in lists experiment

Loading 2005.02259v3…