CoChat
Sign Up
Cited by 13Logic, Reasoning, and KnowledgeAI-based Problem Solving and PlanningLogic, programming, and type systems

Learning higher-order logic programs

Open access
Cropper, Andrew, Morel, Rolf, Muggleton, Stephen·2020·Machine Learning
DOI 10.1007/s10994-019-05862-7
Open this paper in CoChat — free accountOpen PDF

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.

AI snapshot

Written from the paper’s full text.

TL;DR

The paper extends meta-interpretive learning (MIL) to learn higher-order logic programs by allowing higher-order definitions as interpreted background knowledge, implemented in Metagol_ho and HEXMIL_ho. It argues theoretically and shows experimentally that higher-order abstraction with predicate invention can reduce hypothesis/sample complexity and improve predictive accuracy and learning time over first-order MIL.

Key findings

  • Abstracted MIL can reduce textual complexity: for the decryption example, the first-order program in M₂² requires 7 clauses, while the higher-order program requires 3 clauses and 1 extra higher-order variable; the corresponding hypothesis spaces are approximately 10²¹ versus 10¹³ programs.
  • Theorem 1 gives a condition under which abstracted MIL has lower sample complexity than unabstracted MIL: \(s_u > s_a\) when \(n_u - n_a > \frac{k}{j+1} n_a\).
  • Across robot waiter, chess, droplast, and encryption experiments, Metagol_ho learned programs with higher predictive accuracies and lower learning times than Metagol; e.g. in chess Metagol_ho approached 100% accuracy after around six examples while Metagol stayed around default accuracy, and in droplast Metagol_ho reached 100% accuracy after two examples.
  • HEXMIL_ho also improved over HEXMIL in several domains, but HEXMIL and HEXMIL_ho did not scale well; in encryption both failed to find any programs within the time limit, even in an extremely simple version.

Methods

  • The paper extends MIL to abstracted MIL, where background knowledge includes compiled BK and interpreted BK (IBK) consisting of higher-order definitions such as map/3, until/4, and ifthenelse/5; metarules and higher-order predicate invention drive hypothesis search.
  • It introduces Metagol_ho, a Prolog meta-interpreter extension of Metagol, and HEXMIL_ho, an ASP/HEX extension of HEXMIL, and provides theoretical analysis of hypothesis-space size and sample complexity.
  • Experiments compare first-order and higher-order learning in four domains; for each system and each \(m \in \{1,\dots,10\}\), they generate \(m\) positive and \(m\) negative training examples, 1000 positive and 1000 negative testing examples, measure predictive accuracy and learning time over 10 repetitions, and use a 10-minute timeout. Prolog experiments used SWI-Prolog 7.6.4; ASP experiments used Hexlite 1.0.0 with exact metarules and background relations necessary to represent target hypotheses because HEXMIL failed to learn under the common methodology.

Limitations

  • Stated: the choice of metarules is not fully justified; the three curry metarules lack theoretical justification and each requires an extra clause when used with abstractions.
  • Stated: the approach requires user-provided higher-order definitions such as map/3; future work should learn or invent such definitions.
  • Stated: negation of invented predicates is unsupported, and HEXMIL/HEXMIL_ho suffer from scalability and grounding issues.
  • Evident from the text: the ASP experiments did not use the same methodology as the Prolog experiments because HEXMIL failed to learn any programs due to scalability, and the paper does not directly compare the Prolog and ASP implementations even though it reports that Metagol outperforms HEXMIL and Metagol_ho outperforms HEXMIL_ho.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1007/s10994-019-05862-7

Cites

50 of 50 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Claims the paper makes

5 of 19 cited sources checked · 4 supported · 0 flagged · accuracy not yet measured

  • Premisecitation
    § 6.1.1 Metarules · p. 30

    Eight of the metarules used in our experiments are a subset of a derivationally irreducible set of monadic and dyadic metarules.

    “Eight of these metarules (the ones with only monadic or dyadic literals) are a subset of a derivationally irreducible set of monadic and dyadic metarules (Cropper and Tourret 2018).”
    Quote in the paperSubstantial claim1 of 1 sources checked
    • cites Cropper and Tourret 2018 source

      Section 4 describes reducing sets of metarules to derivationally minimal sets, and the discussion of derivation reduction defines what makes a set derivationally irreducible. The cited paper does not identify the citing authors’ eight metarules, so our copy cannot establish that those particular eight are a subset of one of its irreducible sets. Page numbers are unavailable in our copy. (LLM, conf=0.82)

      Experimental — accuracy not yet measured
  • Findingnone given
    § 1 Introduction · p. 2

    Metagol ho supports the invention of conditions and functions to an arbitrary depth.

    “Metagol ho supports the invention of conditions and functions to an arbitrary depth, which goes beyond anything in the literature.”
    Quote in the paperNot a substantial claim
  • Findingreasoning
    § Metarules · p. 15

    Metagol ho combines abstraction (learning higher-order programs) and invention (predicate invention).

    “As this scenario illustrates, the real power and novelty of Metagol ho is the combination of abstraction (learning higher-order programs) and invention (predicate invention).”
    Quote in the paperSubstantial claim
  • Findingreasoning
    § 3.3 Language classes, expressivity, and complexity · p. 11

    The hypothesis space of abstracted MIL contains approximately 10^13 programs, which is substantially smaller than the first-order hypothesis space, despite using more metarules and more background relations.

    “Then plugging these values into the formula from Proposition 2 shows that the hypothesis space of abstracted MIL contains approximately 10 13 programs, which is substantially smaller than the first-order hypothesis space, despite using more metarules and more background relations.”
    Quote in the paperSubstantial claim
  • Findingreasoning
    § 3.3 Language classes, expressivity, and complexity · p. 9

    For the M_2^2 fragment, the MIL hypothesis space contains at most (mp^3)^n programs, where m is the number of metarules and n is the number of clauses in the target program.

    “For instance, for the M 2 2 fragment, the MIL hypothesis space contains at most ( mp 3 ) n programs, where m is the number of metarules and n is the number of clauses in the target program.”
    Quote in the paperNot a substantial claim
  • Classified as probably not a substantial claim. 22
  • May combine two claims. 31
  • The quote only partly states this claim. 1

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation
    § 2.6 Abstraction and invention · p. 5

    Predicate invention has been repeatedly stated as an important challenge in ILP.

    “Predicate invention has been repeatedly stated as an important challenge in ILP (Muggleton and Buntine 1988; Stahl 1995; Muggleton et al. 2012).”
    Quote in the paperNot a substantial claim2 of 3 sources checked
    • cites Muggleton and Buntine 1988 source
    • cites Stahl 1995 source
    • cites Muggleton et al. 2012 source

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation
    § 2.1 Program induction · p. 3

    MIL supports predicate invention.

    “In addition, MIL supports predicate invention , which has been repeatedly stated as an important challenge in ILP (Muggleton and Buntine 1988; Stahl 1995; Muggleton et al. 2012).”
    Quote in the paperNot a substantial claim2 of 3 sources checked
    • cites Muggleton and Buntine 1988 source
    • cites Stahl 1995 source
    • cites Muggleton et al. 2012 source

  • May combine two claims.

    Findingreasoning
    § 3.3 Language classes, expressivity, and complexity · p. 11

    In the example, the target hypothesis, or a hypothesis equivalent to it, is in both hypothesis spaces, but the abstracted MIL space is smaller.

    “In this example, the target hypothesis, or a hypothesis that is equivalent 3 to the target hypothesis, is in both hypothesis spaces but the abstracted MIL space is smaller.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

    Findingnone given
    § 3.2 Abstracted meta-interpretive learning · p. 7

    The distinction between BI and M is that the clauses in BI are all universally quantified, whereas the metarules in M contain existentially quantified variables whose substitutions form the induced program.

    “The distinction between BI and M is that the clauses in BI are all universally quantified, whereas the metarules in M contain existentially quantified variables whose substitutions form the induced program.”
    Quote in the paperNot a substantial claim

  • Classified as probably not a substantial claim.

    Findingnone given
    § 1 Introduction · p. 2

    Metagol ho extends Metagol to support interpreted BK (IBK).

    “Metagol ho extends Metagol to support interpreted BK (IBK).”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 1 Introduction · p. 2

    The higher-order decryption program in Fig. 2b is much smaller and requires half the number of literals (6 vs. 12) compared to the first-order program in Fig. 2a.

    “The programs are success set equivalent when restricted to the target predicate decrypt/2 but the higher-order program is much smaller and requires half the number of literals (6 vs. 12).”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Findingown data
    § 3.2 Abstracted meta-interpretive learning · p. 8

    In the example, a MIL learner has invented the predicate f1/2 for use in a map/3 definition.

    “In this program, a MIL learner has invented the predicate f1/2 for use in a map/3 definition.”
    Quote in the paperNot a substantial claim

  • Classified as probably not a substantial claim.

    Findingnone given
    § 2.5 Higher-order logic · p. 5

    The paper introduces higher-order definitions which allow for invented predicate symbols to be used as arguments in literals.

    “By contrast, we introduce higher-order definitions which allow for invented predicate symbols to be used as arguments in literals.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 3.3 Language classes, expressivity, and complexity · p. 10

    The first-order decryption program would require seven clauses, while the higher-order program requires only three clauses and one extra higher-order variable.

    “Figure 3a shows that the first-order program would require seven clauses. By contrast, Fig. 3b shows that the higher-order program requires only three clauses and one extra higher-order variable.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § Abstract · p. 1

    Experiments in four domains (robot strategies, chess playing, list transformations, and string decryption) show that learning higher-order programs can substantially improve predictive accuracies and reduce learning times compared to learning first-order programs.

    “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.”
    • Also stated in: § 1 Introduction · p. 3 · boosted
      “In all cases learning higherorder programs leads to substantial increases in predictive accuracies and lower learning times in agreement with our theoretical results.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingnone given
    § 4.5 Complexity of the search · p. 18

    The performance of HEXMIL is a function of the number of constant symbols, which is not the case for Metagol.

    “Our main observation is that the performance of HEXMIL is a function of the number of constant symbols, which is not the case for Metagol.”
    Quote in the paperNot a substantial claim

  • Classified as probably not a substantial claim.

    Findingreasoning
    § 3.2 Abstracted meta-interpretive learning · p. 7

    The procedural distinction between BC and BI is that a clause from BC is proved deductively (by calling Prolog), while a clause from BI is proved through meta-interpretation, which allows for predicate invention to be combined with abstractions to invent higher-order predicates.

    “The procedural distinction between BC and BI is that whereas a clause from BC is proved deductively (by calling Prolog), a clause from BI is proved through meta-interpretation, which allows for predicate invention to be combined with abstractions to invent higher-order predicates.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 5.2.3 Results · p. 21

    In all cases Metagol ho learns programs with higher predictive accuracies and lower learning times than Metagol.

    “Figure 10 shows that in all cases Metagol ho learns programs with higher predictive accuracies and lower learning times than Metagol.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 5.2.3 Results · p. 21

    Metagol learns a recursive program, whereas Metagol ho avoids recursion and uses the higher-order abstraction until/4.

    “Whereas Metagol learns a recursive program, Metagol ho avoids recursion and uses the higher-order abstraction until/4 .”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Findingnone given
    § 6.1.2 Higher-order definitions · p. 32

    We have used abstracted MIL to invent functional constructs.

    “Similarly, we have used abstracted MIL to invent functional constructs.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data
    § 4.5 Complexity of the search · p. 18

    HEXMIL and HEXMIL ho do not scale well, both in terms of the amount of BK and the number of training examples.

    “The experimental results also show that HEXMIL and HEXMIL ho do not scale well, both in terms of the amount of BK and the number of training examples.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 5.4.3 Results · p. 27

    The program learned in the repeated droplast experiment includes the invented predicate f3/2 which reverses a given list and is used twice.

    “This program now includes the invented predicate f3/2 which reverses a given list and is used twice in the program.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Findingnone given
    § 6.1.1 Metarules · p. 30

    We have additionally used three curry metarules with arities three, four, and five, which were not considered in the work on identifying derivationally irreducible metarules.

    “However, we have additionally used three curry metarules with arities three, four, and five, which were not considered in the work on identifying derivationally irreducible metarules.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Findingnone given
    § 6.1.3 Learning higher-order abstractions · p. 32

    Our preliminary work suggests that learning such definitions is possible.

    “Our preliminary work suggests that learning such definitions is possible.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data
    § 5.3.3 Results · p. 24

    In the chess experiment, Metagol ho learns programs with higher predictive accuracies and lower learning times than Metagol in all cases.

    “Figure 16 shows that in all cases Metagol ho learns programs with higher predictive accuracies and lower learning times than Metagol.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 5.6 Discussion · p. 30

    Our empirical results contradict those by Kaminski et al. (2018), but support those by Morel et al. (2019).

    “Our empirical results contradict those by Kaminski et al. (2018), but support those by Morel et al. (2019).”
    Quote in the paperNot a substantial claim0 of 2 sources checked
    • cites Kaminski et al. (2018)

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

    • cites Morel et al. (2019) source

  • May combine two claims.

    Findingreasoning
    § 5.2.3 Results · p. 21

    Although both programs are general and handle any number of guests and any assignment of drink preferences, the program learned by Metagol ho is smaller than the one learned by Metagol.

    “Although both programs are general and handle any number of guests and any assignment of drink preferences, the program learned by Metagol ho is smaller than the one learned by Metagol.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingreasoning
    § 5.5.3 Results · p. 29

    In the encryption experiment, Metagol ho learns programs with higher predictive accuracies and lower learning times than Metagol.

    “Figure 26 shows that, as with the other experiments, Metagol ho learns programs with higher predictive accuracies and lower learning times than Metagol.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingnone given
    § 6.2 Summary · p. 32

    The techniques allow us to learn substantially more complex programs using fewer examples with less search.

    “We have shown that the techniques allow us to learn substantially more complex programs using fewer examples with less search.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingnone given
    § 6 Conclusions and further work · p. 30

    Learning higher-order programs can reduce the textual complexity required to express target classes of programs which in turn reduces the hypothesis space.

    “We showed that learning higher-order programs can reduce the textual complexity required to express target classes of programs which in turn reduces the hypothesis space.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingreasoning
    § curry2 metarule · p. 19

    The search complexity of Metagol is independent of the number of constant symbols and is the same as Proposition 1.

    “It follows that the search complexity of Metagol is independent of the number of constant symbols and is the same 8 as Proposition 1.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Premisereasoning
    § 2.3 Inductive logic programming · p. 4

    Existing MIL implementations such as Metagol can learn a program using map/3 as background knowledge, but cannot invent the predicate f1/2 because Metagol deductively proves BK by delegating proofs to Prolog.

    “Existing MIL implementations, such as Metagol, could learn a similar program to the one above when map/3 is provided as background knowledge. However, even though Metagol supports predicate invention, it is unable to invent the predicate f1/2 in the example above because Metagol deductively proves BK by delegating the proofs to Prolog.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation
    § 4.3 HEXMIL · p. 15

    An ASP implementation can be more efficient than a Prolog implementation because ASP solvers employ efficient conflict propagation, which is important for detecting the derivability of negative examples early during ASP search.

    “As argued by Kaminski et al., an ASP implementation can be more efficient than a Prolog implementation because ASP solvers employ efficient conflict propagation, which is important for detecting the derivability of negative examples early during ASP search.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites Kaminski et al.

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • May combine two claims.

    Interpretationcitation
    § 2.6 Abstraction and invention · p. 5

    The approach supports a form of abstraction which goes beyond typical first-order predicate invention in that the use of higher-order definitions combined with meta-interpretation drives both the search for a hypothesis and predicate invention, leading to more accurate and compact programs.

    “This approach supports a form of abstraction which goes beyond typical first-order predicate invention (Saitta and Zucker 2013) in that the use of higher-order definitions combined with meta-interpretation drives both the search for a hypothesis and predicate invention, leading to more accurate and compact programs.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites Saitta and Zucker 2013 source

  • Classified as probably not a substantial claim. May combine two claims.

    Interpretationnone given
    § 3.2 Abstracted meta-interpretive learning · p. 8

    The first condition of the abstracted MIL problem ensures that a logic program hypothesis is an instance of the given metarules, and this condition enforces the strong inductive bias in MIL.

    “The first condition ensures that a logic program hypothesis is an instance of the given metarules. It is this condition that enforces the strong inductive bias in MIL.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim.

    Premisecitation
    § 4.3 HEXMIL · p. 15

    HEXMIL is an answer set programming (ASP) encoding of MIL introduced by Kaminski et al. (2018).

    “HEXMILis an answer set programming (ASP) encoding of MIL introduced by Kaminski et al. (2018).”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites Kaminski et al. (2018)

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • May combine two claims.

    Premisereasoning
    § 4.3 HEXMIL · p. 15

    HEXMIL benefits from external atoms by allowing for arbitrary encodings of complex structures and incremental introduction of new constants.

    “HEXMIL benefits from external atoms by allowing for arbitrary encodings of complex structures (e.g. we encode lists as strings, thereby reducing the number of variables needed in the encoding). Another benefit is that external atoms allow for the incremental introduction of new constants (i.e. symbols not in the initial ASP program).”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation
    § 4.1 Metagol · p. 12

    Metagol is a MIL learner based on a Prolog meta-interpreter.

    “Metagol (Cropper and Muggleton 2016b) is a MIL learner based on a Prolog meta-interpreter.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites Cropper and Muggleton 2016b

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Classified as probably not a substantial claim. May combine two claims.

    Interpretationreasoning
    § 3.3 Language classes, expressivity, and complexity · p. 10

    The theoretical results motivate the use of abstracted MIL and help explain the experimental results.

    “The results from this section motivate the use of abstracted MIL, and help explain the experimental results (Sect. 5).”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationreasoning
    § 2.4 Meta-interpretive learning · p. 4

    The ASP approach is highly sensitive to the number of constant symbols, which leads to scalability issues.

    “We show that the ASP approach is highly sensitive to the number of constant symbols, which leads to scalability issues.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim.

    Premisecitation
    § 3.3 Language classes, expressivity, and complexity · p. 11

    The Blumer bound states that given two hypothesis spaces of different sizes, searching the smaller space will result in less error compared to the larger space, assuming that the target hypothesis is in both spaces.

    “The Blumer bound (Blumer et al. 1987) says that given two hypothesis spaces of different sizes, then searching the smaller space will result in less error compared to the larger space, assuming that the target hypothesis is in both spaces.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites Blumer et al. 1987 source

  • May combine two claims.

    Premisecitation
    § 2.3 Inductive logic programming · p. 4

    Progol and Aleph could learn higher-order programs such as f(A,B):-map(A,B,f1) given appropriate mode declarations, but because they do not support predicate invention, they would be unable to invent f1/2.

    “Given appropriate mode declarations (Muggleton 1995) for higher-order predicates such as map/3 , Progol and Aleph could learn higher-order programs such as f(A,B):-map(A,B,f1) . However, because Progol and Aleph do not support predicate invention, they would be unable to invent the predicate f1/2 in the above example.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites Muggleton 1995 source

  • May combine two claims.

    Interpretationown data
    § 5.3.3 Results · p. 24

    The results from the chess experiment suggest that we can reject null hypotheses 1 and 2.

    “The results from this experiment suggest that we can reject null hypotheses 1 and 2.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

    Interpretationcitation
    § 5.6 Discussion · p. 30

    HEXMIL should benefit from more negative examples, but may suffer from fewer.

    “Therefore, HEXMIL should benefit from more negative examples, but may suffer from fewer.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationown data
    § 5.6 Discussion · p. 30

    The main problem with HEXMIL is that of ASP grounding; in most experiments, HEXMIL timed out during the grounding (and not solving) stage.

    “We think that the main problem with HEXMIL is that of ASP grounding in most of our experiments, HEXMIL timed out during the grounding (and not solving) stage.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Interpretationreasoning
    § curry2 metarule · p. 19

    The same complexity reasoning can be applied to the abstracted MIL setting.

    “For simplicity, the above complexity reasoning was for the first-order systems. We can easily apply the same reasoning to the abstracted MIL setting.”
    Quote in the paperNot a substantial claim

  • May combine two claims. The quote only partly states this claim.

    Interpretationreasoning
    § 5.3.3 Results · p. 24

    The larger first-order program is more difficult to learn because the MIL hypothesis space grows exponentially in the size of the target hypothesis.

    “which is why the larger first-order program is more difficult to learn.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim. May combine two claims.

    Study design and conductreasoning
    § 5.1 Common materials · p. 20

    In the Prolog experiments, the only variable is the system (Metagol or Metagol ho), because the same metarules and IBK are used in each experiment.

    “In the Prolog experiments we use the same metarules and IBK in each experiment, i.e. the only variable in the Prolog experiments is the system (Metagol or Metagol ho ).”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Interpretationreasoning
    § 6.1.1 Metarules · p. 30

    We have no theoretical justification for using the curry metarules.

    “Although these metarules seem intuitive and sensible to use, we have no theoretical justification for using them.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationown data
    § 5.2.3 Results · p. 21

    The results from this experiment suggest that we can reject null hypotheses 1 and 2.

    “The results from this experiment suggest that we can reject null hypotheses 1 and 2.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S2 (checkable), S3 (load-bearing), S4 (based).

    Interpretationreasoning
    § 5.4.4 Further discussion · p. 28

    This form of higher-order abstraction and invention goes beyond anything in the existing literature.

    “This form of higher-order abstraction and invention goes beyond anything in the existing literature.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationreasoning
    § 5.2.3 Results · p. 21

    The compactness of the higher-order program affects predictive accuracies because Metagol ho almost always finds the target hypothesis in the allocated time, while Metagol often struggles because the programs are too large.

    “The compactness of the higher-order program affects predictive accuracies because, whereas Metagol ho almost always finds the target hypothesis in the allocated time, Metagol often struggles because the programs are too large, as explained by our theoretical results in Sect. 3.3.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S2 (checkable).

    Interpretationreasoning
    § 5.5.3 Results · p. 29

    The encryption experiment suggests that HEXMIL needs to be better at determining which groundings are relevant to consistent hypotheses.

    “The experiment suggests that HEXMIL needs to be better at determining which groundings are relevant to consistent hypotheses.”
    Quote in the paperNot a substantial claim
48 of 48

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

Each contradiction between two passages listed here was confirmed by an independent check.

  • Droplast negative-example procedure cannot handle some selected lengths

    Minor

    The procedure permits sublists of length 1 or 2, but requires an integer j satisfying 1 < j < k for every sublist. No such j exists for either of those permitted lengths, and no resampling rule is stated.

1 of 1

Cites

Flagged first, then by citations

Research works printed but not linked: 3

  1. Bratko, I., & Michie, D. (1980). A representation for pattern-knowledge in chess endgames. Advances in Computer Chess, 2, 31–56.
  2. Mitchell, T. M. (1997). Machine learning. McGraw Hill series in computer science. McGraw-Hill.
  3. Srinivasan, A. (2001). The ALEPH manual. Machine Learning at the Computing Laboratory: Oxford University.

Cited by

Sorted by citations

Related

Authors
Cropper, A., Morel, R., & Muggleton, S.
Affiliations
  • University of Oxford (GB)
  • Imperial College London (GB)
Corresponding author
Cropper, Andrew
ORCID
Venue
Machine Learning
Publisher
Springer Science and Business Media LLC
Published
2019-12-03
Volume
109
Issue
7
Pages
1289-1322
ISSN
  • 0885-6125 (ISSN-L)
  • 1573-0565
DOI
10.1007/s10994-019-05862-7
OpenAlex
W2963653872
Semantic Scholar
ab72a87f395db6f38ad4708a0fc764c4711920fe
Cited by
11
References
43
Citations by year
2023: 2 · 2022: 1 · 2021: 1 · 2020: 7
FWCI
1.02
Type
journal article
Language
en
Open access
Licence
Locations
  • Machine Learning (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
Engineering and Physical Sciences Research Council (EP/N509711/1)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Logic, Reasoning, and Knowledge
  • Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
  • Physical Sciences › Computer Science › Artificial Intelligence › Logic, programming, and type systems
Keywords
inductive logic programming, prior knowledge, sample complexity, Prolog, answer set programming

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Claims read by deepseek-v4.1-flash under definition version 3 (extract-v3) on 2026-10-19.

Classified by jev-1.13-20260917 (gold-guideline-v0.2) on 2026-10-19.

Cited sources are checked by gpt-6-sol.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review