CoChat
Sign Up
Cited by 184Logic, Reasoning, and KnowledgeComputability, Logic, AI AlgorithmsAI-based Problem Solving and Planning

Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited

Open access
Muggleton, Stephen H., Lin, Dianhuan, Tamaddoni-Nezhad, Alireza·2015·Machine Learning
DOI 10.1007/s10994-014-5471-y
Open this paper in CoChat — free accountOpen PDF

Verified 2026-10-19 · 1 reference not checked yet

AI snapshot

Written from the paper’s full text.

TL;DR

The paper generalises meta-interpretive learning (MIL) to higher-order dyadic datalog programs in the class H₂², showing that H₂² is Turing expressive with an infinite signature but decidable with a finite signature. It implements MetagolD and demonstrates efficient learning with predicate invention and recursion on robot strategies, East-West trains, and NELL data.

Key findings

  • H₂² has universal Turing expressivity when the constant signature is infinite, but satisfiability is decidable when the predicate and constant signatures are finite; the MIL setting is decidable when meta-rules, background knowledge, and examples are Datalog and signatures are finite.
  • MetagolD, using Knuth-Bendix ordering and logarithmic clause bounding, PAC-learns minimal cardinality H₂² definitions; Theorem 3 gives polynomial sample complexity, and experiments show rapid error reduction with roughly linear learning-time growth under the logarithmic bound.
  • On robot wall-building, MetagolD reaches predictive accuracy above 90% at training size 2 with one positive and one negative example; a dramatic time increase occurs at training size 10 because an additional negative example forces a larger hypothesis.
  • On East-West trains, Metagol learns a recursive theory that correctly classifies all 20 trains in about 45 s on a 2.5 GHz MacBook laptop, equivalent to the winning competition entry, which took about 1 day on a 40 MHz Sun Sparc 10; on NELL, a greedy variant runs in about 0.004 s, hundreds of times faster, and MetagolD learns higher-order concepts such as symmetry.

Methods

  • MIL uses higher-order meta-rules and a modified Prolog meta-interpreter that proves examples and saves metalogical substitutions for existentially quantified higher-order variables; applying these substitutions yields a first-order definite program.
  • MetagolD is implemented in Yap Prolog and constrains search with total orderings over the Herbrand Base (lexicographic/Knuth-Bendix and interval inclusion), iterative deepening for minimal cardinality hypotheses, logarithmic clause bounding, and episodes for multi-predicate incremental learning.
  • Experiments cover robot wall-building (training sizes 2–80, test size 200, half positive/half negative, averaged over five resamples), East-West trains (20 training trains, 100 test trains, averaged over 10 random samples), and NELL athletehomestadium (tenfold cross-validation, 120 examples, 919 background facts, training sizes up to 108).

Limitations

  • The paper states that the NELL evaluation can lead to excessive runtimes; the logarithmic bound was dropped and a 2 min time limit used, causing MetagolD’s learning curve to drop significantly at training size 80.
  • The paper states that the effect of incompleteness of meta-rules on predictive accuracy and robustness was not explored, and that the user is expected to provide the total orderings ⪰P and ⪰C over initial predicates and constants.
  • The paper states that the greedy search variant can lead to overly specific, non-minimal programs and has unresolved overfitting issues; it was not applied to the other experiments. Evident from the text, the robot model is a simplification of a real-world robotics application, and the NELL data is incomplete, with 17% of examples missing teamhomestadium information.

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

Integrity signals

Registry

Crossref · 10.1007/s10994-014-5471-y

Cites

69 of 70 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Claims the paper makes

8 of 31 cited sources checked · 2 supported · 1 flagged · accuracy not yet measured

  • Premisecitation
    § Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited · p. 1

    Predicate invention has been under-explored within inductive logic programming since the late 1990s due to difficulties in formulating efficient search mechanisms.

    “Since the late 1990s predicate invention has been under-explored within inductive logic programming due to difficulties in formulating efficient search mechanisms.”
    • Also stated in: § 1 Introduction · p. 2 · plain
      “Although the topic of Predicate Invention was investigated in early Inductive Logic Programming (ILP) research (Muggleton and Buntine 1988; Stahl 1992) it is still seen as hard and under-explored (Muggleton et al. 2011).”
    Quote in the paperSubstantial claim1 of 1 sources checked
    • cites Muggleton et al. 2011 source
  • Premisereasoning
    § 2 Related work · p. 4

    Inductive generalisation and predicate invention are not achieved in existing EBG paradigms, which assume a complete first-order domain theory.

    “A key difference is that inductive generalisation and predicate invention are not achieved in existing EBG paradigms, which assume a complete first-order domain theory.”
    Quote in the paperSubstantial claim1 of 3 sources checked
    • cites De Jong 1981

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

    • cites Kedar-Cabelli and McCarty 1987 source
    • cites Mitchell et al. 1986 source

      Section 4.2.1 says EBG assumes a domain theory sufficient to prove the training example belongs to the goal concept, so its generalizations follow deductively from existing knowledge. The EBG as Reformulating/Operationalizing/Deducing section likewise says the method compiles deductive consequences of its domain theory. These passages support the distinction from inductive generalisation, but they do not establish that EBG requires a complete first-order domain theory or address predicate invention. (LLM, conf=0.85)

      Experimental — accuracy not yet measured
  • Findingown data
    § Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited · p. 1

    Metagol D efficiently learns compact H2^2 definitions involving predicate invention for learning robotic strategies, the East-West train challenge and NELL.

    “This result is consistent with our experiments which indicate that Metagol D efficiently learns compact H 2 2 definitions involving predicate invention for learning robotic strategies, the East-West train challenge and NELL.”
    Quote in the paperSubstantial claim
  • Findingreasoning
    § Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited · p. 1

    H2^2 is decidable given a finite signature.

    “We show that with an infinite signature the higher-order dyadic datalog class H 2 2 has universal Turing expressivity though H 2 2 is decidable given a finite signature.”
    • Also stated in: § 3.4 Language classes and expressivity · p. 8 · plain
      “Theorem 2 (Decidable fragment of H 2 2 ) The satisfiability of G , P is decidable when P , C is finite.”
    Quote in the paperSubstantial claim
  • Findingown data
    § Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited · p. 1

    Higher-order concepts were learned in the NELL language learning domain.

    “Additionally higher-order concepts were learned in the NELL language learning domain.”
    • Also stated in: § 2 Related work · p. 4 · boosted
      “The NELL language application (Sect. 5.3) demonstrates that higher-order concepts can be readily and naturally expressed in H 2 2 and learned within the MIL framework.”
    Quote in the paperSubstantial claim
  • Classified as probably not a substantial claim. 46
  • May combine two claims. 26
  • The quote only partly states this claim. 1

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

    Premisecitation
    § 2 Related work · p. 5

    Relational Reinforcement approaches for learning robot strategies are based on the use of ground instances and do not involve predicate invention to extend the relational vocabulary provided by the user.

    “However, unlike the approach for learning recursive robot strategies described in Sect. 5.1 the Relational Reinforcement approaches are based on the use of ground instances and do not involve predicate invention to extend the relational vocabulary provided by the user.”
    Quote in the paperNot a substantial claim3 of 3 sources checked
    • cites Džeroski et al. 2001 source

      The Introduction describes states as sets of ground facts, and §5.2 specifies relational states built from basic facts. Section 4.4 says the user can influence learning through supplied background predicates and declarative bias. The paper studies blocks-world planning, however, and the passages do not explicitly establish that the approach never invents predicates or that it learns robot strategies. (LLM, conf=0.84)

      Experimental — accuracy not yet measured
    • cites Katz et al. 2008 source

      The section “Representation of Q-Value Function” (page unavailable) explicitly says that states and actions are relational and stored uninstantiated, contrary to the claim that the approach uses ground instances. The paper describes a defined set of predicates, but does not establish the broader claim about user-provided vocabularies or predicate invention across relational reinforcement approaches. (LLM, conf=0.88)

      Checked by a reasoning model — may be wrong.

      Experimental — accuracy not yet measured
    • cites Driessens and Ramon 2003

      Section 3 (page unavailable) says RRL builds examples from encountered states and chosen actions, represented in datalog or Herbrand interpretations; this supports the claim that it uses ground instances. The paper does not state that RRL avoids predicate invention or limits itself to a user-provided relational vocabulary, and it does not establish the claim specifically for robot strategies. (LLM, conf=0.82)

      Experimental — accuracy not yet measured

  • May combine two claims.

    Premisecitation
    § 1 Introduction · p. 2

    ILP systems such as ALEPH and FOIL have no predicate invention and limited recursion learning and therefore cannot learn recursive grammars from example sequences.

    “ILP systems such as ALEPH (Srinivasan 2001) and FOIL (Quinlan 1990) have no predicate invention and limited recursion learning and therefore cannot learn recursive grammars from example sequences.”
    Quote in the paperSubstantial claim1 of 2 sources checked
    • cites Srinivasan 2001

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

    • cites Quinlan 1990 source

      The Discussion (page not available in our copy) says FOIL cannot invent new predicates, and §5.7 says its handling of recursion is incomplete. But the paper also says FOIL can find recursive definitions; it does not establish that FOIL cannot learn recursive grammars from example sequences. It does not address ALEPH. (LLM, conf=0.88)

      Experimental — accuracy not yet measured

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

    Premisecitation
    § 2 Related work · p. 4

    Failure to address these issues has led to limited progress being made in predicate invention over a protracted period.

    “Failure to address these issues has led to limited progress being made in this important topic over a protracted period (Muggleton et al. 2011).”
    Quote in the paperNot a substantial claim1 of 1 sources checked
    • cites Muggleton et al. 2011 source

  • May combine two claims.

    Interpretationcitation
    § 6 Conclusions and further work · p. 21

    Blumer-bound arguments indicate that search constrained in this way achieves not only speed improvements but also reduction in out-of-sample error.

    “Blumer-bound arguments are provided which indicate that search constrained in this way achieves not only speed improvements but also reduction in out-ofsample error.”
    Quote in the paperSubstantial claim1 of 1 sources checked
    • cites Blumer et al., 1989 source

      The Introduction and Section 2 give VC-dimension bounds on the out-of-sample error of consistent hypotheses, supporting the use of a Blumer bound in a generalization argument. Our copy does not show that the particular search constraint described by the citing paper improves speed or reduces out-of-sample error; those appear to be conclusions of the citing authors' arguments. (LLM, conf=0.84)

      Experimental — accuracy not yet measured

  • May combine two claims.

    Findingown data
    § 5.1.3 Results and discussion · p. 13

    Metagol D, given increasing number of randomly chosen examples, produces rapid error reduction while learning time increases roughly linearly.

    “Metagol 's accuracy and learning time plots shown in Fig. 12 indicate that, consistent with the analysis in Sect. 4.3, Metagol D , given increasing number of randomly chosen examples, produces rapid error reduction while learning time increases roughly linearly.”
    Quote in the paperNot a substantial claim

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

    Findingnone given
    § 3.4 Language classes and expressivity · p. 7

    H2^2 is sufficient for the kinship example in Sect. 1.

    “Note that H 2 2 is sufficient for the kinship example in Sect. 1.”
    Quote in the paperNot a substantial claim

  • Classified as probably not a substantial claim.

    Findingnone given
    § 5.3.2 Evaluation experiment: learning athletehomestadium · p. 20

    There are seven clauses in this hypothesis.

    “There are seven clauses in this hypothesis.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 5.3.1 Initial experiment: debugging NELL using abduction · p. 18

    In our initial experiment Metagol inductively inferred the clause above from NELL data and used it to abduce the following facts, not found in the database.

    “In our initial experiment Metagol inductively inferred the clause above from NELL data and used it to abduce the following facts, not found in the database.”
    Quote in the paperSubstantial claim

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

    Findingown data
    § 6.1 Further work · p. 22

    In the NELL experiment described in Sect. 5.3.2 we found that a greedy modification of the Metagol D search strategy leads to considerable speed increases.

    “In the NELL experiment described in Sect. 5.3.2 we found that a greedy modification of the Metagol D search strategy leads to considerable speed increases.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data
    § 5.3.1 Initial experiment: debugging NELL using abduction · p. 18

    Abductive hypotheses 1 and 3 are erroneous.

    “However, 1 and 3 are erroneous.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingreasoning
    § 5.3.2 Evaluation experiment: learning athletehomestadium · p. 20

    The running time with the greedy search strategy is around 0.004s, which is hundreds of times faster than the original MetagolD without being greedy.

    “Therefore, the running time with the greedy search strategy is around 0.004s, which is hundreds of times faster than the original MetagolD without being greedy.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data
    § 5.3.2 Evaluation experiment: learning athletehomestadium · p. 20

    This data is incomplete. Specifically, 17% of the examples have incomplete information on teamhomestadium, requiring abduction of ground facts.

    “However, this data is incomplete. Specifically, 17% of the examples have incomplete information on teamhomestadium , requiring abduction of ground facts.”
    Quote in the paperSubstantial claim

  • The quote only partly states this claim.

    Findingown data
    § 5.2.3 Results and discussion · p. 17

    Progol can quickly find a partial solution shown in Fig. 18.

    “When provided with all 20 trains, Progol can quickly find a partial solution shown in Fig. 18.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data
    § 6 Conclusions and further work · p. 22

    In an evaluation experiment it was found that learning on the NELL dataset can lead to excessive runtimes, which are improved using a greedy version of the search Metagol mechanism.

    “In an evaluation experiment it was found that learning on the NELL dataset can lead to excessive runtimes, which are improved using a greedy version of the search Metagol mechanism.”
    Quote in the paperSubstantial claim

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

    Findingown data
    § 5.3.2 Evaluation experiment: learning athletehomestadium · p. 20

    Using this Metagol D abduced the following hypothesis.

    “Using this Metagol D abduced the following hypothesis.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingcitation
    § 5.2.3 Results and discussion · p. 15

    This theory correctly classifies all 20 trains and is equivalent to the winning entry for the first competition submitted by Bernhard Pfahringer.

    “This theory correctly classifies all 20 trains and is equivalent to the winning entry for the first competition submitted by Bernhard Pfahringer (Turney 1995).”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites Turney 1995

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

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

    Findingown data
    § 5.3.2 Evaluation experiment: learning athletehomestadium · p. 20

    The background knowledge contained 919 facts about athleteplays f orteam and teamhomestadium.

    “The background knowledge contained 919 facts about athleteplays f orteam and teamhomestadium .”
    Quote in the paperNot a substantial claim

  • May combine two claims.

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

    The dyadic datalog fragment H 2 2 is Turing expressive in the case of an infinite signature, but decidable otherwise.

    “This fragment is shown to be Turing expressive in the case of an infinite signature, but decidable otherwise.”
    Quote in the paperNot a substantial claim

  • Classified as probably not a substantial claim.

    Study design and conductreasoning
    § 1 Introduction · p. 2

    Each meta-rule has an associated Order constraint designed to ensure termination of the proof.

    “As shown in Fig. 3 each meta-rule has an associated Order constraint, which is designed to ensure termination of the proof (see Sect. 4.1).”
    Quote in the paperSubstantial claim

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

    Premisecitation
    § 1 Introduction · p. 2

    In Muggleton et al. 2014, definite clause grammars were learned with predicate invention using MIL.

    “By contrast, in (Muggleton et al. 2014) definite clause grammars were learned with predicate invention using Meta-Interpretive Learning (MIL).”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites Muggleton et al. 2014 source

  • May combine two claims.

    Premisecitation
    § 1 Introduction · p. 2

    MIL supports efficient predicate invention and learning of recursive logic programs built as a set of metalogical substitutions by a modified Prolog meta-interpreter.

    “MIL (Muggleton and Lin 2013; Muggleton et al. 2014; Lin et al. 2014) is a technique which supports efficient predicate invention and learning of recursive logic programs built as a set of metalogical substitutions by a modified Prolog meta-interpreter (see Fig. 2) which acts as the central part of the ILP learning engine.”
    Quote in the paperSubstantial claim0 of 3 sources checked
    • cites Muggleton and Lin 2013 source
    • cites Muggleton et al. 2014 source
    • cites Lin et al. 2014 source

  • Classified as probably not a substantial claim.

    Premisecitation
    § Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited · p. 1

    A recent paper demonstrated that both predicate invention and the learning of recursion can be efficiently implemented for regular and context-free grammars, by way of metalogical substitutions with respect to a modified Prolog meta-interpreter which acts as the learning engine.

    “However, a recent paper demonstrated that both predicate invention and the learning of recursion can be efficiently implemented for regular and context-free grammars, by way of metalogical substitutions with respect to a modified Prolog meta-interpreter which acts as the learning engine.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites Muggleton et al. 2014 source

  • Classified as probably not a substantial claim.

    Interpretationnone given
    § Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited · p. 1

    New predicate symbols are introduced as constants representing existentially quantified higher-order variables.

    “New predicate symbols are introduced as constants representing existentially quantified higher-order variables.”
    Quote in the paperSubstantial claim

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

    Study design and conductnone given
    § Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited · p. 1

    The Metagol code and datasets described in this paper have been made publicly available on a website to allow reproduction of results.

    “The Metagol code and datasets described in this paper have been made publicly available on a website to allow reproduction of results in this paper.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationnone given
    § 1 Introduction · p. 3

    A fragment of the dyadic datalog class is Turing equivalent, allowing the learning of complex recursive programs such as robot strategies.

    “We show that a fragment of this class is Turing equivalent, allowing the learning of complex recursive programs such as robot strategies.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Study design and conductreasoning
    § 4.1 Ordering the Herbrand Base · p. 9

    Termination is guaranteed because atoms higher in the Herbrand Base are always proved by ones lower in the ordering, and the ordering is finite and cannot be infinitely descending.

    “Termination is guaranteed because atoms higher in the Herbrand Base are always proved by ones lower in the ordering. Also the ordering is finite and so cannot be infinitely descending.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Premisecitation
    § 2 Related work · p. 4

    Early approaches to predicate invention based on W operators within the inverting resolution framework had inherent problems in controlling search and their completeness was never demonstrated, partly because of the lack of a declarative bias to delimit the hypothesis space.

    “Early approaches were based on the use of W operators within the inverting resolution framework (Muggleton and Buntine 1988; Rouveirol and Puget 1989). However, apart from the inherent problems in controlling the search, the completeness of these approaches was never demonstrated, partly because of the lack of a declarative bias to delimit the hypothesis space.”
    Quote in the paperSubstantial claim0 of 2 sources checked
    • cites Muggleton and Buntine 1988 source
    • cites Rouveirol and Puget 1989

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

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

    Interpretationreasoning
    § 2 Related work · p. 4

    Owing to the existentially quantified variables in the meta-rules, the resulting first-order theories are strictly logical generalisation of the meta-rules.

    “Owing to the existentially quantified variables in the meta-rules, the resulting first-order theories are strictly logical generalisation of the meta-rules.”
    Quote in the paperNot a substantial claim

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

    Premisecitation
    § 2 Related work · p. 4

    Predicate invention is essential for automating the introduction of auxiliary predicates within top-down programming.

    “Predicate Invention has been viewed as an important problem since the early days of ILP (e.g. Muggleton and Buntine 1988; Rouveirol and Puget 1989; Stahl 1992) since it is essential for automating the introduction of auxiliary predicates within top-down programming.”
    Quote in the paperNot a substantial claim

  • Classified as probably not a substantial claim.

    Interpretationnone given
    § 2 Related work · p. 4

    MIL introduces new predicate symbols which represent relations rather than new objects or propositions.

    “One important feature of MIL, which distinguishes it from other existing approaches, is that it introduces new predicate symbols which represent relations rather than new objects or propositions.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationreasoning
    § 3.4 Language classes and expressivity · p. 8

    Limiting to the H2^2 fragment limits the number of possible meta-rules and forces more prolific predicate invention, leading to more opportunities for internal re-use of part of the hypothesised program.

    “This restriction limits the number of possible meta-rules and forces more prolific predicate invention, leading to more opportunities for internal re-use of part of the hypothesised program.”
    Quote in the paperSubstantial claim

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

    Interpretationnone given
    § 2 Related work · p. 4

    New predicate names are introduced as higher-order skolem constants, a finite number of which are introduced during every iterative deepening of the search.

    “New predicate names are introduced as higher-order skolem constants, a finite number of which are introduced during every iterative deepening of the search.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Premisecitation
    § 2 Related work · p. 5

    The approach of Pasula and Lang for learning STRIPS-like operators is restricted to learning non-recursive operators and does not involve predicate invention.

    “The approach of Pasula and Lang (Pasula et al. 2004) for learning STRIPS-like operators in a relational language is closer to the approach described in Sect. 5.1, but is restricted to learning non-recursive operators and does not involve predicate invention.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites Pasula et al. 2004

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

  • Probably not a substantial claim: may not pass S4 (based).

    Interpretationnone given
    § 4.4 Episodes for multi-predicate learning · p. 11

    The time taken for searching the hypothesis space for the joint definition is a function of the product of the hypothesis spaces of the individual predicates.

    “This phenomenon can be explained by considering that time taken for searching the hypothesis space for the joint definition is a function of the product of the hypothesis spaces of the individual predicates.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Premisecitation
    § 2 Related work · p. 4

    Various higher-order logic learning frameworks have difficulties in incorporation of background knowledge and compatibility with more developed logic programming frameworks.

    “Various authors (Feng and Muggleton 1992; Lloyd 2003) have advocated higher-order logic learning frameworks. However, to date these approaches have difficulties in incorporation of background knowledge and compatibility with more developed logic programming frameworks.”
    Quote in the paperNot a substantial claim0 of 2 sources checked
    • cites Feng and Muggleton 1992

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

    • cites Lloyd 2003 source

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

    Study design and conductnone given
    § 1 Introduction · p. 3

    Unlike many ILP systems, only hypotheses consistent with all examples are considered in MIL.

    “Moreover, unlike many ILP systems, only hypotheses consistent with all examples are considered.”
    Quote in the paperNot a substantial claim

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

    Premisecitation
    § 2 Related work · p. 4

    λ-Prolog achieves efficient unification through assumptions on the flexibility of terms.

    “λ -Prolog (Miller 1991), is a notable exception which achieves efficient unification through assumptions on the flexibility of terms.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites Miller 1991 source

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

    Premisecitation
    § 2 Related work · p. 4

    In Cropper and Muggleton (2014), sets of irreducible or minimal sets of meta-rules can be found automatically by applying Plotkin's clausal theory reduction algorithm to an enumeration of all meta-rules in a given finite hypothesis language, resulting in meta-rules which exhibit lower runtimes and higher predictive accuracies.

    “For instance, in Cropper and Muggleton (2014) it is demonstrated that sets of irreducible, or minimal sets of meta-rules can be found automatically by applying Plotkin's clausal theory reduction algorithm to an enumeration of all meta-rules in a given finite hypothesis language, resulting in meta-rules which exhibit lower runtimes and higher predictive accuracies.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites Cropper and Muggleton 2014

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

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

    Premisecitation
    § 4.1 Ordering the Herbrand Base · p. 9

    Within ILP, search efficiency depends on the partial order of θ-subsumption.

    “Within ILP, search efficiency depends on the partial order of θ -subsumption (NienhuysCheng and de Wolf 1997).”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites NienhuysCheng and de Wolf 1997

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

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

    Study design and conductnone given
    § 4.2 Minimum cardinality hypotheses · p. 10

    Metagol D uses iterative deepening to ensure the first hypothesis returned contains the minimal number of clauses.

    “Metagol D uses iterative deepening to ensure the first hypothesis returned contains the minimal number of clauses.”
    Quote in the paperNot a substantial claim

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

    Interpretationnone given
    § 2 Related work · p. 4

    Logical equivalence with the larger set ensures completeness of the reduced set.

    “Moreover logical equivalence with the larger set ensures completeness of the reduced set.”
    Quote in the paperNot a substantial claim

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

    Interpretationreasoning
    § 2 Related work · p. 4

    Meta-rules are logical statements, which provides the potential for reasoning about them and manipulating them alongside normal first-order background knowledge.

    “By comparison with other forms of declarative bias in ILP, such as modes (Muggleton 1995; Srinivasan 2001) or grammars (Cohen 1994), meta-rules are logical statements. This provides the potential for reasoning about them and manipulating them alongside normal first-order background knowledge.”
    Quote in the paperNot a substantial claim

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

    Premisecitation
    § 2 Related work · p. 4

    Most knowledge representation languages avoid higher-order quantification owing to problems with decidability and theorem-proving efficiency.

    “Although McCarthy (1999) long advocated the use of higher-order logic for representing common sense reasoning, most knowledge representation languages avoid higher-order quantification owing to problems with decidability (Huet 1975) and theorem-proving efficiency.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites Huet 1975 source

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

    Interpretationnone given
    § 2 Related work · p. 4

    The use of meta-rules clarifies the declarative bias being employed.

    “The use of the meta-rules clarifies the declarative bias being employed.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationreasoning
    § 3.3 Learning from interpretations · p. 7

    The Learning from Interpretations setting is inappropriate for MIL because the user has no ascribed meaning for P' and C', so it would not be possible to provide examples containing full interpretations.

    “Since the user has no ascribed meaning for P ′ and C ′ , it would not be possible to provide examples containing full interpretations, and therefore the Learning from Interpretations setting is inappropriate.”
    Quote in the paperNot a substantial claim
    • The authors state this as an assumption: P' ⊆ P and C' ⊆ C represent uninterpreted predicates and constants whose interpretation is assigned by the Meta-interpreter.
    • Rests on an assumption: The user has no ascribed meaning for P' and C'.

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

    Interpretationcitation
    § 2 Related work · p. 4

    Higher-order datalog has advantages in being both expressive and decidable.

    “As a knowledge representation, higher-order datalog (see Sect. 3), first introduced in Pahlavi and Muggleton (2012), has advantages in being both expressive and decidable.”
    Quote in the paperSubstantial claim

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

    Premisecitation
    § 1 Introduction · p. 3

    MIL implementations have been demonstrated to search the hypothesis space 100-1,000 times faster than state-of-the-art ILP systems in the task of learning recursive grammars.

    “Owing to the efficiency of Prolog backtracking MIL implementations have been demonstrated to search the hypothesis space 100-1,000 times faster than state-of-the-art ILP systems (Muggleton et al. 2014) in the task of learning recursive grammars.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites Muggleton et al. 2014 source

  • Classified as probably not a substantial claim.

    Interpretationnone given
    § 4.1 Ordering the Herbrand Base · p. 9

    In the lexicographic ordering, predicates higher in the ordering are defined in terms of ones lower in the ordering.

    “In the lexicographic ordering predicates which are higher in the ordering, such as grandparent/2 , are defined in terms of ones which are lower, such as parent/2 .”
    Quote in the paperSubstantial claim

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

    Interpretationcitation
    § 2 Related work · p. 4

    In MIL, predicate invention is conducted via construction of substitutions for meta-rules employed by a meta-interpreter.

    “In the MIL framework described in Muggleton et al. (2014) and in this paper, predicate invention is conducted via construction of substitutions for meta-rules employed by a meta-interpreter.”
    Quote in the paperNot a substantial claim

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

    Interpretationreasoning
    § 2 Related work · p. 4

    Induction, abduction and predicate invention are all achieved in MIL by way of the meta-rules.

    “By contrast, induction, abduction and predicate invention are all achieved in MIL by way of the meta-rules.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationown data
    § 6 Conclusions and further work · p. 22

    In the NELL task abduction with respect to inductively inferred rules uncovered a systematic error in the existing NELL data, indicating that Metagol D shows promise in helping debug large-scale knowledge bases.

    “In the NELL task abduction with respect to inductively inferred rules uncovered a systematic error in the existing NELL data, indicating that Metagol D shows promise in helping debug large-scale knowledge bases.”
    Quote in the paperSubstantial claim

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

    Premisenone given
    § 6.1 Further work · p. 23

    A Universal Turing Machine can be considered as simply a meta-interpreter incorporated within hardware.

    “Finally it is worth noting that a Universal Turing Machine can be considered as simply a meta-interpreter incorporated within hardware.”
    Quote in the paperNot a substantial claim

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

    Interpretationown data
    § 5.3.2 Evaluation experiment: learning athletehomestadium · p. 20

    This example demonstrates the potential for the MIL framework to use and infer higher-order concepts.

    “This example demonstrates the potential for the MIL framework to use and infer higher-order concepts.”
    Quote in the paperNot a substantial claim

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

    Interpretationown data
    § 6.1 Further work · p. 22

    The greedy approach can lead to overly specific results.

    “However, the greedy approach can lead to overly specific results.”
    Quote in the paperNot a substantial claim

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

    Interpretationcitation
    § 6.1 Further work · p. 22

    The use of a non-greedy complete search for each episode leads to search time increasing exponentially in the maximum number of clauses considered.

    “This provides an interesting topic for further work since the use of a non-greedy complete search for each episode leads to search time increasing exponentially in the maximum number of clauses considered [see search bound in Lin et al. (2014)].”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites Lin et al. (2014) source

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

    Study design and conductnone given
    § 5.3.2 Evaluation experiment: learning athletehomestadium · p. 20

    This greedy search strategy has not been applied to other experiments.

    “However, this greedy search strategy has not been applied to other experiments.”
    Quote in the paperNot a substantial claim

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

    Interpretationcitation
    § 6 Conclusions and further work · p. 21

    The approach can also be implemented within more sophisticated solvers such as ASP.

    “However, the approach can also be implemented within more sophisticated solvers such as ASP (see Muggleton et al. 2014).”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites Muggleton et al. 2014 source

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

    Interpretationnone given
    § 5.3.4 Discussion · p. 21

    The NELL experiments are distinct from those on robot strategies and east-west trains in providing an initial indication of the power of the technique to reveal new and unexpected insights in large-scale real-world data.

    “The NELL experiments are distinct from those on robot strategies and east-west trains in providing an initial indication of the power of the technique to reveal new and unexpected insights in large-scale real-world data.”
    Quote in the paperNot a substantial claim

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

    Interpretationnone given
    § 5.3.4 Discussion · p. 21

    The experiment also indicates the potential for learning higher-order concepts like symmetric.

    “The experiment also indicates the potential for learning higher-order concepts like symmetric .”
    Quote in the paperNot a substantial claim

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

    Interpretationnone given
    § 6 Conclusions and further work · p. 21

    In the Prolog implementation, Metagol D, efficiency of search is achieved by constraining the backtracking search in several ways.

    “In the Prolog implementation, Metagol D , efficiency of search is achieved by constraining the backtracking search in several ways.”
    Quote in the paperNot a substantial claim

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

    Premisenone given
    § 5.3.2 Evaluation experiment: learning athletehomestadium · p. 20

    NELL presently incorporates manual annotation on concepts being symmetric or transitive.

    “NELL presently incorporates manual annotation on concepts being symmetric or transitive.”
    Quote in the paperNot a substantial claim

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

    Premisenone given
    § 6.1 Further work · p. 22

    The user is expected to provide the total orderings ⪰ P and ⪰ C over the initial predicate symbols and constants.

    “A related issue is that the user is expected to provide the total orderings ⪰ P and ⪰ C over the initial predicate symbols and constants.”
    Quote in the paperNot a substantial claim

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

    Interpretationreasoning
    § 5.3.2 Evaluation experiment: learning athletehomestadium · p. 20

    This leads to a large hypothesis space.

    “This leads to a large hypothesis space.”
    Quote in the paperNot a substantial claim

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

    Interpretationnone given
    § 6 Conclusions and further work · p. 21

    A Knuth-Bendix style total ordering can be imposed over the Herbrand base which requires predicates which are higher in the ordering to be defined in terms of lower ones.

    “For instance, a Knuth-Bendix style total ordering can be imposed over the Herbrand base which requires predicates which are higher in the ordering to be defined in terms of lower ones.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationnone given
    § 5.3.2 Evaluation experiment: learning athletehomestadium · p. 20

    When learning up to seven clauses, not only is the hypothesis space excessively large but learning requires more training examples than is consistent with the logarithmic bound in Theorem 3.

    “When learning up to seven clauses, not only is the hypothesis space excessively large but learning requires more training examples than is consistent with the logarithmic bound in Theorem 3.”
    Quote in the paperSubstantial claim

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

    Interpretationnone given
    § 5.3.2 Evaluation experiment: learning athletehomestadium · p. 20

    The approach seems promising though there are unresolved issues relating to potential overfitting.

    “The approach seems promising though there are unresolved issues relating to potential overfitting.”
    Quote in the paperNot a substantial claim

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

    Interpretationnone given
    § 6 Conclusions and further work · p. 21

    An interval inclusion ordering ensures finite termination of (mutual) recursion in the case that the Herbrand Base is infinitely ascending but finitely descending.

    “Alternatively, an interval inclusion ordering ensures finite termination of (mutual) recursion in the case that the Herbrand Base is infinitely ascending but finitely descending.”
    Quote in the paperNot a substantial claim
67 of 67

  • The paper relies on this without support.

    SLD resolution is complete, so all hypotheses consistent with the examples can be constructed.

    “Completeness of SLD resolution ensures that all hypotheses consistent with the examples can be constructed.”

  • The authors state this as an assumption.

    P' ⊆ P and C' ⊆ C represent uninterpreted predicates and constants whose interpretation is assigned by the Meta-interpreter.

    “To account for predicate invention we assume that P ′ ⊆ P and C ′ ⊆ C represent uninterpreted predicates and constants respectively, whose interpretation is assigned by the Meta-interpreter.”

  • The authors state this as an assumption.

    The UTM has a suitably designed set of machine instructions representing functions of the form used in the encoding.

    “We assume the UTM has a suitably designed set of machine instructions representing functions of the form”

  • The paper relies on this without support.

    The user has no ascribed meaning for P' and C'.

    “Since the user has no ascribed meaning for P ′ and C ′ , it would not be possible to provide examples containing full interpretations, and therefore the Learning from Interpretations setting is inappropriate.”

  • The authors state this as an assumption.

    The big data assumption holds.

    “under the big data assumption (Sect. 4.3)”

  • The paper relies on this without support.

    The simplified model of wall building is adequate for evaluating Metagol D's robot strategy learning.

    “This model is a simplification of a real-world robotics application.”
6 of 6

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Metagol's expressiveness is bounded by the metarules provided, requiring domain expertise to design appropriate templates.

    “However, the expressiveness of Metagol is bounded by the metarules provided, requiring domain expertise to design appropriate templates.”

    From ADVENT: LLM-Driven Automatic Predicate Invention for ILP (2026) · cites this paper as [13]

    The Framework (p. 6) defines learning in terms of a supplied set of meta-rules, and Further work (p. 22) acknowledges that incomplete meta-rules may affect learning. These passages support the point that the supplied rules constrain what Metagol can learn, but they do not say that designing appropriate templates requires domain expertise. (LLM, conf=0.85)

    Experimental — accuracy not yet measured

  • Recent meta-level ILP approaches often learn optimal solutions, such as programs with the fewest clauses or literals.

    “Recent meta-level ILP approaches often learn optimal solutions, such as programs with the fewest clauses (Muggleton et al. 2015; Cropper and Muggleton 2016; Kaminski et al. 2018) or literals (Corapi et al. 2011; Law et al. 2014).”

    From Learning programs by learning from failures (2021) · cites this paper as Muggleton et al. 2015

  • Metagol performs iterative deepening over the number of clauses allowed in a solution.

    “Metagol performs iterative deepening over the number of clauses allowed in a solution (Muggleton et al. 2015).”

    From Learning programs by learning from failures (2021) · cites this paper as Muggleton et al. 2015

  • A third approach has recently emerged called meta-level ILP.

    “A third approach has recently emerged called meta-level ILP (Inoue et al., 2013; Muggleton et al., 2015; Inoue, 2016; Law et al., 2020; Cropper & Morel, 2021).”

    From Inductive Logic Programming At 30: A New Introduction (2022) · cites this paper as Muggleton et al., 2015

  • Metagol uses a Prolog meta-interpreter to search for a proof of a meta-level Prolog program.

    “For instance, Metagol (Muggleton et al., 2015; Cropper & Muggleton, 2016) uses a Prolog meta-interpreter to search for a proof of a meta-level Prolog program.”

    From Inductive Logic Programming At 30: A New Introduction (2022) · cites this paper as Muggleton et al., 2015

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.

  • Training sets larger than two cannot come from the first two examples

    Minor

    The experiment reports training sizes as large as 100, but says every training set smaller than 108 was derived from the first two examples of its 108-example set. Two examples cannot supply those larger training sets.

1 of 1

Cites

Flagged first, then by citations

Research works printed but not linked: 4

  1. De Jong, G. (1981). Generalisations based on explanations. In IJCAI-81, pp. 67–69. Kaufmann.
  2. Muggleton, S. H., & Lin, D. (2013). Meta-interpretive learning of higher-order dyadic datalog: Predicate invention revisited. In Proceedings of the 23rd international joint conference artificial intelligence (IJCAI 2013), pp. 1551–1557.
  3. Rouveirol, C., & Puget, J-F. (1989). A simple and general solution for inverting resolution. In EWSL-89, pp. 201–210, London. Pitman.
  4. Srinivasan, A. (2001). The ALEPH manual. Oxford: Machine Learning at the Computing Laboratory, Oxford University.

Cited by

Sorted by citations

Related

Authors
Muggleton, S. H., Lin, D., & Tamaddoni-Nezhad, A.
Affiliations
Imperial College London (GB)
Corresponding author
Muggleton, Stephen H.
ORCID
Muggleton, Stephen H.
Venue
Machine Learning
Publisher
Springer Science and Business Media LLC
Published
2015-03-12
Volume
100
Issue
1
Pages
49-73
ISSN
  • 0885-6125 (ISSN-L)
  • 1573-0565
DOI
10.1007/s10994-014-5471-y
OpenAlex
W1769664091
Cited by
184
References
66
Citations by year
2026: 3 · 2025: 8 · 2024: 13 · 2023: 18 · 2022: 8 · 2021: 23 · 2020: 20 · 2019: 25 · 2018: 24 · 2017: 12 · 2016: 9 · 2015: 10 · 2014: 7 · 2013: 3
FWCI
17.10
Type
journal article
Language
en
Open access
Licence
www.springer.com/tdm (tdm)
Locations
  • Machine Learning (publishedVersion)
  • Spiral (Imperial College London) (submittedVersion)
  • Spiral (Imperial College London) (submittedVersion, cc-by-nc-nd)
Funders
  • Royal Academy of Engineering
  • Imperial College London
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Logic, Reasoning, and Knowledge
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
  • Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
Keywords
predicate invention, higher-order logic, PAC learnability

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