Meta-Interpretive Learning of Higher-Order Dyadic Datalog: Predicate Invention revisited

1 Introduction

Suppose we machine learn a set of Family Relationships such as those in Figure 1. If examples of the ancestor relation are provided and the background contains only father and mother facts, then a system must not only be able to learn ancestor as a recursive definition but also simultaneously invent parent to learn these definitions.

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 a hard and largely under-explored topic [Muggleton et al., 2011]. ILP systems such as ALEPH [Srinivasan, 2001] and FOIL

∗The authors would like to acknowledge support from the Royal Academy of Engineering and the Syngenta University Innovation Centre at Imperial College.

[Quinlan, 1990] have no predicate invention and limited recursion learning and therefore cannot learn recursive grammars from example sequences. By contrast, in [Muggleton et al., 2013] definite clause grammars are learned using MetaInterpretive Learning (MIL). In extending MIL to Dyadic Datalog we start by noting each clause of the target theory in Figure 1 takes the form of one of the following meta-rules.

These three higher-order meta-rules are incorporated (with existential variables P, Q, R, X, Y and universal variables x, y, z) in the clauses of the following Prolog meta-interpreter.

The two examples shown in the upper part of Figure 1 could be proved using the Prolog goal

← prove(ancestor, jake, bob), prove(ancestor, alice, jane)

given the abduced facts in Figure 1. Note that p3 is an invented predicate corresponding to parent with the abduced facts corresponding to the Instantiated Hypothesis 1 in the lower part of Figure 1.

Completeness of abduction ensures that all hypotheses consistent with the examples can be constructed. Moreover, unlike many ILP systems, only hypotheses consistent with all examples are considered. Owing to the efficiency of Prolog backtracking MIL implementations have been demonstrated to search the hypothesis space 100-1000 times faster than state-of-the-art ILP systems [Muggleton et al., 2013] in the task of learning recursive grammars 2 . In this paper we show how, by suitably constraining the search, MIL's efficiency and completeness advantages can be extended to the broader class of Dyadic Datalog programs. We demonstrated this class to be Turing equivalent, allowing the learning of complex recursive programs such as robot strategies.

The paper is organised as follows. Section 2 describes the MIL framework. The implementation of the MetagolD 3 system is then given in Section 3. Experiments on predicate invention for structuring robot strategies and construction of higher-order concepts for the NELL language learning domain are given in Section 4. In Section 5 we provide a comparison to related work. Lastly we conclude the paper and discuss future work in Section 6.

2 MIL framework

2.1 Logical notation

A variable is represented by an upper case letter followed by a string of lower case letters and digits. A function symbol is a lower case letter followed by a string of lower case letters and digits. A predicate symbol is a lower case letter followed by a string of lower case letters and digits. The set of all predicate symbols is referred to as the predicate signature and denoted P. The arity of a function or predicate symbol is the number of arguments it takes. A constant is a function or predicate symbol with arity zero. The set of all constants is referred to as the constant signature and denoted C. Functions and predicate symbols are said to be monadic when they have arity one and dyadic when they have arity two. Variables and constants are terms, and a function symbol immediately followed by a bracketed n-tuple of terms is a term. A variable is first-order if it can be substituted for by a term. A variable is higher-order if it can be substituted for by a predicate symbol. A predicate symbol or higher-order variable immediately followed by a bracketed n-tuple of terms is called an atomic formula or atom for short. The negation symbol is ¬. Both A and ¬A are literals whenever A is an atom. In this case A is called a positive literal and ¬A is called a negative literal. A finite set (possibly empty) of literals is called a clause. A clause represents the disjunction of its literals. Thus the clause {A1,A2, ..¬Ai, ¬Ai+1, ...} can be equivalently represented as (A1 ∨ A2 ∨ ..¬Ai ∨ ¬Ai+1 ∨ ...) or A1,A2, .. ← Ai,Ai+1, .... A Horn clause is a clause which contains at most one positive literal. A Horn clause is unit if and only if it contains exactly one literal. A denial or goal is a Horn clause which contains no positive literals. A definite clause is a Horn clause which contains exactly one positive literal. The positive literal in a definite clause is called the head of the clause while the negative literals are collectively called the body of the clause. A unit clause is positive if it contains a head and no body. A unit clause is negative if it contains one literal in the body. A set of clauses is called a clausal theory. A clausal theory represents the conjunction of its clauses. Thus the clausal theory {C1,C2, ...} can be equivalently represented as (C1∧C2∧...). A clausal theory in which all predicates have arity at most one is called monadic. A clausal theory in which all predicates have arity at most two is called dyadic. A clausal theory in which each clause is Horn is called a logic program. A logic program in which each clause is definite is called a definite program. Literals, clauses and clausal theories are all well-formed-formulae (wffs) in which the variables are assumed to be universally quantified. Let E be a wff or term and σ, τ be sets of variables. ∃σ.E and ∀τ.E are wffs. E is said to be ground whenever it contains no variables. E is said to be higherorder whenever it contains at least one higher-order variable or a predicate symbol as an argument of a term. E is said to be datalog if it contains no function symbols other than constants. A logic program which contains only datalog Horn clauses is called a datalog program. The set of all ground atoms constructed from P, C is called the datalog Herbrand Base. θ = {v1/t1, .., vv/tn} is a substitution in the case that each vi is a variable and each ti is a term. Eθ is formed by replacing each variable vi from θ found in E by ti. µ is called a unifying substitution for atoms A, B in the case Aµ = Bµ. We say clause C θ-subsumes clause D or C ⪰θ D whenever there exists a substitution θ such that Cθ ⊆ D.

1 Instantiate meta-rules using meta1, meta2 and meta3 facts.

2 MetagolR and MetagolC F learn Regular and Context-Free grammars respectively.

3 MetagolD learns Dyadic Datalog programs.

2.2 Framework

We first define the higher-order meta-rules incorporated within the Prolog meta-interpreter.

Definition 1 (Meta-rules) A meta-rule is a higher-order wff

where σ, τ are disjoint sets of variables, P,Qi ∈ σ ∪ τ ∪ P and s1, .., sm, t1, .., tn ∈ σ ∪ τ ∪ C. Meta-rules are denoted concisely without quantifiers as

In general, unification is known to be semi-decidable for higher-order logic [Huet, 1975]. We now contrast the case for higher-order datalog programs.

Proposition 1 (Decidable unification) Given higher-order datalog atoms A = P(s1, .., sm), B = Q(t1, .., tn) the existence of a unifying substitution µ is decidable. Proof. A, B has unifying substitution µ iff p(P, s1, .., sm)µ = p(Q, t1, .., tn)µ.

This construction is used to incorporate meta-rules within clauses of the Prolog meta-interpreter shown in Section 1 .

Definition 2 (Meta-rule incorporation) The meta-rule ∃σ∀τP(s1, .., sm) ← ..,Qi(t1, .., tn), .. is incorporated in the Prolog meta-interpreter M iff M contains a clause Head ← Body where Head = prove(P, s1, .., sm) and Body contains prove(Qi, t1, .., tn), metar(σ) and typet(v) for each v ∈ τ .

The atoms metar(σ) and typet(v) provide groundings for all variables within the meta-rule.

Definition 3 (MIL setting) Given a meta-interpreter M, definite program background knowledge B and ground positive and negative unit examples E+,E-, MIL returns a higher-order datalog program hypothesis H if one exists such that M, B, H |= E+ and M, B, H, E- is consistent.

2.3 Language classes and expressivity

We now define language classes for instantiated hypotheses.

Definition 4 (Hi j program class) Assuming i, j are natural, the class Hi j contains all higher-order definite datalog programs constructed from signatures P, C with predicates of arity at most i and at most j atoms in the body of each clause.

The class of dyadic logic programs with one function symbol has Universal Turing Machine (UTM) expressivity [T¨arnlund, 1977]. Note that H2 2 is sufficient for the Family example in Section 1. This fragment also has UTM expressivity, as demonstrated by the following H2 2 encoding of a UTM in which S, S1, T represent Turing machine tapes.

utm(S,S) ← halt(S). utm(S,T) ← execute(S,S1), utm(S1,T). execute(S,T) ← instruction(S,F), F(S,T).

Below assume G is a datalog goal and program P ∈ H2 2 .

Proposition 2 (Undecidable fragment of H2 2 ) The satisfiability of G, P is undecidable when C is infinite. Proof. Follows from undecidability of halting of UTM above.

The situation differs in the case C is finite.

Theorem 1 (Decidable fragment of H2 2 ) The satisfiability of G, P is decidable when P, C is finite. Proof. The set of Herbrand interpretations is finite.

We limit ourselves to the H2 2 fragment throughout this paper.

3 Implementation

The MetagolD system is an implementation of the MIL setting in Yap Prolog and is a modification of a simple MetaInterpreter of the form shown in Section 1. The modifications are aimed at increasing efficiency of a Prolog backtracking search which returns the first satisfying solution of a goal

where e+i ∈ E+ and e-j ∈ E- and not represents negation by failure. In particular, the modifications include methods for a) ordering the Herbrand Base, b) returning a minimal cardinality hypothesis, c) logarithmic-bounding the maximum depth of iterative deepening and d) use of a series of episodes for ordering multi-predicate incremental learning.

3.1 Ordering the Herbrand Base

Within ILP, search efficiency depends on the partial order of θ-subsumption [Nienhuys-Cheng and de Wolf, 1997]. Similarly in MetagolD search efficiency is achieved using a total ordering to constrain deductive, abductive and inductive operations carried out by the Meta-Interpreter and to reduce redundancy in the search. In particular, we employ KnuthBendix [Knuth and Bendix, 1970; Zhang et al., 2005] (lexicograhic) as well as interval inclusion total orderings over the Herbrand Base to guarantee termination. To illustrate, consider the following ordered variant of the chain meta-rule from Section 1.

Figure 2 illustrates alternative OrderTests which each constrain the chain meta-rule to descend through the Herbrand Base. In the lexicographic ordering predicates which are higher in the ordering, such as grandparent, are defined in terms of ones which are lower, such as parent. Meanwhile interval inclusion supports definitions of (mutually) recursive definitions such as leq, ancestor and even/odd. Interval inclusion assumes all atoms p(u, v) precede the atom q(x, y) in the ordering when the interval [x, y] includes the interval [u, v]. Finite descent guarantees termination even when an ordering is infinitely ascending (eg over the natural numbers).

3.2 Minimum cardinality hypotheses

MetagolD uses iterative deepening to ensure the first hypothesis returned contains the minimal number of clauses. The search starts at depth 1. At depth i the search returns an hypothesis consistent with at most i clauses if one exists. Otherwise it continues to depth i + 1.

3.3 Logarithmic bounding and PACmodel

In MetagolD a maximum depth bound for iterative deepening is set as d = log2m, where m is the number of examples. Assuming c is the number of distinct clauses in H2 2 for a given P, C the number of hypotheses at depth d is

Since the total number of hypotheses for an iterative deepening strategy is a constant, k, times those at the maximum depth considered, logarithmic bounding ensures the total number of hypotheses considered grows polynomially in m. Within the PAC model [Valiant, 1984] the Blumer bound [Blumer et al., 1989] can be used to show that

for the boundary case of ϵ = δ = 1 2 . Therefore MetagolD with logarithmic bounding PAC-learns the class H2 2 .

3.4 Episodes for multi-predicate learning

Learning definitions from a mixture of examples of two interdependent predicates such as parent and grandparent requires more examples and search than learning them sequentially in separate episodes. In the latter case the grandparent episode is learned once it can use the definition from the parent episode. 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. By contrast the total time taken for sequential learning of episodes is the sum of the times taken for the individual episodes 4 so long as each predicate is learned with low error.

4 Experiments

In this section we describe experiments in which MetagolD is used to carry out 1) predicate invention for structuring robot strategies and 2) construction of higher-order concepts for language learning using data from the NELL project [Carlson et al., 2010]. All datasets together with the implementation of MetagolD used in the experiments are available at http://ilp.doc.ic.ac.uk/metagolD/.

4.1 Robot strategy learning

In AI, planning traditionally involves deriving a sequence of actions which achieves a specific goal from a specific initial situation [Russell and Norvig, 2010]. However, various machine learning approaches support the construction of strategies 5 . Such approaches include the SOAR architecture [Laird, 2008], reinforcement learning [Sutton and Barto, 1998], and action learning within ILP [Moyle and Muggleton, 1997; Otero, 2005].

In this experiment structured strategies are learned which build a stable wall from a supply of bricks. Predicate invention is used for top-down construction of re-usable substrategies. Fluents are treated as monadic predicates which apply to a situation, while Actions are dyadic predicates which transform one situation to another.

Figure 3 shows a positive example (a) of a stable wall together with two negative examples (unstable walls) consisting of a column (b) and a wall with insufficient central support (c). Predicates are either high-level if defined in terms of buildWall(X, Y ) ← a2(X, Y ), resourceEmpty(Y ) buildWall(X, Y ) ← a2(X, Z), buildWall(Z, Y ) a2(X, Y ) ← f etch(X, Z), putOnT opOf (Z, Y )

4 Misordering episodes leads to additional predicate invention.

5 A strategy is a mapping from a set of initial to a set of goal situations.

Figure 4: Column/wall building strategy learned from positive examples. a2 is invented.

other predicates or primitive otherwise. High-level predicates are learned as datalog definitions. Primitive predicates are non-datalog background knowledge which manipulate situations as compound terms.

A wall is a list of lists. Thus Figure 3a) can be represented as [[2, 4], [1, 3, 5]], where each number corresponds to the position of a brick 6 and each sublist corresponds to a row of bricks. The primitive actions are fetch and putOnTopOf, while the primitive fluents are resourceEmpty, offset and continuous (meaning no gap). This model is a simplification of a real-world robotics application.

When presented with only positive examples, MetagolD learns the recursive strategy shown in Figure 4. The invented action a2 is decomposed into subactions fetch and putOnTopOf. The strategy is non-deterministic and repeatedly fetches a brick and puts it on top of others so that it could produce either Figure 3a or 3b.

Given negative examples MetagolD generates the refined strategy shown in Figure 5, where the invented action a2 tests the invented fluent f1. f1 can be interpreted as stable. This revised strategy will only build stable walls like Figure 3a.

An experiment was conducted to test performance of MetagolD . Training and test examples of walls containing at most 15 bricks were randomly selected with replacement. Training set sizes were {2, 4, 8, 16, 32, 64} and the test set size was 1000. Both training and test datasets contain half positive and half negative, thus the default accuracy is 50%. Predictive accuracies and associated learning times were averaged over 10 resamples for each training set size. The accuracy and learning time plots shown in Figure 5 indicate that, consistent with the analysis in Section 3.3, MetagolD , given increasing number of randomly chosen examples, produces rapid error reduction while learning time increases roughly linearly.

4.2 NELL learning

NELL [Carlson et al., 2010] is a Carnegie Mellon University (CMU) online system which has extracted more than 50 million facts since 2010 by reading text from web pages. The buildWall(X, Y ) ← a2(X, Y ), f1(Y ) buildWall(X, Y ) ← a2(X, Z), buildWall(Z, Y ) a2(X, Y ) ← a1(X, Y ), f1(Y ) a1(X, Y ) ← f etch(X, Z), putOnT opOf (Z, Y ) f1(X) ← offset(X), continuous(X)

6 Bricks are width 2 and position is a horizontal index.

Figure 5: Stable wall strategy built from positive and negative examples. a1, a2 and f1 are invented.

a) Predictive accuray

facts cover everything from tea drinking to sports personalities and are represented in the form of dyadic ground atoms of the following kind.

playssport(eva longoria,baseball) playssport(pudge rodriguez,baseball) athletehomestadium(chris pronger,honda center) athletehomestadium(peter forsberg,wachovia center) athletealsoknownas(cleveland browns,buffalo bills) athletealsoknownas(buffalo bills,cleveland browns)

Initial experiment - debugging NELL using abduction

A variant of the ILP system FOIL [Quinlan, 1990] has previously been used [Lao et al., 2011] to inductively infer clauses similar to the following from the NELL database.

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

1. athleteplaysforteam(john salmons,los angeles lakers)
2. athleteplaysforteam(trevor ariza,los angeles lakers)
3. athleteplaysforteam(shareef abdur rahim,los angeles lakers)
4. athleteplaysforteam(armando marsans,cincinnati)
5. teamhomestadium(carolina hurricanes,rbc center)
6. teamhomestadium(anaheim angels,angel stadium of anaheim)

Abductive hypotheses 2,4,5 and 6 were confirmed correct using internet search queries. However, 1 and 3 are erroneous. The problem is that NELL's database indicates that only Los Angeles Lakers has Staples Center as its home stadium. In fact Staples is home to four teams 7 . The MetagolD abductive hypotheses thus uncovered an error in NELL's knowledge 8 which assumed uniqueness of teams associated with a home stadium. This demonstrates MIL's potential for helping debug large scale knowledge structures.

Learning higher-order concepts

NELL presently incorporates manual annotation on concepts being symmetric or transitive. The following meta-rule allows MetagolD to abduce symmetry of a predicate.

Using this MetagolD abduced the following hypothesis.

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

5 Related work

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]), though limited progress has been made in this important topic recently [Muggleton et al., 2011]. In the MIL framework described in [Muggleton et al., 2013] and in this paper, predicate invention is conducted via abduction with respect to a metainterpreter and by the skolemisation of higher-order variables. This method is related to other studies where abduction has been used for predicate invention (e.g. [Inoue et al., 2010]). One important feature of MIL, which makes it distinct from other existing approaches, is that it introduces new predicate symbols which represent relations rather than new objects or propositions. This is critical for challenging applications such as robot planning. The NELL language learning task separately demonstrates MIL's abilities for learning higher-order concepts such as symmetry.

Although John McCarthy long advocated the use of higherorder logic for representing common sense reasoning [McCarthy, 1999], most knowledge representation languages avoid higher-order quantification owing to problems with decidability [Huet, 1975] and theorem-proving efficiency. λProlog [Miller, 1991], is a notable exception which achieves efficient unification through assumptions on the flexibility of terms. 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. As a knowledge representation, higher-order datalog (see Section 2), first introduced in [Pahlavi and Muggleton, 2012], has advantages in being both expressive and decidable. The NELL language application demonstrates that higher-order concepts can be readily and naturally expressed in H2 2 and learned within the MIL framework.

7 Los Angeles Lakers, Clippers, Kings and Sparks.

8 Tom Mitchell and Jayant Krishnamurthy (CMU) confirmed these errors and the correctness of the inductively inferred clause.

6 Conclusions and further work

MIL [Muggleton et al., 2013] is an approach which uses a Declarative Machine Learning [De Raedt, 2012] description in the form of a set of Meta-rules, with procedural constraints incorporated within a Meta-Interpreter. The paper extends the theory, implementation and experimental application of MIL from grammar learning to the dyadic datalog fragment H2 2 . This fragment is shown to be Turing expressive in the case of an infinite signature, but decidable otherwise. We show how meta-rules for this fragment can be incorporated into a Prolog Meta-Interpter. MIL supports hard tasks such as Predicate Invention and Recursion via abduction with respect to such a Meta-Interpreter. The MIL framework can be implemented using a simple Prolog program or within a more sophisticated solver such as ASP (see [Muggleton et al., 2013]).

We have applied MetagolD to the problem of inductively inferring robot plans and to NELL language learning tasks. In the planning task the MetagolD implementation used predicate invention to carry-out top-down construction of strategies for building both columns and stable walls. Experimental results indicate that rapid predictive accuracy increase is accompanied by polynomial (near linear) growth in search time with increasing training set sizes.

In the NELL task abduction with respect to inductively inferred rules uncovered a systematic error in the existing NELL data, indicating that MetagolD shows promise in helping debug large-scale knowledge bases. MetagolD was also shown to be capable of learning higher-order concepts such as symmetry from NELL data.

Although H2 2 is theoretically Turing equivalent, some concepts are awkward to express in this fragment. For instance, although symmetry and reflexivity are readily expressed within H2 3 , transitivity requires H2 3 .

In future work we aim to explore the incorporation of probabilities within the MIL framework. In the robot planning domain this would allow modelling of actions and fluents which fail with certain probabilities. Similarly, uncertainty of abductions of player-teams relations could be modified by taking into account the ambiguity of the home stadium relationship in the NELL application. One approach to this might be to incorporate a MIL meta-interpreter into an existing representation such as SLPs [Muggleton, 1996], Blog

[Milch and Russell, 2006] or Problog [De Raedt et al., 2007; den Broeck et al., 2010]. If successful these representations could gain from the model estimation methods of MIL, while MIL would gain from the probability estimation approaches within these systems.

Finally it is worth noting that a Universal Turing Machine can be considered as simply a meta-interpreter incorporated within hardware. In this sense, meta-interpretation is one of, if not the most fundamental concept in Computer Science. Consequently we believe there are fundamental reasons that Meta-Interpretive Learning, which integrates deductive, inductive and abductive reasoning as higher-level operations within a meta-interpreter, will prove to be a flexible and fruitful new paradigm for Artificial Intelligence.

Acknowledgments

We thank Tom Mitchell and Jayant Krishnamurthy for helpful discussions and data from the NELL database.