Learning Higher-Order Logic Programs through Abstraction and Invention

1 Introduction

Inductive Programming (IP) [Gulwani et al., 2015] is a form of machine learning which aims to learn programs from examples given background knowledge (BK). To illustrate this form of machine learning, consider teaching a robot to pour tea and coffee for all place settings at a table. For each setting there is an indication of whether the associated guest prefers tea or coffee. Figure 1 shows an example in terms of an initial state (Figure 1a) and final state (Figure 1b).

⇤The first author thanks the BBSRC and Syngenta for his PhD Case studentship. The second author acknowledges support from his Royal Academy of Engineering/Syngenta Research Chair at the Department of Computing at Imperial College London.

Now consider learning a general strategy for the task from a set of such examples. Given that there may be an arbitrary number of place settings, existing approaches to IP, such as Meta-Interpretive Learning (MIL) [Muggleton et al., 2015; Cropper and Muggleton, 2015a], would learn a recursive strategy, such as that shown in Figure 1c. In this paper, we extend the MIL framework to support learning theories with higherorder constructs, such as map, until, and ifthenelse. In this approach, an equivalent yet more compact strategy can be learned, as in Figure 1d. This is implemented in a system called MetagolAI which uses a form of interpreted BK to learn programs through a sequence of interleaved Abstraction and Invention steps (see Figure 1e). We show that the compactness of such definitions leads to substantially improved predictive accuracy and significantly reduced learning time.

The paper is organised as follows. Section 2 discusses related work. Section 3 describes the theoretical framework for the augmented form of MIL involving Abstraction and Invention, together with a sample complexity result for the new representation. Section 4 describes MetagolAI , including changes to the meta-interpretive learner required to support Abstraction and Invention. Section 5 details three experiments in which predictive accuracies and learning times for MetagolAI are compared with and without higher-order BK. In each case, a substantial increase in predictive accuracy is achieved when the higher-order BK is included, in accordance with the sample complexity result from Section 3. Finally, Section 6 summarises the outcomes and discusses further work.

2 Related work

Interest in IP has grown recently, partially due to successful applications in real-world problems, such as end-user programming [Gulwani, 2014a] and computer education [Gulwani, 2014b]. IP approaches can be classified as either task specific or general-purpose. Task specific approaches focus on learning programs for a specific domain and are often restricted to specific data types, such as numbers [Singh and Gulwani, 2012] and strings [Gulwani, 2011; Wu and Knoblock, 2015]. By contrast, the MIL framework is general-purpose, and has been used in a variety of problems including grammar induction [Muggleton et al., 2014b], string transformations [Lin et al., 2014], and extracting information from markup files [Cropper et al., 2015].

MagicHaskeller [Katayama, 2008] is a general-purpose IP system which learns Haskell functions by selecting and instantiating higher-order functions from a pre-defined vocabulary. In contrast to MagicHaskeller, MIL supports predicate invention and learning explicitly recursive programs. Igor2 [Kitzelmann, 2007] also learns recursive Haskell programs and supports auxiliary function invention but is restricted in that it requires the first k examples of a target theory to generalise over a whole class. Esher [Albarghouthi et al., 2013] learns recursive programs but needs to query an oracle each time a recursive call is encountered to ask for examples. The L2 system [Feser et al., 2015] synthesises recursive functional algorithms, but the hypotheses learned by L2 are not directly executable. By contrast, MetagolAI learns Prolog programs.

Section 5 includes experiments in learning robot strategies [Cropper and Muggleton, 2015a]. Various machine learning approaches support the construction of strategies, including the SOAR architecture [Laird, 2008], reinforcement learning [Sutton and Barto, 1998], and action learning in inductive logic programming (ILP) [Moyle and Muggleton, 1997; Otero, 2005]. This work differs from most of these approaches in that the MetagolAI learns human-readable Prolog programs.

Early work in ILP [Flener and Yıilmaz, 1999] considered using schema to specify the overall form of recursive programs to be learned. By contrast, the use of abstraction described in this paper involves higher-order definitions which treat predicate symbols as first-class citizens. This approach supports a form of abstraction which goes beyond typical first-order predicate invention [Saitta and Zucker, 2013] in that the use of higher-order definitions combined with meta-interpretation drives both the search for a hypothesis and predicate invention, leading to more accurate and compact programs.

Lloyd [Lloyd, 2003] advocates using higher-order logic in the learning process, though the approach was more strongly allied to learning functional programs, and did not support predicate invention.

3 Theoretical framework

The sets of constants, predicate symbols and first and secondorder variables are denoted C↪ P↪ V1 and V2. Elements of V1 and V2 can bind to elements of C and P respectively.

3.1 Higher-order definitions

Definition 1 (Higher-order definite clause) A higher-order definite clause is a well-formed formulae 8⌧P(s1↪ ▷▷↪ sm) ▷▷↪Qi(t1↪ ▷▷↪ tn)↪ ▷▷ where ⌧ ✓ V1 [ V2 and P↪Qi↪ sj↪ tk 2 P [ C [ V1 [ V2.

Definition 2 (Higher-order definite definition) A higherorder definition is a set of higher-order clauses which all have the form 8⌧ p(s1↪ ▷▷↪ sm) ▷▷ where ⌧ ✓ V1 [ V2 and p 2 P.

The clauses in Figure 2a comprise a higher-order definition.

3.2 Abstractions and inventions

Definition 3 (Abstraction) An abstraction is a higherorder definite clause having the form 8⌧ p(s1↪ ▷▷↪ sm) q(v1↪ ▷▷↪ vn↪ r1↪ ▷▷↪ ro)↪ ▷▷ where ⌧ ✓ V1 [ V2 and p↪ q↪ r1↪ ▷▷↪ ro 2 P and v1↪ ▷▷↪ vn 2 V1.

Within Computer Science code abstraction [Cardelli and Wegner, 1985] involves hiding complex code to provide a simplified interface for users to select key details. In this paper Abstractions contain one atom in the body which references a higher-order predicate, as shown in Figure 2b. The secondorder arguments of until are grounded to predicate symbols.

Definition 4 (Invention) In the case background knowledge B is extended to B [ H, where H is a set of higher-order definite definitions, we call predicate p an Invention iff p is defined in H but not in B.

Within this paper Abstractions are used by a meta-interpreter to generate Inventions (Figure 2c).

3.3 Meta-Interpretive Learning

Given background knowledge B and examples E the aim of a MIL system is to learn a hypothesis H such that B↪ H ♣= E, where B = Bp[M, Bp is a set of compiled Prolog definitions and M is a set of metarules (see Figure 3). MIL [Muggleton et al., 2014b; 2015; Cropper and Muggleton, 2015b; Muggleton et al., 2014a] is a form of ILP based on an adapted Prolog metainterpreter. A standard Prolog meta-interpreter proves goals by repeatedly fetching first-order clauses whose heads unify with the goal. By contrast, a MIL learner proves goals by fetching higher-order metarules (Figure 3) whose heads unify with the goal. The resulting meta-substitutions are saved, allowing them to be used as background knowledge by substituting them into corresponding metarules.

3.4 AbstractedMeta-Interpretive Learning

We extend the MIL framework by assuming the background knowledge B = Bp [ Bi [ M, where Bp consists of compiled Prolog code (compiled BK), Bi consists of higher-order definitions (interpreted BK), and M is a set of metarules. The existence of Bp supports efficient execution of background knowledge, but makes the substitution of meta-variables inaccessible to the meta-interpreter for inventing new predicates. By contrast, the existence of Bi allows the meta-interpreter to efficiently interleave Abstraction and Invention.

3.5 Language classes, expressivity and complexity

Metarules limit the language class for the hypothesis space. For instance, the Chain rule in Figure 3 restricts clauses to be definite with two body atoms and a predicate arity of two. This corresponds to the language class H2 2 . In [Lin et al., 2014] it was shown the number of H2 2 programs expressible with n clauses is O(♣M♣np3n ). The result below updates this bound for the abstracted MIL framework.

Lemma 1 (Number of abstractedH2 2 programs of size n.) Given p predicate symbols, ♣M♣ metarules, and abstractions each with at most k ≥ 1 second-order variables the number of H2 2 programs expressible with n clauses is O(♣M♣np(2+k)n ). Proof. Since each abstraction has at most k ≥ 1 secondorder variables the number of clauses Sp which can be constructed from an H2 2 metarule given p predicate symbols is at most max(p3 ↪ p2+k ) = p2+k . The set of such clauses Sm↪p has cardinality at most ♣M♣p2+k . It follows the number of logic programs constructed from a selection of n rules chosen from S♣M♣↪p is at most (♣M♣p2+k n )  (♣M♣p2+k )n = O(♣M♣np(2+k)n )▷

We use this result to develop sample complexity results for unabstracted versus abstracted MIL.

Theorem 1 (Sample complexity of unabstractedMIL) Unabstracted MIL has a polynomial sample complexity of m ≥ n ln♣M♣+p ln(3n)+ln 1 δ .

✏ Proof. According to the Blumer bound [Blumer et al., 1989] the error of consistent hypotheses is bounded by ✏ with probability at least (1 - δ) once m≥ ln♣H♣+ln 1 δ +ln(c) ✏ , where ♣H♣ is the size of the hypothesis space. From [Lin et al., 2014] ♣H♣ = c(♣M♣np3n + d) where c↪ d are constants. Applying logs and substiting gives m ≥ n ln♣M♣+♣p ln(3n)+ln 1 δ ✏ .

Theorem 2 (Sample complexity of abstracted MIL) Abstracted MIL has a polynomial sample complexity of m ≥ n ln♣M♣+p ln((2+k)n)+ln 1 δ .

✏ Proof. Analogous to Theorem 1.

We now consider the ratio of these bounds in the case n ≫ p.

Proposition 1 (Ratio of unabstracted and abstracted bounds) Given m↪mA are the bounds on the number of training examples required to achieve error less than ✏ with probability at least 1 - δ and n↪ nA are the numbers of clauses in the minimum expression of the target theories in these cases then the ratio m : mA approaches n : nA in the case n ≫ p. Proof. Since n ≫ p it follows m : mA ⇡ (n ln♣M♣ : nAln♣M♣) = n : nA.

Proposition 1 indicates abstraction in MIL reduces sample complexity proportional to the number of clauses required to express abstracted hypotheses. For instance, in Figure 1 the use of until and ifthenelse reduces the hypothesis size by one clause each. Thus the minimal hypothesis reduces from six clauses to four leading to a sample complexity reduction of 3 : 2. Figure 4 tabulates higher-order predicates with corresponding clause reductions.

4 MetagolAI

MetagolAI extends Metagol 1 , an existing MIL implementation, to support Abstractions and Invention by learning with interpreted BK. Figure 5 shows the implementation of MetagolAI as a generalised meta-interpreter [Muggleton et al., 2015], similar in form to a standard Prolog meta-interpreter.

Background knowledge The key difference between MetagolAI and Metagol is the introduction of the second prove aux clause in the meta-interpreter, denoted in boldface.

1 https://github.com/metagol/metagol

prove([],H,H). prove([Atom♣Atoms],H1,H2):- prove aux(Atom,H1,H3), prove(Atoms,H3,H2). prove aux(Atom,H,H):- call(Atom). prove aux(Atom,H1,H2):- background((Atom:-Body)), prove(Body,H1,H2). prove aux(Atom,H1,H2):- member(sub(Name,Subs),H1), metarule(Name,Subs,(Atom :- Body)), prove(Body,H1,H2), metarule(Name,Subs,(Atom :- Body)),

prove aux(Atom,H1,H2):- new metasub(H1,sub(Name,Subs)), abduce(H1,H3,sub(Name,Subs)), prove(Body,H3,H2).

Figure 5: Prolog code for the MetagolAI meta-interpreter. The clause denoted in boldface is used to fetch higher-order clauses from the interpreted BK.

This clause allows MetagolAI to prove a goal by fetching a clause from the interpreted BK (such as map) whose head unifies with a given goal. The distinction between compiled BK and interpreted BK is that whereas a clause from the compiled BK is proved deductively by calling Prolog, a clause from the interpreted BK is proved through meta-interpretation. This approach allows for predicate invention to be driven by the proof of conditions (as in filter) and functions (as in map). Interpreted BK is different to metarules because the clauses are all universally quantified. By contrast, metarules contain existentially quantified variables whose meta-substitutions form the hypothesised program. Figure 6 shows examples of the three forms of BK used by MetagolAI .

Algorithm MetagolAI first tries to prove a goal deductively using compiled BK by delegating the proof to Prolog (call(Atom)). Failing this, MetagolAI tries to unify the goal with the head of a clause in the interpreted BK (background((Atom:-Body))) and tries to prove the body goals of the clause. Failing this, MetagolAI tries to unify the goal with the head of a metarule (metarule(Name,Subs,(Atom :- Body))) and to bind the existentially quantified variables in a metarule to symbols in the signature. MetagolAI saves the resulting meta-substitutions (Subs) and tries to prove the body goals of the metarule. After proving all goals, a Prolog program is formed by projecting the meta-substitutions onto their corresponding metarules. Negation as failure [Clark, 1987] is used to negate predicates in the compiled BK. Negation of invented predicates is unsupported and is left for future work.

5 Experiments

This section describes three experiments 2 which compare abstracted MIL with unabstracted MIL, i.e. learning with and without interpreted higher-order BK. To do this, we compare MetagolAI (which supports interpreted BK) with Metagol (which does not support interpreted BK). Accordingly, we investigate the following null hypotheses:

Null hypothesis 1 MetagolAI cannot learn more accurate programs than Metagol

Null hypothesis 2 MetagolAI cannot learn programs quicker than Metagol

Common materials We provide MetagolAI and Metagol with the same BK. The compiled BK varies in each experiment. The interpreted BK contains the following definitions: map/3,reduce/3,reduceback/3, until/4, and ifthenelse/5. The metarules used are shown in Figure 3. Therefore, the only variable in the experiments is the learning system. The only difference between the two systems is the additional clause used by MetagolAI , described in Section 4.

Common methods We train using m randomly chosen positive examples for each m in the set ¶1,2,3,4,5♦. We test using 40 examples, half positive and half negative, so the default accuracy is 50%. We average predictive accuracies and learning times over 20 trials. For each learning task, we enforce a 10-minute timeout.

5.1 Robot waiter

This experiment revisits the waiter example in Figure 1, in which a robot waiter is learning to serve drinks.

Materials The state is a list of facts. In the initial state, the robot starts at position 0; there are d cups facing down at positions 1↪ ▷ ▷ ▷ ↪ d; and for each cup there is a preference for tea or coffee. In the final state, the robot is at position d+1; all the cups are facing up; and each cup is filled with the preferred drink. We generate positive examples as follows. For the initial state, we select a random integer d from the interval [1↪ 20] as the number of cups. For each cup, we randomly select whether the preferred drink is tea or coffee, and set it facing down. For the final state, we update the initial state so that each cup is facing up and is filled with the preferred drink. To generate negative examples, we repeat the aforementioned procedure, but we modify the final state so that the drink choice is incorrect for a random subset of k drinks. The robot can perform the following fluents and actions (details omitted for brevity) defined as compiled BK: at end/1, wants tea/1, wants coffee/1, move left/2, move right/2, turn cup over/2, pour tea/2, and pour coffee/2.

2 Experimental data are available at http://ilp.doc.ic.ac.uk/ijcai16metagolai

Results Figure 7a shows that MetagolAI learns more accurate programs than Metagol, refuting null hypothesis 1. Figure 7b shows that MetagolAI learns programs quicker than Metagol, refuting null hypothesis 2. Figure 1 shows example programs learned by Metagol (c) and MetagolAI (d)). Although both programs are general and can handle any number of guests and any assignment of drink preferences, program (b) is smaller because it uses the higher-order abstractions until and ifthenelse. This compactness affects predicate accuracies because whereas MetagolAI can find solutions in the allocated time, Metagol stuggles because the solutions are too long.

5.2 Chess strategy

Programming robust chess playing strategies is an exceptionally difficult task for human programmers [Bratko and Michie, 1980]. Consider the concept of maintaining a wall of pawns to support promotion [Harris, 1988]. In this case, we might start by trying to inductively program the simple situation in which a black pawn wall advances without interference from white. Having constructed such a program one might consider using negative examples involving interposition of white pieces to deal with exceptional behaviour. Figure 8 shows such an example, where in the initial state pawns are at different ranks, and in the final state all the pawns have advanced to rank 8, but the other pieces have remained in the initial positions. In this experiment, we try to learn such strategies.

Materials The state is a list of pieces, where a piece is denoted as a triple of the form (Type,Id,X/Y), where Type is the type (king=k, pawn=p, etc.), Id is a unique identifier, and X/Y is the position. We generate positive examples as follows. For the initial state, we select a random subset of n pieces from the interval [2↪ 16] and randomly place them on the board. For the final state, we update the initial state so that each pawn finishes at rank 8. To generate negative examples, we repeat the aforementioned procedure but we randomise the final state positions, whilst ensuring that the input/output pair is not a positive example. We use the compiled BK shown in Figure 9.

at rank8(( , , /8)). is pawn((p, , )). not pawn(X):-not(is pawn(X)). empty([]). move forward((Type,Id,X/Y1),(Type,Id,X/Y2)):- Y1 < 8,Y2 is Y1+1. move forward(A,B,Id):- append(Prefix,[(Type,Id,X/Y1)♣Suffix],A), Y1 < 8,Y2 is Y1+1, append(Prefix,[(Type,Id,X/Y2)♣Suffix],B).

Results Figure 10a shows that MetagolAI learns programs approaching 100% accuracy after two examples. By contrast, Metagol learns programs with around default accuracy. This result refutes null hypothesis 1. The semi-log plot in Figure 10b shows that MetagolAI learns programs quicker than Metagol, refuting null hypothesis 2. We can explain these results by looking at the sample programs learned in Figure 11. MetagolAI (b) learns a small higher-order program using the abstractions map and until. In this program, the map operation decomposes the problem into smaller sub-problems of finding how to move a single piece to rank 8. These sub-goals are solved by the chess1 predicate. By contrast, Metagol (a) learns a larger recursive and more specific first-order program.

5.3 Drop lasts

In this experiment, the goal is to learn a program droplasts which drops the last element from each sublist of a given list, a problem frequently used to evaluate IP systems [Kitzelmann, 2007]. Figure 12 shows input/output examples for this problem.

chess(A,B):-chess2(A,C),chess2(C,B).

chess2(A,B):-chess1(A,C),chess1(C,B).

chess1(A,B):-move forward(A,B,p3).

chess2(A,B):-move forward(A,B,p5).

(a) First-order program

chess(A,B):-map(A,B,chess1).

chess1(A,A):-not pawn(A).

chess1(A,B):-until(A,B,at rank8,move forward).

(b) Higher-order program

Figure 12: Input/output examples for the droplasts experiment

Materials We generate training examples as follows. To form the input, we select a random integer i from the interval [2↪ 20] as the number of sublists. For each sublist i, we select a random integer k from the interval [1↪ 100] and populate sublist i with k random integers. To form the output, we wrote a Prolog program to drop the last element from each sublist. We use the compiled BK shown in Figure 13.

head([H♣ ],H). tail([ ♣T],T). concat([H♣T],B,C):-append([H♣T],[B],C). concat(A,B,C):-append([A],[B],C).

Results MetagolAI achieved 100%accuracy after two examples (plot omitted for brevity). Figure 14 shows the program learned by MetagolAI . This program contains a number of noteworthy sub-programs. The invented predicate droplasts1 reverses a given list. The invented predicate droplasts3 drops the last element from a single list by (1) reversing the list by calling droplasts1, (2) dropping the head from the reversed list, and (3) reversing the shortened list back to the original order by again calling droplasts1. Finally, droplasts maps over the input list and applies droplasts3 to each sublist to form the output list. This program highlights invention through the repeated calls to droplasts1 and abstraction through the higherorder functions. By contrast, Metagol was unable to learn any solution for this problem because the corresponding first-order program is too long and thus the search is intractable.

Further discussion To further demonstrate invention and abstraction, consider learning a program d droplasts which extends the droplasts problem so that, in addition to dropping the last element from each sublist, the whole last sublist is also dropped. For this problem, given two examples under the same conditions as in Section 5.3, MetagolAI learns the program in Figure 15. The learned program is similar to the droplasts program, but it makes an additional final call to the invented predicate d droplasts3, which is used twice in the program as both a higher-order argument in d droplasts4 and as a first-order predicate in d droplasts.

6 Conclusions and further work

We have introduced MetagolAI which extends the MIL framework to support learning compact programs by using higherorder Abstractions. Our sample complexity results indicate that the consequent reduction in the number of clauses in the minimal representation of the target leads to a reduced hypothesis space which in turn leads to reductions in the size of the sample complexity required to learn the target theory. These complexity results are consistent with our experiments which indicate increased predictive accuracy and decreased learning time for abstracted MIL compared with unabstracted MIL.

Future work The experiments in this paper were largely related to the use of functional constructs, such as map and reduceback, within logic programs. However, we would like to investigate the use of relational constructs. For instance, consider the following higher-order definition of a closure.

closure(P,X,Y) P(X,Y). closure(P,X,Y) P(X,Z), closure(P,Z,Y).

This definition could be used to learn compact abstractions of relations such as the following.

ancestor(X,Y) closure(parent,X,Y). lessthan(X,Y) closure(increment,X,Y). subterm(X,Y) closure(headortail,X,Y).

Moreover, the issue of how metarules might themselves be learned could be treated in a similar fashion using higher-order programs such as the following.

chain(P,Q,R,X,Y) Q(X,Z), R(Z,Y).

inverse(P,Q,X,Y) Q(Y,X).

In summary we believe that the use of abstractions in machine learning provides an important new approach to the use of powerful programming constructs within IP. We believe that such approaches could have wide application in AI domains such as planning, vision, and natural language processing.