Complete Bottom-Up Predicate Invention in Meta-Interpretive Learning

1 Introduction

An optimal strategy in the chess endgame KRK (King-andRook vs King) is to successively restrict the area available to the opponent's black king using the white rook. Maintenance of this rook safety is achieved using the white king. An example of a situation in which the white king protects its rook is represented in Figure 1a. Figure 1b shows a hypothesis describing such a situation. This hypothesis includes various invented predicates representing sub-concepts. For instance, f1/2 defines the existence of a white king in a board.

We introduce a new method for partially delegating the construction of invented predicates and demonstrate it can improve learning performance. The hypothesis is divided between surface and substrate predicates as in Figure 1b. The substrate is a set of invented predicates generated in a first step by a bottom-up learner and from the background knowledge. The surface is a hypothesis built subsequently by a top-down learner which can reuse these substrate predicates. The surface hypothesis has fewer clauses owing to the use of substrate predicates and so is easier to learn.

Figure 1: Learning a chess pattern: the white king protects its rook

In MIL [Muggleton and Lin, 2013], predicate invention is conducted in a top-down fashion by allowing new predicate symbols in metasubstitutions. We introduce a new bottomup method for performing predicate invention based upon an extension of the immediate consequence operator for secondorder logic programs. For each metarule, if body literals can be resolved with the current background knowledge, then Skolem constants are bound to second-order variables in the head. The resulting head is added to the background knowledge and the resulting metasubstitution is saved as a new predicate definition. This process is iterated. We demonstrate our bottom-up method is complete with respect to a fragment of dyadic datalog. Performing bottom-up iterations reduces the number of surface clauses to be learned by the top-down learner which in turn can reduce the sample complexity.

Our contributions are 1) the introduction of a new method for performing extensive predicate invention, 2) a proof of the completeness of this method, 3) the formalisation of the definition of an equivalence relation for predicates which is used to prune redundant predicates, 4) an implementation of this method 5) experimental results over two domains demonstrating this method can significantly improve learning performance.

2 RelatedWork

2.1 Learning Game Strategies

Early approaches to learning game strategies [Shapiro and Niblett, 1982; Quinlan, 1983] use the decision tree ID3 to classify minimax depth-of-win for positions in chess end game. These approaches use a carefully selected set of board attributes as features. Conversely, we study the automated invention of features and relations from low-level primitives.

2.2 Predicate Invention

Inductive Logic Programming (ILP) systems rely on a language bias to restrict the hypothesis space. Predicate invention is a key challenge in ILP [Muggleton et al., 2012]. It has been investigated as a bias shift [Stahl, 1995] for overcoming the limitations of insufficient vocabulary for learning. New predicates might also allow for the formulation of simpler hypotheses within the target language thus reducing the learning complexity [Stahl, 1993] which we study here for MIL.

Early predicate invention approaches were based on the use of W operators within the inverting resolution framework [Muggleton and Buntine, 1988]. However, the completeness of this approach was never demonstrated. Predicate invention can be performed by adding new predicate symbols to mode declarations [Corapi et al., 2011; Law et al., 2014], however their number and arity has to be user-provided. MIL systems [Muggleton and Lin, 2013] achieve predicate invention in a top-down fashion from the metarules, by introducing Skolem constants representing new predicate symbols. Their number depends on the depth in the iterative deepening search. Conversely, we investigate bottom-up predicate invention in MIL and do not bound the number of invented predicates as such but only bound the depth of the generation process.

Predicate Invention can be performed as a form of metalearning over time. Dependent Learning [Lin et al., 2014] allows the construction of a series of predicates with increasing levels of abstraction by solving a series of tasks with different complexity. In [Cropper, 2019], predicate invention is performed in an initial unsupervised stage. In both cases, learned hypotheses are saved to the background knowledge as predicate definitions that can be reused when solving subsequent tasks. Both approaches are based on a set of tasks, user-provided or randomly sampled. Conversely, our method builds predicate definitions from the background knowledge related to the examples and does not require additional training tasks.

2.3 Combining Top-Down and Bottom-up

Bidirectional hypothesis search strategy was originally presented in the version space algorithm [Mitchell, 1982]. Variants were implemented in algorithms alternating generalisation and specialisation steps to search through the lattice of clauses [Fensel and Wiese, 1993; Zelle et al., 1994]. Progol [Muggleton, 1995] constructs a most specific clause, the bottom clause, that entails a positive example. In a top-down step, it employs a variant of the A* search to find the best possible consistent definition in the space constrained by the bottom clause. However, [Muggleton, 1995; Fensel and Wiese, 1993] do not support automated predicate invention which restrict their expressivity. [Zelle et al., 1994] includes a mechanism for demand driven predicate invention. Conversely, our system is based upon MIL and fully supports automated predicate invention.

3 Learning Framework

3.1 Logical Notation

We assume familiarity with standard logic programming notations [Lloyd, 1984]. We consider Datalog programs which are definite logic programs without proper function symbols. A variable is second-order if it can be bound to predicate symbols. The Herbrand base BP of a first-order logic program P is the set of all ground atoms constructed with the predicates and constants in P. The process of replacing existential variables by constants in a formula is called Skolemisation. The unique constants are called Skolem constants.

3.2 Meta-Interpretive Learning

MIL [Muggleton and Lin, 2013; Muggleton et al., 2014] is a form of ILP [Muggleton, 1991]. The MIL input is a pair (B,E), where E is a set of ground atoms representing positive and negative examples E = E+ ∪ E- and B is a second-order logic program B = Bc ∪M composed of a definite first-order background knowledge Bc and metarules M. Metarules are second-order clauses with existentially quantified predicate variables and universally quantified first-order variables (see examples on Figure 2). The MIL problem is to find a hypothesis H such that B,H |= E. The proof was originally based upon an adapted Prolog meta-interpreter. It attempts to prove the examples and saves the resulting metasubstitutions for any successful proof. Metasubstitutions are the substitution of second-order variables by predicate symbols. Saved metasubstitutions can be used as background knowledge by substituting them back onto their corresponding metarules. MIL supports predicate invention, the learning of recursions and higher-order programs [Cropper and Muggleton, 2016a]. In the following, we use the MIL system Metagol [Cropper and Muggleton, 2016b].

3.3 Immediate Consequence Operator for Predicate Invention

We first recall the well-known definition of the immediate consequence operator [Van Emden and Kowalski, 1976]:

Definition 3.1 (Immediate Consequence Operator of a Definite First Order Program). Let P be a definite first-order logic program. The Immediate Consequence Operator TP associated with P is a mapping from subsets of the Herbrand base BP to subsets of BP defined as:

∀I ⊆ BP , TP (I) = {α ∈ BP | α ← B1, ..., Bm, m ≥ 0 is a ground instance of a clause in P and{B1, ..., Bm} ⊆ I}

MIL systems use second-order logic programs, therefore we extend Definition 3.1 to allow for second-order programs:

Definition 3.2 (Immediate Consequence Operator of a Definite SecondOrder Program). Let P be a definite second-order logic program. The Immediate Consequence Operator TP associated with P is an operator defined over subsets of BP as:

∀I ⊆ BP , TP (I) = {α | α ← B1, ..., Bm, m ≥ 0 is a ground instance of a clause in P and {B1, ..., Bm} ⊆ I and second order variables in α are bound to Skolem constants}

Applying the TP operator to first order logic programs generates atoms which are part of the Herbrand base of P. For second order logic programs, it generates new atoms which may have Skolem constants as predicate symbols in which case it extends the Herbrand base of P .

Example 3.1. Suppose there is a chess board with a rook r1 and a white king k1 located on the same file. We consider a second-order logic program P containing the metarule postcon and ground unit clauses. Given I = ∅, we have:

P = {P (X, Y ) ← Q(X, Y ), R(Y ); rook(r1) ←; king(k1) ←; white(k1) ←; samef ile(r1, k1) ←} TP (I) = {rook(r1), king(k1), white(k1), samef ile(r1, k1)} TP (TP (I)) = {samef ileking(r1, k1), samef ilewhite(r1, k1)}

Atoms in TP (TP (I)) are generated from the following ground instances of the postcon metarule, for which body literals are elements of TP (I). 'samefileking' and 'samefilewhite' are Skolem constants.

samef ileking(r1, k1) ← samef ile(r1, k1), king(k1). samef ilewhite(r1, k1) ← samef ile(r1, k1), white(k1).

3.4 Predicate Invention from the TB Operator

We refer in the following to TB as the immediate consequence operator associated with the second-order program B = Bc ∪M provided as input to a MIL learner. Predicates are invented as follows. The TB operator is iteratively applied to the empty set. For each new fact generated, Skolem constants are saved together with the metasubstitutions. These metasubstitutions can later be projected onto the corresponding metarules to derive the definitions of invented predicates.

Example 3.1 (Continued). Saved metasubstitutions can be projected onto the postcon metarule to derive the following first-order logic program P ′ :

3.5 Elimination of Redundant Predicates

Successive applications of the TB operator generate a series of predicate symbols together with their definitions. The number of predicate symbols thus monotonically increases with the number of iterations. To avoid cluttering the background knowledge, redundant predicates are pruned at the end of each iteration. We define a notion of equivalence of predicate based upon an equivalence of logic programs [Maher, 1988]. We recall that the success set SS(P) of a firstorder logic program P is the set of atoms from the Herbrand base of P which have a successful SLD-derivation for P .

Definition 3.3 (Success set of a predicate). Given a firstorder program P, the success set SS(p, P) of a predicate p is the subset of the success set of P restricted to atoms of p:

Definition 3.4 (Equivalence of Predicates). Two predicates p1 and p2 are equivalent given a first-order program P if they have the same success set up to renaming of the predicate symbols p1, p2:

One can verify reflexivity, symmetry and transitivity for the relation defined in Definition 3.4 and conclude it is an equivalence relation. For all predicates p1, if there exists a predicate p2 such that p1 and p2 are equivalent, p1 is said to be

Algorithm 1 Bottom-Up Learner

Input: second-order logic programB|E related to training examples E, number of iterations k, definitions of initial predicate H0

Output: logic programH 1: set H = H0 and I = ∅ 2: for i in [1,k] do 3: for all new predicates p from TB(I) do 4: if ̸ ∃ p1 ∈ H such that p1 and p are equivalent then 5: add the definition of p to H 6: add atoms from TB(I) with predicate symbol p to I 7: end if 8: end for 9: end for

redundant with respect to p2. Intuitively, predicates covering exactly the same set of ground atoms are not discriminative in a learning process, and adding redundant predicates in the background knowledge is helpless to build a hypothesis.

The success set of P is equivalent to the least fix point of the immediate consequence operator [Lloyd, 1984]: SS(P) = TP ↑ω . This provides a practical way of computing success sets, as the new atoms generated at each iteration are saved together with predicate definitions. Therefore, evaluating success sets is straightforward in this context.

Example 3.1 (Continued). Invented predicates have the success sets below and are equivalent given P ′ ∪ P :

SS(samef ileking, P ′ ∪ P ) = {samef ileking(r1, k1)} SS(samef ilewhite, P ′ ∪ P ) = {samef ilewhite(r1, k1)}

3.6 Algorithm

Our algorithm for bottom-up predicate construction is presented in Algorithm 1. Given a second-order logic program B = Bc ∪M, the learner considers B|E, the restriction of B related to the training examples E, and successively computes the immediate consequence of B|E according to Definition 3.2. Success sets of resulting invented predicates are evaluated. Predicates which are not equivalent to any current predicates following Definition 3.4 are saved into the background knowledge. Their success sets are saved such that can be used in subsequent iterations. After k iterations, the top-down learner learns a consistent hypothesis while being allowed to reuse predicates invented in bottom-up iterations.

4 Theoretical Analysis

4.1 Number of Predicate Symbols Introduced

Assumptions 1: We consider the program class H2 2 which consists of definite Datalog programs with dyadic predicates (arity at most 2) and at most 2 atoms in the body of each clause [Muggleton and Lin, 2013]. We assume the learner is given m metarules in H2 2 and p initial predicate symbols.

Theorem 4.1 (Number of predicate symbols introduced). We call y the column vector of powers of p: y = {pj }∞j=0 , and e the row vector e = {δj,1}∞j=0 , where δj,k is the Kronecker delta. For all k ∈ N∗ , the number of predicate symbols available at the iteration k is upper bounded by a function uk which is polynomial in p and m and defined by: ∀ k ∈ N, uk = eT k y, T verifying ∀ j, l ∈ N : Tj,l = ( j l-j)ml-j .

Proof. By induction over k ∈ N.

k = 0: The initial number of predicate symbols p is upper bounded by u0 = p which is polynomial in p and m.

Let k ∈ N. Suppose the number of predicate symbols available at the iteration k is bounded by uk which is polynomial in p and m. The number of different bodies that can be constructed from uk predicate symbols and a H2 2 metarule is at most u2k . The number of different bodies that can be constructed from m distinct H2 2 metarules is at most mu2k . The number of predicate symbols available at the iteration k + 1 is bounded by uk+1 = uk +m.u2k which is polynomial in p and m. Then, for all k ∈ N, the number of predicate symbols is bounded by uk, which is a non linear sequence defined by the recursive formula: u0 = p and uk+1 = uk +m.u2k .

The solution to this nonlinear recursive sequence is, from [Rabinovich et al., 1996], the expression given above.

For a fixed number of iterations k, Theorem 4.1 provides an upper bound on the number of predicate symbols introduced polynomial in p and m. This number of invented predicates is in practice limited by the initial background knowledge B. We recall that, given m metarules in H2 2 and p initial predicate symbols, top-down MIL complexity for a fixed clause bound n is O((mp3 )n ) [Lin et al., 2014], which is also a polynomial function of p and m. Our method thus has a worst-case complexity no worst than top-down MIL.

4.2 Completeness

Assumption 2: We assume metarules in M are non-recursive. We define the following iterated TB operator as ∀I ⊆ BP:

Algorithm 1 derives a program H containing predicate definitions, each having at most k non-recursive clauses from the hypothesis space. For all clauses in H, there exists a ground substitution θ of the head belonging to Tk,B(∅). In other words, H satisfies equation below for k:

Theorem 4.2 (Completeness). Given k ∈ N and a theory H within the hypothesis space defined by the primitives and metarules provided, H satisties equation 1 with parameter k only if it is derivable in k iterations of Algorithm 1.

Proof. By induction over k ∈ N. For k = 0, H = ∅. Let k ∈ N. Assume theories satisfying equation 1 with parameter k are derivable in k iterations of Algorithm 1. We consider a theory H satisfying equation 1 with parameter k + 1. For all Head ← Body ∈ H, there exists a ground substitution θ such that Head θ = A and A ∈ Tk+1,B(∅). All literals from Body θ are elements of Tk,B(∅). Then all literals from Body θ satisfy Equation (1) thus are derivable in k iterations of Algorithm 1. Performing one more iteration of Algorithm 1 derives Headθ ∈ Tk+1,B(∅) and the clause Head ← Body is saved in H. Then, clauses from H are derivable in k + 1 iterations of Algorithm 1.

If the top-down learner chosen also is complete, the system combining the bottom-up and top-down learner is complete.

4.3 Sample Complexity

Proposition 4.1 (Sample Complexity gain [Cropper, 2019]). We assume the target hypothesis expressed in its minimal form has n clauses with standard MIL. Let n- lk be the minimal number of clauses required to express the target theory after k bottom-up iterations. We call pk the actual number of predicate symbols available after k bottom-up iterations. Given p initial predicate symbols, m metarules in H2 2 , an error level ϵ and a confidence level δ, the number of examples required to achieve an error at most ϵ with confidence δ is reduced after k bottom-up iterations when:

By completeness from Theorem 4.2, it is guaranteed that the number of clauses required to express a target theory is reduced by at least lk = k after k bottom-up iterations.

5 Implementation

Sampling of background knowledge facts. In order to be relevant to the learning task, B|E is the restriction of the background knowledge B related to the examples E. Bc|E is a set of ground unit clauses sampled from the examples and initial predicates. First, the ground terms of each examples are extracted. Next, input first-order variables in the head of clauses from the initial background knowledge are instantiated to these ground terms. Every successful resolution of these instantiated heads is saved as a background fact. This process is iterated. If a resolution generates an output ground term, this ground term is saved and can be reused in further resolutions to build new facts. Examples can be sampled to ensure the number of initial facts is not too large.

Applying the TB operator. New facts and invented predicate definitions are generated by applying the TB operator from Definition 3.2 to B. Bodies of metarules in M are resolved against the background knowledge. In order to limit redundancy of the proofs, we ensure that each new proof reuses at least one fact proved in the last iteration. Hence a proof executed at the bottom-up iteration i will not be executed again at iteration j, with j > i.

Generation of Skolem constants. Skolem constants are built by concatenating the metarule's name and the instantiated second-order variables in the metarule's body. This process ensures the uniqueness of Skolem constants. If two predicates are equivalent with respect to Definition 3.4, the predicate with the shortest number of concatenated names is saved, since it has a simpler definition by construction.

6 Experiments

6.1 Research Hypotheses

We experimentally test within this section whether the use of bottom-up iterations can improve learning performance. Therefore, we investigate the following null hypotheses:

Null Hypothesis 1: Augmenting MIL systems with bottomup iterations can not improve predictive accuracies.

Null Hypothesis 2: Augmenting MIL systems with bottomup iterations can not reduce the sample complexity.

Null Hypothesis 3: AugmentingMIL systems with bottom-up iterations can not improve learning times.

To test these null hypotheses, we compare the regular version of Metagol versus Metagol augmented with bottom-up iterations. We provide the two systems with the same background knowledge and metarules in each experiment. Therefore, the only variable is the learning system 1 .

6.2 Rook Protected in Chess Endgame KRK

KRK denotes the chess ending with white having a king and a rook and black having a king. An optimal strategy is known and its correctness has been demonstrated [Bratko, 1978]. It involves reducing the area available to the black king with the white rook whilst constantly protecting the later with the white king. This experiment considers the task of learning whether the white rook is protected by its king which is an essential feature to conduct an optimal strategy.

Material. The state of the board is a list of non-empty cells. Cells are atoms of the form c(X,Y,Color,Type) and encode the current position X/Y of the piece of color Color (black or white) and type Type (king or rook). Primitives are piece/2, rook/1, king/1, white/1, black/1 and distance1/2 which holds if the arguments are two pieces separated by a Chebyshev distance of 1. Metarules provided (Figure 2) belong to H2 2 . The target theory is shown in Figure 1b.

Methods. Training instances are instances of the form rook protected(S) where S is a board state. Positive examples are generated by placing the white rook and the black king on different squares randomly selected on an empty board. The white king is placed on a random empty square at distance 1 from the rook. Negative examples are generated by altering an attribute (rank, file, color or type) selected at random of either the white king or the rook in a positive example such that the target theory does not hold for the resulting state. Training sets are built with half positive, half negative examples. We perform between 1 and 3 bottom-up iterations. Initial facts are built from a sample of size 1 of the positive examples. We measure the number of correct classifications over a set of 300 test instances generated following the same process as the training set. The default accuracy is 0.5. We compare accuracies and learning times versus the number of training examples. We measure the standard error of the mean over 100 repetitions.

Results. Accuracy results are presented in Figure 3a: a Ttest suggests that the difference in accuracy is statistically significant (p < 0.05) for a training set up with up to 16 instances thus refuting Null Hypothesis 1. Sample complexity results are detailed in Figure 3c and show that performing bottom-up iterations can reduce the sample complexity. It is consistent with Proposition 4.1 and we thus refute null hypothesis 2. Metagol with bottom-up steps requires shorter learning times as shown in Figure 3b thus refuting null hypothesis 3. The surface hypothesis from Figure 1b has a size typically reduced from 5 to 3 clauses after k = 1 bottomup iteration and to 1 clause for k = 2. It is better than the expected reduction of 1 and 2 clauses for k = 1 and k = 2 respectively guaranteed by Theorem 4.2. The number of predicates available after the iterations k = 1 and k = 2 typically is at most p1 = 18 and p2 = 42 respectively. These numbers are much lower than the worst case scenario bound provided by Theorem 4.1 which guaranteed p1 < 150 and p2 < 90150 and are consistent with Proposition 4.1. Performing more bottom-up iterations (k > 2) is not beneficial for this experiment as it can not further reduce the size of the target theory but increases learning times.

1 The code for reproducing the experiments is available at https: //github.com/celinehocquette/bottom up.git

Figure 3: KRK results: Learning "rook protected by the king"

6.3 String Transformations

Materials. We consider 94 real-world string transformation problems evaluated in [Cropper, 2019] and inspired from [Lin et al., 2014; Gulwani, 2011]. The dataset contains 10 positive examples for each problem. Each example is an atom of the form task(s1, s2) where task is the task name and s1 and s2 are input and output strings respectively. Some examples

• (c) Hypothesis learned for task p39: initial predicates are represented in bold. Predicates have been renamed for clarity.

Figure 4: String transformation experiment

are shown in Figure 4a and 4b. For each run and each task, one example is randomly selected to form the training set, the remaining nine being being left for testing.

Methods. We provide both systems with the same background knowledge from [Lin et al., 2014] containing the predicates copyalphanum/2, copy1/2, write point/2, skipalphanum/2, skip1/2, skiprest/2, make lowercase/2, make uppercase/2, make uppercase1/2 and the chain metarule (Figure 2). A functional restriction is set to compensate for the lack of negative examples. We set the size of the top-down learner search space to n ∈ [2, 4] clauses. For k ∈ [0, 3], k bottom-up iterations are performed. If a learning tasks fails and no hypothesis is returned, the default accuracy is 0. A timeout is set to 10 minutes. We measure the standard error of the mean over 20 repetitions of the 94 tasks.

Results. Results are presented in Figure 5. The accuracy increases with the number of bottom-up iterations, outperforming the regular version of Metagol, thus refuting null hypothesis 1. Moreover, both the accuracy and the percentage of tasks solved for a clause bound of n and after k bottomup iterations are greater than that's of Metagol for a clause bound of n + k. Indeed, k bottom-up iterations can reduce the target theory by more than k clauses which is more than the guarantee provided by Theorem 4.2. Learned hypotheses are characterized by a high usage of predicates invented in bottom-up iterations. For example, the hypothesis learned for the task 39 is shown in Figure 4c. Respectively one and two bottom-up iterations are enough to build the bottom two or three invented substrate predicates in which case the surface hypothesis has respectively 2 and one clauses. Conversely, Metagol requires 4 clauses to learn the same hypothesis.

7 Conclusion

We have introduced in this work a method for performing extensive predicate invention in a bottom-up fashion within MIL. The background knowledge is generalised with an extension of the immediate consequence operator for secondorder logic programs. We have demonstrated this method is complete with respect to a fragment of dyadic datalog. This methods reduces the number of clauses to be learned by the top-down learner, which can reduce the sample complexity. Our experimental results provide convincing evidence to support this claim.

We have restricted the scope of this work to second-order metarules. The use of higher-order metarules [Cropper and

(a) Accuracy

(b) Percentage of tasks solved

Muggleton, 2016a] could allow higher-order definitions to be learned, thus allowing disjunctions or recursions to be built in bottom-up iterations.

Preliminary experiments suggest our method is more effective for target theories for which the calling diagram has a tree structure instead of a more complex directed cyclic or acyclic graph. We intend to conduct a theoretical characterisation of target theories for which this method is more effective. This characterisation will be based upon the degree of reuse of invented predicates in the calling diagram and the density of relevant predicates in the search space. We also intend to determine theoretically the optimal number of bottom-up iterations given a search space.

We have shown a theoretical condition over the number of predicate symbols introduced which guarantees a sample complexity gain. We will devise a more discriminative selection of relevant predicates to guarantee this condition is fulfilled which would provide a better scalability of this method.